0

ソートされたディクショナリが必要であることを考慮するのSortedDictionary<>ではなく、使用するとパフォーマンスが低下するので、ディクショナリを使用した場合は手動でソートする必要があります。Dictionary<>どちらが速いでしょうか？ SortedDictionary<>または ( Dictionary<>+ 手動ソート)。

4

4 に答える 4

3

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 はハッシュを使用するため制限しません。

実際、どちらが優れているかはアクセス パターンによって異なります。そのため、最善の方法は、ユース ケースで両方のパフォーマンスを測定することです。

于 2013-02-28T21:14:11.443 に答える
1

パフォーマンス ヒットがあります。http://msdn.microsoft.com/en-us/library/f7fta44c.aspxでコメントを読む

基本的に、SortedDictionary<T>は二分探索木Dictionary<T>ですが、 はハッシュ テーブルです。

挿入、削除、ランダム ルックアップDictionary<T>が高速になります。SortedDictionary頻繁にリストを作成し、頻繁に変更しないようにすると、より高速になります。Dictionary頻繁な変更とランダムなルックアップを行い、ソートして出力する必要があまりない場合は、より高速です。

于 2013-02-28T21:11:12.130 に答える
1

それは、並べ替えられた結果を取得することとは別に辞書にデータを追加するか、一度にすべてを行うかによって異なります。

長時間にわたってデータを追加すると、 を使用して追加するたびにパフォーマンスがわずかに低下しSortedDictionary<>ますが、最終的に並べ替えられた結果が必要になると、すぐに結果が得られます。これは、たとえばユーザー入力によるアイテムの追加を待つ場合に理想的です。わずかなパフォーマンス ヒットは目立たないためです。

ディクショナリを作成し、それにデータを追加して、ソート結果をすぐに取得する場合Dictionary<T>、より高速なソート アルゴリズムを使用するため、a の方が高速になります (アイテムが追加されている間、ソート結果を維持する代わりに、一度にすべてをソートできるため)。 .

于 2013-02-28T21:20:34.063 に答える
1

辞書をどのように使用しているかによって異なります。

  • アイテムを多く使用していますか、それともあまり使用していませんか。
  • 新しいアイテムを並べ替える必要がある場合と比較して、どのくらいの頻度で新しいアイテムを追加しますか。
  • より多くの検索または挿入を行いますか

最善の方法は、両方のアプローチを使用して実際のデータでいくつかのパフォーマンス テストを行い、どちらが状況に適しているかを確認することです。

于 2013-02-28T21:13:33.393 に答える