检查数组是否排序的最快方法

Question

考虑到从一个非常大的函数返回的数组.

fastest如果对数组进行排序,测试的方法是什么？

最简单的方法是:

/// <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;
}

Answer 1

您将不得不访问数组的每个元素以查看是否有任何未排序的内容.

你的O(n)方法速度和它一样快,没有任何关于数组可能状态的特殊知识.

您的代码专门测试数组是否在较低索引处使用较小值进行排序.如果这不是您想要的,那么您的if会变得稍微复杂一些.您的代码评论确实表明您正在追求的目标.

如果你是有可能的状态的专业知识(比方说,你知道它的一般分类,但新的数据可能被添加到年底),您可以优化您的访问数组元素,让测试失败更快的顺序时,数组未排序.

你可以利用硬件体系结构的知识通过划分阵列,第一比较分区的边界(快速失败检查),然后在一个单独的线程(不超过每个核运行一个阵列的分区,以检查在平行阵列的多个部分每个CPU核心1个线程).请注意,如果数组分区远小于高速缓存行的大小,则线程将倾向于相互竞争以访问包含该数组的内存.多线程只对相当大的数组非常有效.

Answer 2

更快的方法，平台目标：任何 CPU，首选 32 位。
一个包含 512 个元素的排序数组：快 25%。

static bool isSorted(int[] a)
{
    int j = a.Length - 1;
    if (j < 1) return true;
    int ai = a[0], i = 1;
    while (i <= j && ai <= (ai = a[i])) i++;
    return i > j;
}

目标：x64，相同的阵列：快 40%。

static bool isSorted(int[] a)
{
    int i = a.Length - 1;
    if (i <= 0) return true;
    if ((i & 1) > 0) { if (a[i] < a[i - 1]) return false; i--; }
    for (int ai = a[i]; i > 0; i -= 2)
        if (ai < (ai = a[i - 1]) || ai < (ai = a[i - 2])) return false;
    return a[0] <= a[1];
}

忘了一个，比我的第一个代码块慢一点。

static bool isSorted(int[] a)
{
    int i = a.Length - 1; if (i < 1) return true;
    int ai = a[i--]; while (i >= 0 && ai >= (ai = a[i])) i--;
    return i < 0;
}

测量它（见灰胡子的评论）。

using System;                                  //  ????????? DEBUG ?????????
using sw = System.Diagnostics.Stopwatch;       //  static bool abc()    
class Program                                  //  {   // a <= b <= c ?  
{                                              //      int a=4,b=7,c=9;  
    static void Main()                         //      int i = 1;  
    {                                          //      if (a <= (a = b))  
        //abc();                               //      {  
        int i = 512;                           //          i++;  
        int[] a = new int[i--];                //          if (a <= (a = c))
        while (i > 0) a[i] = i--;              //          {    
        sw sw = sw.StartNew();                 //              i++;  
        for (i = 10000000; i > 0; i--)         //          }  
            isSorted(a);                       //      }  
        sw.Stop();                             //      return i > 2;  
        Console.Write(sw.ElapsedMilliseconds); //  }  
        Console.Read();                        //  static bool ABC();
    }                                          //  {
                                               //      int[]a={4,7,9};    
    static bool isSorted(int[] a) // OP Cannon //      int i=1,j=2,ai=a[0]; 
    {                                          //  L0: if(i<=j)    
        for (int i = 1; i < a.Length; i++)     //        if(ai<=(ai=a[i]))  
            if (a[i - 1] > a[i]) return false; //          {i++;goto L0;}  
        return true;                           //      return i > j;  
    }                                          //  }  
}

目标：x64。四核/线程。具有 100,000 个元素的排序数组：~55%。

static readonly object _locker = new object();
static bool isSorted(int[] a)  // a.Length > 3
{
    bool b = true;
    Parallel.For(0, 4, k =>
    {
        int i = 0, j = a.Length, ai = 0;
        if (k == 0) { j /= 4; ai = a[0]; }                        // 0 1
        if (k == 1) { j /= 2; i = j / 2; ai = a[i]; }             // 1 2
        if (k == 2) { i = j - 1; ai = a[i]; j = j / 2 + j / 4; }  // 4 3
        if (k == 3) { i = j - j / 4; ai = a[i]; j = j / 2; }      // 3 2
        if (k < 2)
            while (b && i <= j)
            {
                if (ai <= (ai = a[i + 1]) && ai <= (ai = a[i + 2])) i += 2;
                else lock (_locker) b = false;
            }
        else
            while (b && i >= j)
            {
                if (ai >= (ai = a[i - 1]) && ai >= (ai = a[i - 2])) i -= 2;
                else lock (_locker) b = false;
            }
    });
    return b;
}

1,000,000 件物品？

if (k < 2)
    while (b && i < j)
        if (ai <= (ai = a[i + 1]) && ai <= (ai = a[i + 2]) &&
            ai <= (ai = a[i + 3]) && ai <= (ai = a[i + 4])) i += 4;
        else lock (_locker) b = false;
else
    while (b && i > j)
        if (ai >= (ai = a[i - 1]) && ai >= (ai = a[i - 2]) &&
            ai >= (ai = a[i - 3]) && ai >= (ai = a[i - 4])) i -= 4;
        else lock (_locker) b = false;

让我们忘记百分比。
原始：0.77 ns/项，现在：0.22 ns/项。
2,000,000 件物品？四核：快 4 倍。