SortedDictionary、SortedList、および Dictionary (比較のため) を使用していくつかのテストを行いました。その結果、ディクショナリは、キー (各ディクショナリで 100,000 ペアのキーと値) に基づいて値を追加、削除、および返す際に、他の 2 つよりもはるかに高速でした。
SortedList と SortedDictionary が Dictionary よりも遅い理由を教えてもらえますか?
質問する
849 次
3 に答える
2
ソートされていないリストに基づいて、ソートされたリストの簡単な例を見てみましょう。
ソートされていないリストの任意のインデックスでの挿入時間が O(n/2) であると仮定します。ここで、n はリストのサイズです。これは、要素を挿入するためのスペースを確保するために、平均してリスト要素の半分を移動する必要があることを反映しています。
同様に、このリストでは、任意の位置から要素を削除するのも O(n/2) です。平均すると、要素の半分を移動してギャップを埋める必要があるからです。
. . .
ここで、同じ実装を想像してみてください。ただし、並べ替えを使用します。
並べ替えは挿入時に行う必要があります。つまり、新しい要素の位置を見つける必要があります。以前のすべての要素は既にソートされているため (挿入時にソートするため、これは真です)、最初からスキャンを開始できます。
これは、挿入を開始する前の O(n/2) 操作です。つまり、挿入ポイントを見つけるだけです。
バイナリ検索を使用するより良い方法は、挿入位置を見つけるために O(log n) を提供しますが、それでも挿入自体を行う O(n/2) コストを支払う前です。
スキャン操作のコストが s で、挿入操作のコストが m (移動) の場合、並べ替えられた挿入のコストは次のようになります。
s x O(log n) + m x (n/2)
ただし、ソートされていないリストの任意の位置への挿入操作は次のとおりです。
m x (n /2)
これは、ソート操作に時間がかかる本当の理由の具体例です。
このタイプの理論には他にもありますが、それは出発点であるべきです。
于 2012-11-28T21:50:04.803 に答える
1
これらのデータ構造は、値を追加または削除するたびに再度並べ替えを行うためです。そのため、それらを使用するとパフォーマンスが低下します。
于 2012-11-28T21:39:12.377 に答える
0
ディクショナリは、単に新しいエントリをリストの最後にスローします。リストの末尾の位置を追跡するだけです。ただし、SortedDictionary は、新しいエントリを配置するために、リスト内の適切な場所を探す必要があります。明らかに、これには計算上の労力が必要であり、単純に最後に追加するよりも遅くなります。
削除の場合、どちらのタイプのオブジェクトも、削除するレコードを探し出す必要がありますが、Sorted タイプは、内部構造に対するそのレコードの削除の影響を評価する必要があります。たとえば、B ツリーは、削除後にブランチのバランスを再調整する必要がある場合があります。これを評価するには、やはりある程度の計算が必要です。したがって、パフォーマンスの違い。
于 2012-11-28T21:46:07.880 に答える