ソートされたディクショナリが必要であることを考慮するのSortedDictionary<>
ではなく、使用するとパフォーマンスが低下するので、ディクショナリを使用した場合は手動でソートする必要があります。Dictionary<>
どちらが速いでしょうか?
SortedDictionary<>
または ( Dictionary<>
+ 手動ソート)。
4 に答える
a への挿入SortedDictionary
は O(log(n)) なので、n 個の項目を挿入すると O(n log(n)) になります。対照的に、a への挿入Dictionary
は O(1) であるため、n 個のアイテムを挿入すると O(n) になりますが、使用する前にアイテムを並べ替える必要があります。これは O(n log(n)) です。それに基づいて、大きな違いはありませんがDictionary
、ハッシュのオーバーヘッドがありますが、SortedDictionary はおそらくリンクされた構造として実装されているため、メモリの局所性が低下する可能性があります。
また、SortedDictionary はキーでソートする必要があるため、使用できるキーの種類に制限を設けますが、Dictionary はハッシュを使用するため制限しません。
実際、どちらが優れているかはアクセス パターンによって異なります。そのため、最善の方法は、ユース ケースで両方のパフォーマンスを測定することです。
パフォーマンス ヒットがあります。http://msdn.microsoft.com/en-us/library/f7fta44c.aspxでコメントを読む
基本的に、SortedDictionary<T>
は二分探索木Dictionary<T>
ですが、 はハッシュ テーブルです。
挿入、削除、ランダム ルックアップDictionary<T>
が高速になります。SortedDictionary
頻繁にリストを作成し、頻繁に変更しないようにすると、より高速になります。Dictionary
頻繁な変更とランダムなルックアップを行い、ソートして出力する必要があまりない場合は、より高速です。
それは、並べ替えられた結果を取得することとは別に辞書にデータを追加するか、一度にすべてを行うかによって異なります。
長時間にわたってデータを追加すると、 を使用して追加するたびにパフォーマンスがわずかに低下しSortedDictionary<>
ますが、最終的に並べ替えられた結果が必要になると、すぐに結果が得られます。これは、たとえばユーザー入力によるアイテムの追加を待つ場合に理想的です。わずかなパフォーマンス ヒットは目立たないためです。
ディクショナリを作成し、それにデータを追加して、ソート結果をすぐに取得する場合Dictionary<T>
、より高速なソート アルゴリズムを使用するため、a の方が高速になります (アイテムが追加されている間、ソート結果を維持する代わりに、一度にすべてをソートできるため)。 .
辞書をどのように使用しているかによって異なります。
- アイテムを多く使用していますか、それともあまり使用していませんか。
- 新しいアイテムを並べ替える必要がある場合と比較して、どのくらいの頻度で新しいアイテムを追加しますか。
- より多くの検索または挿入を行いますか
最善の方法は、両方のアプローチを使用して実際のデータでいくつかのパフォーマンス テストを行い、どちらが状況に適しているかを確認することです。