.NET4.8への移行で躓いた！List<T>.Sortアルゴリズムの変更

この記事は、 KENTEM TechBlog アドベントカレンダー2023 6日目、12月8日の記事です。

C#初心者から上級者までよく使われる List.Sort ですが、.NET4.5 のグレードアップで動作に変更がありました。

今回は変更点によってどのような影響があるのか、実際に .NET4.5 を跨ぐ移行で体験したエラー内容と一緒にご紹介いたします！

発見のきっかけ
比べてみよう
変更内容
なぜ変更があったのか
対処方法
まとめ
おわりに

発見のきっかけ

私は、現在プロジェクト業務でフレームワークの載せ替えを行っています。

この作業はエラー箇所の問題をなくすことなど多少の変更点はありますが、主な仕組みや処理を変更することはない作業になります。

変更することがないとは言っても、業務タスクには修正が必要な作業もあり両者作業は並行に行われていました。

あるとき、ロジックの変更をしていないのにも関わらずテストケースが通らない箇所がありました。

その部分というのが List.Sort メソッドだったのです。

既に変更した処理の影響だと考え、周辺を隈なく探しましたが問題はありませんでした。

List.Sortのロジック自体に変更があったのではないか⁉と変更履歴を調べたことによって原因が発覚したのです。

比べてみよう

実際の状況と近いデータでソート結果を見比べてみましょう。

以下のコードは
Number と Text を持つ DataItem型を List で持つ dataItems をソート後に出力する処理です。

dataItems の特徴は、Number には重複があるが Text には重複がないという点です。

class DataItem
{
    public int Number { get; set; }
    public string Text { get; set; }
}

static void Main()
{
    List<DataItem> dataItems = new List<DataItem>
    {
         new DataItem { Number = 1, Text = "A" },
         new DataItem { Number = 2, Text = "B" },
         new DataItem { Number = 3, Text = "C" },
         new DataItem { Number = 3, Text = "D" },
         new DataItem { Number = 2, Text = "E" },
         new DataItem { Number = 1, Text = "F" }
    };

    dataItems.Sort((x, y) => x.Number.CompareTo(y.Number));
    foreach (var item in dataItems)
        Console.WriteLine($"Number: {item.Number}, Text: {item.Text}");
}

このソート結果を .NET4.0 と 4.5 で比較をしてみます。

Number: 1, Text: F
Number: 1, Text: A
Number: 2, Text: E
Number: 2, Text: B
Number: 3, Text: C
Number: 3, Text: D

Number: 1, Text: A
Number: 1, Text: F
Number: 2, Text: B
Number: 2, Text: E
Number: 3, Text: C
Number: 3, Text: D

結果はご覧の通り
同じ Sort を使ったのにもかかわらず並び順が異なっています。

Number の比較だけでソートした結果を見比べてみると
Number が同値のときに 4.0 では元の並び順が保持されず、 4.5 では保持されていることが分かりました。
これをそれぞれ、不安定ソート、安定ソートと言います。

結果が異なれば当然テストも落ちてしまいます。

しかし、なぜこのような結果の違いが出てしまったのでしょうか。

変更内容

実は .NET4.0 から .NET4.5 へグレードアップするタイミングで System.Collections.Generic.Listにアルゴリズムの変更があり、ソート手法が変わってしまったことが原因だったのです。

以前の .NET4.0 ではクイックソートという手法が使われていました。
しかし、.NET4.5 へのグレードアップでイントロソートという手法に変更されました。

このソート手法の違いで結果の違いが発生していたのです。

learn.microsoft.com

なぜ変更があったのか

先ほどのように .NET4.5 ではイントロソートというものが使われるようになりました。

変更の理由は、各ソートの特性に関係がありました。

クイックソート (.NET4.0以前に採用されていたソート手法)

クイックソートとは、データの配列を分割しながら並び替える手法です。

ソート手法の中では最速と呼ばれていますが安定ソートではありません。

またデータを分割する境界値の選択に強く依存してしまい、 同じ値の相対的な順序がソート後に保持されるとは限らないという欠点があります。

ja.wikipedia.org

ヒープソート (イントロソートの要素となるソート手法)

ヒープソートとは、二分ヒープ木を用いて並び替える手法です。

安定ソートではありませんが、比較的安定しています。

高速であり、木構造のためデータ自体の並び替順だけで表現することができます。

ja.wikipedia.org

イントロソート (.NET4.5以降で採用されたソート手法)

イントロソートとは、クイックソートとヒープソートの組み合わせでできているソート手法です。

同じく安定ソートではありませんが、比較ソートのため基準値に依存しません。

最初にクイックソートを行い、再帰の深さがある限度を超えるとヒープソートに切り替わります。

この仕組みは、クイックソートの不安定さによる最悪のケースをカバーするために行われています。

ja.wikipedia.org

要するに .NET 4.5 の変更は .NET 4.0 で発生した最悪のケースを改善するために行われました。

実行時間などの詳細情報は各ソート説明下のリンクからご覧になっていただけますと幸いです。

対処方法

今回のケースでは dataItems の初期状態の順番が重要でした。

そのため、Text 側の条件も指定してあげることで求めている結果を得ることができます。

以下は変更前後の Sort メソッドです。

dataItems.Sort((x, y) => x.Number.CompareTo(y.Number));

dataItems.Sort((x, y) =>
{
    int result = x.Number.CompareTo(y.Number);
    if (result == 0) 
        result = x.Text.CompareTo(y.Text);
    return result;
});

このように Number だけでなく Text にもどのような条件で並び替えをしてあげるか条件を付けることで、安定的なソート結果を出すことができます。

.NET Framework 4.5.x への移行に関するランタイム変更 - .NET Framework | Microsoft Learn