algorithm - 二分木 vs. リンクリスト vs. ハッシュテーブル

Question

現在取り組んでいるプロジェクトのシンボルテーブルを作成しています。シンボルテーブルの保存と作成に利用できるさまざまな方法の長所と短所について、人々の意見はどうなっているのかと思っていました。

私はかなりの検索を行いましたが、最も一般的に推奨されるのは、バイナリツリー、リンクリスト、またはハッシュテーブルです。上記のすべての利点と欠点は何ですか? (C++ で作業)

score 76 · Accepted Answer

これらのデータ構造間の標準的なトレードオフが適用されます。

二分木
- 実装が中程度の複雑さ (ライブラリから取得できないと仮定)
- 挿入は O(logN) です
- ルックアップは O(logN)
リンクされたリスト (ソートされていない)
- 実装の複雑さが低い
- 挿入は O(1) です
- ルックアップは O(N)
ハッシュテーブル
- 実装が非常に複雑
- 挿入は平均で O(1) です
- ルックアップは平均で O(1) です

score 48 · Accepted Answer

あなたのユースケースは、おそらく「データを1回挿入し（アプリケーションの起動など）、その後、多くの読み取りを実行しますが、余分な挿入があったとしてもほとんどありません」となるでしょう。

したがって、必要な情報を検索するための高速なアルゴリズムを使用する必要があります。

したがって、キーオブジェクトのハッシュを生成し、それを使用してターゲットデータにアクセスするだけなので、HashTable が使用するのに最も適したアルゴリズムであると思います-それは O(1) です。他のものは O(N) (サイズ N のリンクされたリスト - 一度に 1 つずつ、平均 N/2 回リストを反復する必要があります) と O(log N) (二分木 - で検索スペースを半分にします)各反復 - ツリーのバランスが取れている場合のみ。これは実装によって異なります。バランスの取れていないツリーはパフォーマンスが大幅に低下する可能性があります)。

HashTable にデータ用の十分なスペース (バケット) があることを確認してください (Re、この投稿に対する Soraz のコメント)。ほとんどのフレームワークの実装 (Java、.NET など) は、実装について心配する必要がない品質のものです。

大学でデータ構造とアルゴリズムのコースを受講しましたか?

score 43 · Accepted Answer

誰もが忘れているように見えるのは、N が小さい場合、つまりテーブル内のシンボルが少ない場合、連結リストはハッシュテーブルよりもはるかに高速になる可能性があるということですが、理論的にはその漸近的な複雑さは確かに高くなります。

Pike の Notes on Programming in C からの有名な引用があります: 「ルール 3. n が小さい場合、派手なアルゴリズムは遅く、n は通常小さい場合。派手なアルゴリズムには大きな定数があります。n が頻繁に大きくなることがわかるまでは、派手にならないで。」http://www.lysator.liu.se/c/pikestyle.html

あなたの投稿から、小さな N を扱うかどうかはわかりませんが、大きな N に最適なアルゴリズムが小さな N に必ずしも適しているとは限らないことを常に覚えておいてください。

score 8 · Accepted Answer

次のことがすべて当てはまるようです。

キーは文字列です。
挿入は 1 回です。
検索は頻繁に行われます。
キーと値のペアの数は比較的少ない (たとえば、K 程度よりも少ない)。

もしそうなら、これらの他の構造のいずれかの上に並べ替えられたリストを検討するかもしれません。ソートされたリストは挿入時に O(N) であるのに対し、リンクされたリストまたはハッシュテーブルでは O(1) であり、O(log ₂N) バランスの取れた二分木。しかし、ソートされたリスト内のルックアップは、これらの他のどの構造よりも高速である可能性があるため (これについてはすぐに説明します)、トップに立つことができます。また、すべての挿入を一度に実行する場合 (または、すべての挿入が完了するまでルックアップを必要としない場合)、O(1) への挿入を単純化し、最後に 1 つのはるかに迅速な並べ替えを実行できます。さらに、並べ替えられたリストは、これらの他のどの構造よりも少ないメモリを使用しますが、これが問題になる可能性が高い唯一の方法は、小さなリストが多数ある場合です。1 つまたはいくつかの大きなリストがある場合、ハッシュテーブルはソートされたリストよりもパフォーマンスが優れている可能性があります。

並べ替えられたリストを使用すると検索が高速になるのはなぜですか? 後者の O(N) ルックアップ時間により、連結リストよりも高速であることは明らかです。二分木では、木が完全にバランスが取れている場合、ルックアップは O(log _{2 N) のままです。}ツリーのバランスを保つ (たとえば、赤と黒) と、複雑さと挿入時間が長くなります。さらに、リンクされたリストとバイナリツリーの両方で、各要素は個別に割り当てられた¹ ノードです。つまり、ポインターを逆参照し、潜在的に大きく変化するメモリアドレスにジャンプする必要があり、キャッシュミスの可能性が高くなります。

ハッシュテーブルに関しては、おそらく StackOverflow に関する他のいくつかの質問を読む必要がありますが、ここでの主な関心点は次のとおりです。

最悪の場合、ハッシュテーブルは O(N) に縮退する可能性があります。
ハッシュのコストはゼロではなく、一部の実装では、特に文字列の場合、かなりのコストになる可能性があります。
リンクリストやバイナリツリーと同様に、各エントリはキーと値以上のものを格納するノードであり、一部の実装では個別に割り当てられるため、より多くのメモリを使用し、キャッシュミスの可能性が高くなります。

もちろん、これらのデータ構造がどのように機能するかを本当に気にしている場合は、それらをテストする必要があります。ほとんどの一般的な言語で、これらのいずれかの適切な実装を見つけるのに問題はほとんどないはずです。これらのデータ構造のそれぞれに実際のデータの一部を投入し、どれが最もパフォーマンスが良いかを確認することはそれほど難しくありません。

_{実装でノードの配列を事前に割り当てることができます。これは、キャッシュミスの問題を解決するのに役立ちます。リンクリストまたはバイナリツリーの実際の実装でこれを見たことはありません (もちろん、すべてを見たわけではありません)。ただし、ノードオブジェクトは必然的にキーと値のペアよりも大きくなるため、キャッシュミスの可能性はわずかに高くなります。}

score 7 · Accepted Answer

私はビルの答えが好きですが、実際には物事を統合していません.

3つの選択肢から：

リンクされたリストは、(O(n)) からアイテムを検索するのに比較的時間がかかります。したがって、テーブルに多くのアイテムがある場合、または多くのルックアップを行う場合、それらは最良の選択ではありません. ただし、それらは作成が簡単で、書き込みも簡単です。テーブルが小さい場合、および/または作成後に小さなスキャンを 1 回しか実行しない場合は、これが選択される可能性があります。

ハッシュテーブルは非常に高速です。ただし、それが機能するには、入力に適切なハッシュを選択する必要があり、多くのハッシュ衝突なしですべてを保持するのに十分な大きさのテーブルを選択する必要があります。つまり、入力のサイズと量についてある程度知っておく必要があります。これを台無しにすると、リンクされたリストの非常に高価で複雑なセットになってしまいます。テーブルがどのくらいの大きさになるかを事前に知っていない限り、ハッシュテーブルを使用しないでください。これは、「受け入れられた」回答とは異なります。ごめん。

それは木を残します。ただし、ここにはオプションがあります。バランスをとるか、バランスをとらないかです。ここにある C および Fortran コードでこの問題を調査してわかったことは、シンボルテーブルの入力は十分にランダムである傾向があり、ツリーのバランスをとらないことで失われるのはツリーレベルの 1 つか 2 つであるということです。バランスの取れたツリーは要素の挿入が遅く、実装が難しいため、気にしません。ただし、デバッグ済みの優れたコンポーネントライブラリ (例: C++ の STL) に既にアクセスできる場合は、先に進んでバランスツリーを使用することもできます。

score 6 · Accepted Answer

注意すべき点がいくつかあります。

二分木は、ツリーのバランスが取れている場合、O（log n）ルックアップと挿入の複雑さのみを持ちます。シンボルがかなりランダムに挿入されている場合、これは問題にはなりません。それらが順番に挿入されている場合は、リンクリストを作成することになります。（特定のアプリケーションでは、それらはどのような順序でもないはずなので、大丈夫です。）シンボルが整然としすぎる可能性がある場合は、赤黒木がより適切なオプションです。
ハッシュテーブルはO（1）の平均的な挿入とルックアップの複雑さを示しますが、ここにも注意点があります。ハッシュ関数が悪い場合（つまり、本当に悪い場合）、ここでもリンクリストを作成することになります。ただし、適切な文字列ハッシュ関数であれば何でもかまいません。したがって、この警告は、実際には、それが発生する可能性があることを認識していることを確認するためだけのものです。ハッシュ関数が予想される入力範囲で多くの衝突を起こさないことをテストできるはずです。そうすれば問題ありません。もう1つの小さな欠点は、固定サイズのハッシュテーブルを使用している場合です。ほとんどのハッシュテーブルの実装は、特定のサイズに達すると大きくなります（より正確には、負荷率。ここを参照してください）。詳細については）。これは、10個のバケットに100万個のシンボルを挿入するときに発生する問題を回避するためです。これは、平均サイズが100,000の10個のリンクリストにつながります。
本当に短いシンボルテーブルがある場合にのみ、リンクリストを使用します。実装するのが最も簡単ですが、リンクリストのベストケースのパフォーマンスは、他の2つのオプションのワーストケースのパフォーマンスです。

score 1 · Accepted Answer

他のコメントは要素の追加/取得に焦点を当てていますが、この議論は、コレクション全体を反復処理するために何が必要かを考慮せずに完了することはできません。ここでの簡単な答えは、ハッシュテーブルは反復処理に必要なメモリは少なくて済みますが、ツリーは必要な時間が少ないということです。

ハッシュテーブルの場合、（キー、値）ペアを反復処理することによるメモリのオーバーヘッドは、テーブルの容量やテーブルに格納されている要素の数に依存しません。実際、反復には1つまたは2つのインデックス変数のみが必要です。

ツリーの場合、必要なメモリの量は常にツリーのサイズによって異なります。反復中に未訪問ノードのキューを維持するか、反復を容易にするためにツリーにポインターを追加することができます（反復の目的でツリーをリンクリストのように動作させる）が、どちらの場合も、反復のために追加のメモリを割り当てる必要があります。

しかし、タイミングに関しては状況が逆転します。ハッシュテーブルの場合、反復にかかる時間は、格納されている要素の数ではなく、テーブルの容量によって異なります。したがって、容量の10％でロードされたテーブルは、同じ要素を持つリンクリストよりも反復処理に約10倍の時間がかかります。

score 0 · Accepted Answer

もちろん、これはいくつかのことに依存します。シンボルテーブルとして機能する適切なプロパティがほとんどないため、連結リストは適切であると言えます。すでにバイナリツリーがあり、その作成とデバッグに時間を費やす必要がない場合は、バイナリツリーが機能する可能性があります。私の選択はハッシュテーブルです。これは多かれ少なかれ、この目的のデフォルトだと思います。

score 0 · Accepted Answer

この質問は C# のさまざまなコンテナーを対象としていますが、使用するどの言語でも同様です。

score 0 · Accepted Answer

シンボルテーブルが小さいと思われる場合を除き、リンクリストは避けてください。1000 項目のリストは、その中の項目を見つけるのに平均で 500 回の繰り返しが必要です。

二分木は、バランスがとれている限り、はるかに高速になる可能性があります。コンテンツを保持している場合、シリアル化されたフォームはソートされる可能性が高く、再ロードされると、結果として結果のツリーのバランスが完全に崩れ、リンクされたリストと同じように動作します。基本的にどうなったかです。バランスツリーアルゴリズムはこの問題を解決しますが、シバン全体をより複雑にします。

ハッシュマップ (適切なハッシュアルゴリズムを選択する限り) が最適なソリューションのように見えます。あなたの環境については言及していませんが、最近のほぼすべての言語には Hashmap が組み込まれています。

algorithm - 二分木 vs. リンクリスト vs. ハッシュテーブル

10 に答える 10

Related

Reference