Le moyen le plus rapide pour vérifier si un tableau est trié

Plus rapide approche, la plate-forme cible: une unité centrale, Préférez 32 bits.

Un tableau trié avec 512 éléments: ~25% plus vite.

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

Cible: x64, même matrice: ~40% plus rapide.

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

Oublié un, peu moins rapide que mon premier bloc de code.

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

De la mesure (voir le vieillard du commentaire).

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

Cible: x64. Quatre cores/threads.
Un tableau trié avec 100 000 éléments: ~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 d'articles?

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;

Oublions pourcentages.

Original: 0.77 ns/item, maintenant: 0.22 ns/item.

2 000 000 d'articles? Quatre noyaux: 4 fois plus rapide.

OriginalL'auteur P_P

La seule amélioration que je peux penser à est de vérifier que les deux extrémités du tableau en même temps, ce peu de changement fera en deux temps...

public static bool IsSorted(int[] arr)
{
int l = arr.Length;
for (int i = 1; i < l/2 + 1 ; i++)
{
if (arr[i - 1] > arr[i] || arr[l-i] < arr[l-i-1])
{
return false;
}
}
return true;
}

OriginalL'auteur saul672

C'est ce que je suis venu avec et trouver des œuvres mieux, en particulier avec une plus grande taille des tableaux. La fonction est récursive et sera appelé pour la première fois, par exemple dans une boucle while comme ce

while( isSorted( yourArray, 0 )

L'instruction if vérifie si les limites du tableau ont été atteint.

L'autre si l'instruction va s'appeler lui-même de manière récursive et pause à tout moment lorsque la condition devient fausse

 public static bool IsSorted(int[] arr, int index)
{
if (index >= arr.Length - 1)
{
return true;
}
else if ((arr[index] <= arr[ index + 1]) && IsSorted(arr, index + 1))
{
return true;
}
else
{
return false;
}
}

OriginalL'auteur Michael Dera