非常に大きなサイズの関数から返された配列があることを考慮してください。
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;
}
配列の各要素にアクセスして、ソートされていないものがあるかどうかを確認する必要があります。
O（n）アプローチは、アレイのありそうな状態についての特別な知識がなくても、ほぼ同じくらい高速です。
コードは、配列が低いインデックスで小さい値でソートされているかどうかを具体的にテストします。それがあなたの意図したものでない場合、あなたのifは少し複雑になります。あなたのコードコメントはそれがあなたが求めているものであることを示唆しています。
可能性のある状態について特別な知識がある場合（たとえば、一般的に並べ替えられているが、最後に新しいデータが追加される可能性があることを知っている場合）、配列要素にアクセスする順序を最適化して、次の場合にテストがより速く失敗するようにすることができます。配列はソートされていません。
ハードウェアアーキテクチャの知識を活用して、アレイをパーティション分割し、最初にパーティションの境界を比較し（高速チェックに失敗）、次にコアごとに1つのアレイパーティションを別のスレッドで実行することで、アレイの複数の部分を並列にチェックできます（ CPUコアごとに1スレッド）。ただし、配列パーティションがキャッシュラインのサイズよりもはるかに小さい場合、スレッドは配列を含むメモリへのアクセスをめぐって互いに競合する傾向があることに注意してください。マルチスレッドは、かなり大きなアレイに対してのみ非常に効率的です。
より高速なアプローチ、プラットフォームターゲット：任意の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];
}
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;
}
それを測定する（greybeardのコメントを参照）。
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。4つのコア/スレッド。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.22ns/アイテム。
2,000,000アイテム？4つのコア：4倍高速。
Linqソリューション。
public static bool IsSorted<T>(IEnumerable<T> list) where T:IComparable<T>
{
var y = list.First();
return list.Skip(1).All(x =>
{
bool b = y.CompareTo(x) < 0;
y = x;
return b;
});
}
これが私のバージョンの関数IsSortedです
public static bool IsSorted(int[] arr)
{
int last = arr.Length - 1;
if (last < 1) return true;
int i = 0;
while(i < last && arr[i] <= arr[i + 1])
i++;
return i == last;
}
この関数は質問よりも少し高速ですが、これまでに投稿されたものよりも割り当てと比較が少なくなります。最悪の場合、2n+1の比較を行います。最小データサイズや配列に偶数の要素が含まれているなど、データの性質について合理的な仮定を立てることができれば、それでも改善できます。
私が考えることができる唯一の改善は、アレイの両端を同時にチェックすることです。この小さな変更は、半分の時間でそれを行います...
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;
}
これは私が思いついたものであり、特に大きなサイズのアレイでよりうまく機能することがわかりました。この関数は再帰的であり、このようにwhileループで初めて呼び出されます。
while( isSorted( yourArray, 0 )
ifステートメントは、配列の境界に達しているかどうかを確認します。
else ifステートメントはそれ自体を再帰的に呼び出し、条件がfalseになるといつでも中断します
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;
}
}
順序が重要でない場合（降順または昇順）。
private bool IsSorted<T>(T[] values) where T:IComparable<T>
{
if (values == null || values.Length == 0) return true;
int sortOrder = 0;
for (int i = 0; i < values.Length - 1; i++)
{
int newSortOrder = values[i].CompareTo(values[i + 1]);
if (sortOrder == 0) sortOrder = newSortOrder;
if (newSortOrder != 0 && sortOrder != newSortOrder) return false;
}
return true;
}
私の頭に浮かぶ質問は「なぜ」ですか？
すでにソートされているリストの再ソートを避けるためですか？はいの場合は、Timsort（PythonおよびJavaの標準）を使用してください。すでにソートされている、またはほぼソートされている配列/リストを利用するのは非常に優れています。ティムソートがこれでどれほど優れているとしても、ループ内でソートしない方が良いです。
もう1つの方法は、treap、赤黒木、AVL木など、本質的にソートされたデータ構造を使用することです。これらは、ループ内での並べ替えに代わる優れた方法です。
これは最速ではないかもしれませんが、完全なソリューションです。インデックスがi未満のすべての値は、iの現在の値と照合されます。これはphpで書かれていますが、c＃またはjavascriptに簡単に変換できます
for ($i = 1; $i < $tot; $i++) {
for ($j = 0; $j <= $i; $j++) {
//Check all previous values with indexes lower than $i
if ($chekASCSort[$i - $j] > $chekASCSort[$i]) {
return false;
}
}
}