26

ハッシュテーブルとソートされたリストのどちらでアイテムを見つけるのが速いですか?

4

7 に答える 7

32

アルゴリズムの複雑さは知っておくと良いことであり、ハッシュテーブルはO(1)であることが知られていますが、ソートされたベクトル (あなたの場合、リストよりもソートされた配列を使用する方が良いと思います) はO(log n)アクセス時間を提供します.

しかし、複雑さの表記法は、N が無限になるまでのアクセス時間を提供することを知っておく必要があります。つまり、データが成長し続けることがわかっている場合、複雑さの表記は、選択するアルゴリズムに関するヒントを提供します。

データの長さがかなり短いことがわかっている場合: たとえば、配列/ハッシュテーブルに少数のエントリしかない場合は、監視と測定を行う必要があります。だからテストをしてください。

たとえば、別の問題: 配列の並べ替え。いくつかのエントリでは、O(N^2) はO(n log n)ですが、O(N^2)はクイック ソートよりも速いかもしれません。

また、他の回答に応じて、アイテムに応じて、ハッシュテーブルインスタンスに最適なハッシュ関数を見つけようとする必要があります。そうしないと、ハッシュテーブルでのルックアップのパフォーマンスが大幅に低下する可能性があります（ハンクゲイの回答で指摘されているように）。

編集: Big O表記の意味を理解するには、この記事をご覧ください。

于 2009-05-18T09:54:53.057 に答える
14

「ソートされたリスト」とは、「ランダムアクセス可能なソートされたコレクション」を意味すると仮定します。リストには、要素ごとにのみトラバースできるというプロパティがあり、その結果、O(N) の複雑さが生じます。

並べ替えられたインデックス可能なコレクション内の要素を見つける最速の方法は、N-ary 検索 O(logN) によるものですが、衝突のないハッシュテーブルの検索の複雑さは O(1) です。

于 2009-05-18T09:49:51.523 に答える
7

ハッシュ アルゴリズムが非常に遅い (および/または悪い) 場合を除き、ハッシュテーブルは高速になります。

更新: コメンターが指摘したように、ハッシュ アルゴリズムが悪いためではなく、単にハッシュ テーブルが十分に大きくないために、衝突が多すぎるためにパフォーマンスが低下する可能性もあります。ほとんどのライブラリの実装 (少なくとも高水準言語では) は、ハッシュテーブルを舞台裏で自動的に拡張します。これにより、拡張をトリガーする挿入で予想よりもパフォーマンスが低下しますが、独自にローリングしている場合、それは間違いなく何かです。考慮する。

于 2009-05-18T09:49:43.020 に答える
5

でのget操作はSortedListですがO(log n)、HashTable での同じ操作はO(1)です。したがって、通常は のHashTable方がはるかに高速です。ただし、これは多くの要因に依存します。

  • リストのサイズ
  • ハッシュ アルゴリズムのパフォーマンス
  • ハッシュ アルゴリズムの衝突数 /品質
于 2009-05-18T09:57:37.823 に答える
3

それは、保存したデータの量に完全に依存します。

投入するのに十分なメモリがある (ハッシュ テーブルが十分に大きい) と仮定すると、ハッシュ テーブルは一定の時間内にターゲット データを見つけますが、ハッシュを計算する必要があるため、いくらかの (これも固定の) オーバーヘッドが追加されます。

並べ替えられたリストを検索すると、ハッシュのオーバーヘッドは発生しませんが、リストが大きくなるにつれて、ターゲット データを実際に見つける作業に必要な時間が長くなります。

したがって、一般に、並べ替えられたリストは、小さなデータ セットの場合に高速になります。(頻繁に変更されたり検索されることの少ない非常に小さなデータ セットの場合、並べ替えを行うオーバーヘッドを回避できるため、並べ替えられていないリストの方が高速になる場合があります。) データ セットが大きくなるにつれて、リストの検索時間は長くなります。ハッシュの固定オーバーヘッドを覆い隠し、ハッシュ テーブルが高速になります。

そのブレークポイントの場所は、特定のハッシュ テーブルとソート リスト検索の実装によって異なります。通常サイズの多数のデータ セットでテストとベンチマーク パフォーマンスを実行して、特定のケースで実際にどれがより優れたパフォーマンスを発揮するかを確認します。(または、コードが既に「十分に速く」実行されている場合は、実行しないでください。最適化する必要のないものを最適化することを心配する必要はなく、より使いやすい方を使用してください。)

于 2009-05-18T10:13:12.723 に答える
1

場合によっては、コレクションのサイズに依存します (程度は低いですが、実装の詳細)。リストが非常に小さく、おそらく 5 ～ 10 個のアイテムである場合、リストの方が高速になると思います。それ以外の場合は、xtofl が適切です。

于 2009-05-18T09:53:56.273 に答える
1

HashTable は、10 個を超えるアイテムを含むリストの場合により効率的です。リストのアイテム数が 10 未満の場合、ハッシュ アルゴリズムによるオーバーヘッドはさらに大きくなります。

In case you need a fast dictionary but also need to keep the items in an ordered fashion use the OrderedDictionary. (.Net 2.0 onwards)

于 2009-05-18T09:57:22.833 に答える