1

ドキュメント によるとList<T>.Sort、QuickSortアルゴリズムを使用しています。ピボットが適切に選択されていない場合、事前にソートされたリストで呼び出された場合、これは最悪の場合のパフォーマンスを示す可能性があると聞いています。

QuickSortの.NET実装は、事前に並べ替えられたリストで最悪の場合の動作を経験しますか？

私の場合、リストに対して何らかの処理を行うメソッドを作成しています。メソッドを機能させるには、リストを並べ替える必要があります。ほとんどの場合、リストはすでに並べ替えられて渡されますが、順序に小さな変更が加えられることは不可能ではありません。メソッド呼び出しごとにリストを並べ替えるのが良いかどうか疑問に思っています。明らかに、私は時期尚早の最適化の罠に陥っています。

4

3 に答える 3

5

編集：質問を編集しました。

私の質問はひどく尋ねられたと思います。それは本当にあったはずです：

List<T>.Sortソートされたリストで最悪の場合のパフォーマンスが低下しますか？

答えは「いいえ」のようです。

いくつかのテストを行いましたが、並べ替えられたリストは、ランダム化されたリストよりも並べ替えに必要な比較が少ないようです：https ://gist.github.com/3749646

const int listSize = 1000;
const int sampleSize = 10000;

var sortedList = Enumerable.Range(0,listSize).ToList();
var unsortedList = new List<int>(sortedList);

var sortedCount = 0;
sortedList.Sort((l,r) => {sortedCount++; return l - r;});
//sortedCount.Dump("Sorted");
// Returns: 10519   

var totalUnsortedComparisons = 0;
for(var i = 0; i < sampleSize; i++)
{
    var unsortedCount = 0;
    unsortedList.Shuffle();
    unsortedList.Sort((l,r) => {unsortedCount++; return l - r;});
    totalUnsortedComparisons += unsortedCount;
}

//(totalUnsortedComparisons / sampleSize).Dump("Unsorted");
// Returns: 13547

もちろん、@dlevは有効なポイントを上げます。リストがソートされているかどうかわからない状況に陥ることを決して許すべきではありませんでした。

この問題を回避するために、代わりにSortedListを使用するように切り替えました。

于 2012-09-19T13:28:05.910 に答える
2

比較を行うための難しいメトリックが得られるまで、時期尚早の最適化の罠に陥ることになります。コードを1000回以上ループで実行し、2つの異なる方法を使用して実行時間を収集し、どちらが高速で、違いが生じるかどうかを確認します。

于 2012-09-17T16:40:05.437 に答える
2

適切なアルゴリズムを選択することは、時期尚早の最適化ではありません。

リストがすでに並べ替えられているか、ほぼ並べ替えられている場合は、安定した並べ替えを使用するのが理にかなっています。 .NETには、LINQの実装が1つ付属しています。OrderBy 残念ながら、リスト全体が数回コピーされますが、コピーは依然としてO（N）であるため、重要なリストの場合は、それでも高速になります。

于 2012-09-17T16:43:18.783 に答える