9

コレクションを並べ替えるときに、.NET フレームワークの非常に奇妙な動作に遭遇しました。この動作は .NET 3.5 と 4.0 の間で異なります (ただし、その理由はわかっていると思います)。さらに重要なのは (これが私の本当の関心事です)、動作は同じフレームワーク上の異なるマシン間で異なります。

環境

私は、いくつかのサードパーティ ソフトウェア (この場合は spring.net ですが、問題ではありません) に依存しているソフトウェアに取り組んでおり、ある時点で、すべてのアイテムが「等しい」コレクションを並べ替えています (比較器は常に 0 を返します)。これは私の管理下にはありません。そのリストの並べ替えの動作が常に一貫していれば、私はそれで問題ありません。そうではありません。

再現方法

.NET 3.5で簡単なプロジェクトを作成し、以下のコードを実行します。3.5 でコンパイルすると、動作は一貫しているように見え、コレクションは「逆」になります ( Three、Two、Oneとして出力されます)。ここで、プロジェクト ターゲットを.NET 4 ( 4.5 ではない)に変更して、もう一度実行してください。 (スリー、ツー、ワン)!!! 私たちはまったく同じ設定をしています...

あなたのマシンで 4.0 未満のものを教えてください。反転するか反転しないか?

セットアップが正しいかどうかを評価しようとしています。

コンセプトの証明

class Program
{
    static void Main()
    {
        var collection = new ArrayList
        {
            "One",
            "Two",
            "Three",
        };

        // It should in any case write One, Two, Three
        Console.Out.WriteLine("Before sort: ");
        foreach (string item in collection)
        {
            Console.Out.WriteLine("\t"+item);
        }

        collection.Sort(new OrderComparator());

        // In .NET 3.5, it will write Three, Two, One
        // In .NET 4, it will sometimes write Three, Two, One, sometimes One, Two, Three: what is it for you?
        Console.Out.WriteLine("After sort: ");
        foreach (string item in collection)
        {
            Console.Out.WriteLine("\t" + item);
        }

        Console.Out.WriteLine("--end--");
        Console.Read();
    }
}

public class OrderComparator : IComparer
{
    public virtual int Compare(object o1, object o2)
    {
        return 0;
    }
}

また、どうしてこうなったのかわかる方いましたら教えてください！

4

1 に答える 1

9

ArrayList.Sort() によって行われる並べ替えは安定していないため、「同一の」アイテムが並べ替えられる順序を予測することはできません。

さらに、ArrayList.Sort() はランダム メカニズムを使用して QuickSort アルゴリズムのピボットを選択する場合があるため、同じアイテムが別の PC または同じ PC で異なる方法でソートされる場合があります。

[編集: 現在の実装でランダム ピボットが選択されているという証拠は見つかりませんが、配列の並べ替えはまだ不安定です。ランダム性は、おそらく呼び出されるネイティブ コードの Quicksort 実装に由来すると推測してTrySZSort()います。]

また、興味を引くために、Reflector は ArrayList.Sort() でこのコードを示しています (少し掘り下げた場合)。

internal void Sort(int left, int length)
{
    if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
    {
        this.IntrospectiveSort(left, length);
    }
    else
    {
        this.DepthLimitedQuickSort(left, (length + left) - 0x1, 0x20);
    }
}

これは、.Net 4.5 に対してまったく異なるソート アルゴリズムを選択しているようです。

于 2013-03-11T12:21:47.927 に答える