テストクラッシュの理由はすぐに判明しました。同僚にとって、結果の配列の要素の順序は、参照配列の順序の逆でした。 テストメソッドのコードでは、標準のList.Sortをコンパレータと共に使用し、常に0を返します。このテストでは、要素がチーム全体で同じ順序で返され、1人の従業員ではまったく逆に返されました。 同僚が長い間更新を行っておらず、mscorlib.dllのバージョンが他のものとは非常に異なっていたことがすぐにわかりました。 これで落ち着くことができましたが、それは私にとって興味深いものになりました。私はさらに掘り下げることに決めました。
ソート後と同じ要素を持つ前のシートの内容は異なる場合があります。 msdnによると、listSortはQuickSortを使用しますが、これは誰もが知っているように不安定です。 ただし、興味深い機能が1つあります。 彼女についてさらに。
このコードを取ります：
コード
using System; using System.Collections.Generic; namespace fkComparer { internal struct Smth { public int X; public int Y; } internal class SmthComparer : IComparer<Smth> { #region Implementation of IComparer<in smth> public int Compare(Smth x, Smth y) { Result.Count++; if(xY < yY) return -1; if(xY > yY) return 1; return 0; } #endregion } internal static class Result { public static int Count; } internal class Program { static void Main() { List<Smth> list = new List<Smth> {new Smth {X = 4, Y = 4}, new Smth {X = 5, Y = 4}, new Smth {X = 6, Y = 4}}; SmthComparer comparrer = new SmthComparer(); for (int i = 0; i < aaa.Count; i++) { Console.WriteLine(list[i].X); } Console.WriteLine("***************"); aaa.Sort(comparrer); Console.WriteLine(Result.Count); Console.WriteLine("***************"); for(int i = 0; i < aaa.Count; i++) { Console.WriteLine(list[i].X); } Console.ReadLine(); } } }
原則として、特別なことは何もありません。 2つのフィールドがあるSmth構造があります。 この構造にはコンパレータがあります。 コンパレーターと同一の3つの構造でシートを飽和させ、ソートする前にシートの内容を表示し、ソートし、行われた比較の数を表示し、ソート後のシートの内容を表示します。
次に、.NET Frameworkの3つの異なるバージョンが生成するものを見てみましょう。
mscorlib.dll 4.0.30319.17929の.NET Framework 4.0バージョン
4
5
6
***************
3
***************
4
5
6
5
6
***************
3
***************
4
5
6
.NET Framework 4.0バージョンmscorlib.dll 4.0.30319.18047
4
5
6
***************
7
***************
6
5
4
5
6
***************
7
***************
6
5
4
.NET Framework 4.5
4
5
6
***************
3
***************
4
5
6
5
6
***************
3
***************
4
5
6
ご覧のとおり、.NETの古いバージョンでは、ソートは安定しており、3つの比較のみが実行されます。 .NET 4.0の最新バージョンでは、並べ替えが不安定で、7つの（！）比較が実行されます。 .NET 4.5では、並べ替えが再び堅牢になり、3つの比較が再び実行されます。
つまり .NET 4.0の新しいバージョンは、より遅い同一の要素を処理します。 これを確認するために、同一の要素の数を100に増やし、.NET 4.0-813比較の最新バージョンと、旧バージョンの.NET 4.0および.NET 4.5-390で受け取りました。
したがって、Microsoftがすべてを正しく行い、その後間違って、そして再び正しくしたことがわかります。 さらに、この問題はオリンピアードとしてどこかに戻ってくる可能性があります。
ZY：比較回数の計算を使用して、独自の最も簡単なクイックソートを作成しました。
コード
static void Sort(int left, int right) { int l = left; int r = right; Smth m = list[left + (right - left) / 2]; while(true) { Result.Count++; while(list[l].Y < mY) { l++; Result.Count++; } Result.Count++; while(list[r].Y > mY) { r--; Result.Count++; } if(l < r) { Smth t = list[l]; list[l] = list[r]; list[r] = t; l++; r--; } if(l >= r) break; } if(left < r) Sort(left, r); if(right > l) Sort(l, right); }
そして、彼女でさえ、744回しか比較されていないことを裏切りました。 比較者が.NET 4.0の最新バージョンを要求するよりも少ない