最快的方法来检查，如果一个数组排序 [英] Fastest way to check if an array is sorted

问题描述

考虑有从一个函数，这是非常大的尺寸返回的数组。

会是怎样的最快的方法进行测试，如果数组排序？

有一个简单的方法将是：

  ///＆LT;总结＆gt;
///确定是否int数组从0排序 - ＆GT;马克斯
///＆LT; /总结＆gt;
公共静态布尔IsSorted（INT [] ARR）
{
的for（int i = 1; I＆LT; arr.Length;我++）
{
    如果（改编[I  -  1]≥常用3 [I]）
    {
    返回false;
    }
}
返回true;
}
 

解决方案

您将要访问数组中的每个元素，看看什么是排序的。

您O（n）的方法是一样快，因为它得到，没有对阵列的可能状态的任何特殊的知识。

您code专门测试，如果数组排序的数值越小以较低的指标的。如果这不是你的意图，你的如果的变得稍微复杂一些。您的code意见并建议就是你追求的是什么。

如果你拥有的可能状态的专业知识（比方说，你知道这是普遍进行排序，但新的数据可能被添加到年底），您可以优化您访问数组元素，可以在测试失败的顺序当该阵列被未排序更快。

您可以利用硬件体系结构的知识通过分割阵列，首先比较分区的界限（快速失败检查），然后在一个单独的线程运行的每个核心一个阵列分区检查并行排列的多个部分（没有每个CPU核心1个多线程）。注意的是，如果一个阵列的分区比高速缓存行的大小要小得多，线程将趋向相互争夺访问包含该阵列的存储器。多线程只会是非常有效的相当大的阵列。

Considering there is an array returned from a function which is of very large size.

What will be the fastest approach to test if the array is sorted?

A simplest approach will be:

/// <summary>
/// Determines if int array is sorted from 0 -> Max
/// </summary>
public static bool IsSorted(int[] arr)
{
for (int i = 1; i < arr.Length; i++)
{
    if (arr[i - 1] > arr[i])
    {
    return false;
    }
}
return true;
}

解决方案

You will have to visit each element of the array to see if anything is unsorted.

Your O(n) approach is about as fast as it gets, without any special knowledge about the likely state of the array.

Your code specifically tests if the array is sorted with smaller values at lower indices. If that is not what you intend, your if becomes slightly more complex. Your code comment does suggest that is what you're after.

If you were to have special knowledge of the probable state (say, you know it's generally sorted but new data might be added to the end), you can optimize the order in which you visit array elements to allow the test to fail faster when the array is unsorted.

You can leverage knowledge of the hardware architecture to check multiple parts of the array in parallel by partitioning the array, first comparing the boundaries of the partition (fail fast check) and then running one array partition per core on a separate thread (no more than 1 thread per CPU core). Note though that if a array partition is much smaller than the size of a cache line, the threads will tend to compete with each other for access to the memory containing the array. Multithreading will only be very efficient for fairly large arrays.

这篇关于最快的方法来检查，如果一个数组排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！