これは、このような質問の続きです。
パフォーマンスを微調整するためのガイドラインはありますか? Big-O の利益を意味するのではなく、直線的な時間を節約するだけです。
たとえば、事前に並べ替えを行うと、または でどれくらい節約できますSortedListかSortedDictionary?
並べ替える 3 つのプロパティを持つ人物クラスがあるとします。そのうちの 1 つは年齢です。最初にオブジェクトを年齢別にバケット化する必要がありますか?
最初に 1 つのプロパティで並べ替えてから、結果のリスト/辞書を使用して 2 つのプロパティで並べ替える必要がありますか?
他に思いつく最適化はありますか?
さて、SortedList では簡単に勝てます。アイテムを挿入するには、バイナリ検索 (O(log(n)) で挿入ポイントを見つけ、次に List.Insert (O(n)) でアイテムを挿入する必要があります。 ^2). 入力項目が既にソートされている場合, Insert は O(1) に折りたたまれますが, 検索には影響しません. Populating は O(nlog(n). 2 倍のストレージ要件を許容できると仮定すると、最初にソートする方が常に効率的です。
SortedDictionary は異なり、赤黒ツリーを使用します。挿入ポイントを見つけるには、O(log(n)) が必要です。その後、ツリーの再調整が必要になる場合があります。これには O(log(n)) もかかります。したがって、辞書の作成には O(nlog(n)) が必要です。ソートされた入力を使用しても、挿入ポイントや再調整を見つける努力は変わりません。それは依然として O(nlog(n)) です。ここで重要なのは、ソートされた入力を挿入するには、ツリー自体が一定のバランスを取り直す必要があることです。入力がランダムで、ソートされた入力が必要ない場合は、より適切に機能します。
したがって、SortedList に並べ替えられた入力を入力することと、SortedDictionary に並べ替えられていない入力を入力することは、どちらも O(nlog(n)) です。ソートされた入力を提供するコストを無視すると、SortedList の Oh は、SortedDictionary の Oh よりも小さくなります。これは、List がメモリを割り当てる方法による実装の詳細です。O(log(n)) 回行うだけでよく、赤黒木は O(n) 回割り当てる必要があります。非常に小さいああところで。
注目に値するのは、単純に List にデータを入力してから Sort() を呼び出すよりも、どちらも優れていないことです。それも O(nlog(n)) です。実際、入力が既に誤ってソートされている場合は、Sort() 呼び出しをバイパスできます。これは O(n) に折りたたまれます。コスト分析は、入力をソートするために必要な作業に移行する必要があります。Sort()、O(nlog(n)) の基本的な複雑さを回避することは困難です。たとえば、SQL クエリによってソートされた入力を取得する可能性があります。完了するまでに時間がかかるだけです。
SortedList または SortedDictonary を使用するポイントは、挿入後にコレクションをソートしたままにすることです。データの入力のみを考え、変更は考えない場合は、これらのコレクションを使用しないでください。