26

.NET 4.0 を対象とするプロジェクト内で次のテストを行っています。

[TestFixture]
public class Donkey
{
    [Test]
    public void TestListSorting()
    {
        var expected = new[]
                    {
                                MockRepository.GenerateStub<IComparable>(),
                                MockRepository.GenerateStub<IComparable>()
                    };

        var sorted = new List<IComparable>(expected);

        CollectionAssert.AreEqual(expected, sorted);
        sorted.Sort();
        CollectionAssert.AreEqual(expected, sorted);

    }
}

.NET 4.0 しかインストールされていないマシンで実行すると失敗します。.NET 4.5 のみがインストールされているマシンで実行すると、パスします。

.NET 4.5 では、からSortそれぞれ返されるオブジェクトのリストをソートするときに順序を維持するためにの実装が変更されたと想定しています。0CompareTo

さて、このテストの明らかな狂気は脇に置いてください。この種の行動に頼るのが狂っていることを私は知っています。

確かにこれは重大な変更ですか？.NET 4.0 と 4.5 の間の互換性については、このページには記載されていません。

これには理由がありますか？何か不足していますか？実際の重大な変更を示す別のページはありますか? 座ってパニックをやめるべきですか？

4

6 に答える 6

36

以前、これと似たような質問に答えたことがあります。4.5 と 4.0 の間でソート方法が変更され、クイック ソートからイントロスペクティブ ソートに変更されました。

実際には高速ですが、それでも安定したソート1ではありません。つまり、等しいアイテムの順序を維持することで、実行ごとに同じ出力が得られるソートではありません。の実装List.Sortは安定した並べ替えではないため、両方のランタイムでエラーが発生するのに十分な回数を超えて単体テストを実行したとは思いませんか?

.NET 4.5 と .NET 3.5 の両方で、リストの順序が保持される場合と保持されない場合があります。

ソートタイプが安定から不安定に変更されたとしても、重大な変更ではありません。使用される並べ替えの種類と正確な出力は、 の契約の一部ではありませんList.Sort。メソッド コントラクトが保証するのは、使用する比較子に従ってアイテムが並べ替えられるということだけです。

[MSDN のドキュメント](http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx) ではまだ (`Array.Sort` を介して) QuickSort を使用していると書かれているため、これは興味深いことですが、これは.NET 参照ソースをステップ実行する場合は、そうではありません。

1 とを組み合わせて使用​​することの定義により、不安定な並べ替えになるはずです。アルゴリズムの設計者である David Musser でさえ、彼の論文で次のように述べています。QuickSortHeapSort

クイックソートと同様に、イントロソートは安定していません (同等の要素の順序を保持しません)。そのため、安定したソート ルーチンについては別の要件が必要です。

于 2012-09-17T14:54:55.793 に答える
5

の仕様でList.Sortは、使用される並べ替えが不安定であるため、等しい要素の順序が保持されない可能性があると述べられています。等しい要素の特定の並べ替えを指定していないため、この変更を破壊的変更と呼ぶことはできません。

于 2012-09-17T14:33:20.920 に答える
3

@Rawlingが言ったように、のドキュメントをSort()見てください：

この実装は、不安定な並べ替えを実行します。つまり、2 つの要素が等しい場合、それらの順序は保持されない可能性があります。

したがって、未定義として明示的に文書化されているものをテストしようとしています。これは重大な変更ではありません。

于 2012-09-17T14:36:54.570 に答える
2

変化は見られません。他の人が既に書いたように、どちらのバージョンも不安定なソートを実行します。つまり、等しいと比較される要素の順序に依存することはできません。それらの順序は、ソート中に変更される場合と変更されない場合があります。それは確かに重大な変更ではありません。

参照: List< T >.Sort のドキュメント

于 2012-09-17T14:40:02.603 に答える
1

MSDNから

この実装は、不安定な並べ替えを実行します。つまり、2 つの要素が等しい場合、それらの順序は保持されない可能性があります。

注文が信頼できるようには見えないため、テストは無効です。また、なぜSortメソッドをテストしているのですか? 私には不必要なテストのように思えます。

于 2012-09-17T14:36:48.630 に答える
0

このような質問は、フレームワークの新しいバージョンでよく発生します。3.5 → 4.0 への移行の一部がこことここにあります。

この特定のバージョンの変更についてはList<>、質問が示すように、配列または 2 つの要素の違いが既に発生しています。別の簡単な例は次のとおりです。

using System;
using System.Linq;

namespace SortTest
{
  static class Program
  {
    static void Main()
    {
      var arr = new[] { new { Name = "Mary", Age = 17, }, new { Name = "Louise", Age = 17, }, };

      Array.Sort(arr, (x, y) => x.Age.CompareTo(y.Age));

      Console.WriteLine(string.Join(",", arr.Select(x => x.Name)));
    }
  }
}

.NET 4.0 では、これはLouise,Mary. 要素が交換されます。ただし、.NET 4.5 では出力されMary,Louiseます。2 人の女の子が同じ年齢であることに注意してください。

List<>.SortインスタンスメソッドとArray.Sort静的メソッドは、非安定ソートであると文書化されています。同じ「サイズ」の要素を任意の順序で自由に残すことができます。したがって、コードでは、同等の要素がどの順序で入ってくるかについて仮定を立ててはなりません。

対照的に、Linq のOrderByメソッドは安定した並べ替えを実行します。そう

var ordered = arr.OrderBy(x => x.Age);

MaryとLouiseは同じAge.

于 2013-09-24T11:24:35.027 に答える