4

IComparer<T>custom を使用して .NET で配列をソートすると、アイテムとそれ自体の比較が要求されることに気付きました。

これはなぜですか？確かに、比較が同一のインデックスで行われようとしているかどうかを確認し、結果がゼロでなければならないと仮定するのは簡単な最適化ですか?

コード例:

class Comparer : IComparer<string>
{
  public int Compare(string x, string y)
  {
    Console.WriteLine("{0} vs {1}", x, y);

    return string.Compare(x, y);
  }
}

static void Main(string[] args)
{
  var values = new[] {"A", "D", "C", "B", "E"};

  Array.Sort(values, new Comparer());
}

出力あり（奇妙な比較がマークされています）：

A vs C
A vs E
C vs E
A vs C
D vs C
C vs E
C vs B
C vs C   ***
C vs C   ***
A vs B
A vs B
A vs A   ***
A vs B
A vs A   ***
D vs E
D vs E
D vs D   ***
D vs E
D vs D   ***
4

1 に答える 1

3

Array.Sort() アルゴリズムが数回変更されたため、人々はさまざまな結果を報告しています。少なくとも .NET 4.0 では、.NET 4.5 では、おそらくそれより前です。最新かつ最高のバージョンは、QuickSort から Introsort に切り替わりました。

クイックソートの非常に貧弱な最悪のケースの動作 O(n^2) に対する対策により、要素が単独で比較されています。Introsortのウィキペディアの記事では、次のように説明されています。

クイックソートで重要な操作の 1 つは、ピボット (リストが分割される要素) の選択です。最も単純なピボット選択アルゴリズムは、リストの最初または最後の要素をピボットとして取得することであり、ソート済みまたはほぼソート済みの入力の場合に不適切な動作を引き起こします。Niklaus Wirth のバリアントは、中間要素を使用してこれらの発生を防ぎ、不自然なシーケンスの O(n²) に退化します。median-of-3 ピボット選択アルゴリズムは、リストの最初、中間、および最後の要素の中央値を取ります。ただし、これは多くの現実世界の入力でうまく機能しますが、このピボット選択手法に基づくクイックソートの劇的な速度低下を引き起こす中央値 3 のキラー リストを考案することは依然として可能です。このような入力は、攻撃者によって悪用される可能性があります。

median-of-3 ピボット選択アルゴリズムの副作用が見られます。

于 2012-11-12T13:30:53.913 に答える