algorithm - 連想 - 連結リスト 特徴



バイナリツリー対リンクリスト対ハッシュテーブル (7)

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

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

https://src-bin.com


Answer #1

この質問は、C#のさまざまなコンテナを通っていますが、使用する言語に似ています。


Answer #2

あなたのシンボルテーブルが小さくなることを期待しない限り、私はリンクされたリストを明確にするべきです。 1000個のアイテムのリストは、その中のアイテムを見つけるために平均して500回の反復を行います。

バイナリツリーは、バランスが取れている限り、はるかに高速になります。 内容を保持している場合は、シリアライズされたフォームがソートされてしまい、再読み込み時にツリーの結果が完全にアンバランスになり、リンクされたリストと同じように動作します。基本的にはそれが何になったのか。 バランスの取れたツリーアルゴリズムはこの問題を解決しますが、シバン全体をより複雑にします。

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


Answer #3

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

  • バイナリツリー
    • (あなたがライブラリからそれらを得ることができないと仮定して)
    • 挿入はO(logN)
    • ルックアップはO(logN)
  • リンクされたリスト(ソートされていない)
    • 実装する複雑さが低い
    • 挿入物はO(1)
    • ルックアップはO(N)
  • ハッシュテーブル
    • 実装するための複雑さ
    • 挿入物は平均でO(1)である
    • ルックアップは平均でO(1)です

Answer #4

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


Answer #5

次のようなことが起こるかもしれません。

  • あなたの鍵は文字列です。
  • 挿入は一度行われます。
  • ルックアップは頻繁に行われます。
  • キーと値のペアの数は比較的少ない(たとえば、K程度かそれ以下)。

そうであれば、これらの他の構造のいずれかにソートされたリストを考えるかもしれません。 ソートされたリストは、挿入時にはO(N)、リンクされたリストまたはハッシュテーブルではO(1)、平衡二分木ではO(log 2 N)であるため、挿入時に他のものよりも悪くなります。 しかし、ソートされたリストのルックアップは、他の構造より速いかもしれません(私はこれを少し説明します)。 また、すべての挿入を一度に実行する(または、すべての挿入が完了するまでルックアップを必要としない)場合は、O(1)への挿入を簡略化して、最後にすばやくソートすることができます。 さらに、ソートされたリストはこれらの他の構造よりも少ないメモリしか使用しませんが、これが重要な唯一の方法は小さなリストが多数ある場合です。 1つまたは2つの大きなリストがある場合、ハッシュテーブルはソートされたリストを外れてしまう可能性があります。

ソートされたリストでルックアップが高速になるのはなぜですか? さて、リンクされたリストよりも早く、後者のO(N)ルックアップ時間があることは明らかです。 バイナリツリーでは、ツリーが完全に均衡したままであれば、ルックアップはO(log 2 N)のままです。 ツリーをバランスのとれた状態に保つと(例えば、赤黒)、複雑さと挿入時間が増えます。 さらに、リンクリストとバイナリツリーの両方で、各要素は別々に割り当てられた1つの ノードです。つまり、ポインタを逆参照する必要があり、潜在的に幅広く変化するメモリアドレスにジャンプし、キャッシュミスの可能性を高めます。

ハッシュテーブルに関しては、ここでで他に いくつか の質問を読むべきでしょうが、ここでの重要なポイントは次のとおりです。

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

もちろん、これらのデータ構造がどのように実行されるかを実際に気にしている場合は、それらをテストする必要があります。 ほとんどの一般的な言語でこれらのいずれかの良い実装を見つけることはほとんど問題にならないはずです。 これらのデータ構造のそれぞれに実際のデータの一部を投げて、どれが最も優れているかを確認することはあまり難しいことではありません。

  1. 実装では、ノードの配列を事前に割り当てることができます。これは、キャッシュミスの問題に役立ちます。 私はリンクリストやバイナリツリーの実際の実装ではこれを見たことがありません。 ただし、 ノードオブジェクトは必ずキーと値のペアよりも大きいため、キャッシュミスの可能性はやや高いです。

Answer #6

気をつけるべきことのカップル。

  • バイナリツリーは、ツリーが均衡している場合にのみ、O(log n)ルックアップを持ち、複雑さを挿入します。 あなたのシンボルがかなりランダムな方法で挿入されている場合、これは問題ではありません。 それらが順番に挿入されている場合は、リンクされたリストを作成します。 (あなたの特定のアプリケーションのために、彼らはどんな順序でもすべきではないので、あなたは大丈夫です。)シンボルがあまりにも規則正しくなる可能性がある場合は、 Red-Blackツリーが良い選択肢です。

  • ハッシュテーブルはO(1)の平均挿入と検索の複雑さを与えますが、ここでも注意が必要です。 あなたのハッシュ関数が悪い(と私は本当に悪いことを意味する)場合は、ここでもリンクリストを構築することができます。 ただし、合理的な文字列ハッシュ関数を使用する必要があります。この警告は実際には起こり得ることを認識していることを確認するためのものです。 あなたは、あなたのハッシュ関数が予想される入力範囲に多くの衝突を持たないことをテストするだけで十分です。 もう1つの小さな欠点は、固定サイズのハッシュテーブルを使用している場合です。 ほとんどのハッシュテーブルの実装は、特定のサイズに達すると大きくなります(詳細については、負荷係数を参照hereてください)。 これは、10個のバケットに100万個のシンボルを挿入するときに発生する問題を回避するためです。 それは10個のリンクされたリストにつながり、平均サイズは100,000です。

  • 私は本当に短いシンボルテーブルを持っている場合、私はリンクリストを使用します。 実装が最も簡単ですが、リンクされたリストの最高のパフォーマンスは、他の2つのオプションの最悪の場合のパフォーマンスです。


Answer #7

誰もが忘れているように見えるのは、小さなNs、IEのいくつかのシンボルがあなたのテーブルにあり、リンクリストはハッシュテーブルよりもはるかに高速ですが、理論的には漸近的な複雑さは確かに高いです。

パイクのCのプログラミングに関するノートから有名なqouteがあります: "ルール3:ファンシーアルゴリズムは、nが小さいときには遅く、通常はnが小さいときにはかなり大きいアルゴリズムです。ファンシーにならないでください」 http://www.lysator.liu.se/c/pikestyle.html

小さなNを扱うかどうかはあなたのポストからは分かりませんが、大きなNのための最良のアルゴリズムは必ずしも小さなNに対しては必ずしも良いとは限りません。





symbol-tables