16

二分探索木をいつ使用するか、いつ辞書を使用するかという概念に苦労しています。

私のアプリケーションでは、C5ライブラリTreeDictionary（赤黒木であると私は信じています）とC＃辞書を使用した小さな実験を行いました。辞書は、追加/検索操作で常に高速であり、また、常により少ないメモリスペースを使用していました。たとえば、16809<int, float>エントリでは、ディクショナリは342 KiBを使用し、ツリーは723KiBを使用しました。

BSTの方がメモリ効率が高いと思いましたが、ツリーの1つのノードには、辞書の1つのエントリよりも多くのバイトが必要なようです。何が得られますか？BSTが辞書よりも優れている点はありますか？

また、副次的な質問として、<int, float>辞書タイプのアクセス用のペアを格納するための、前述の構造のいずれよりも高速でメモリ効率の高いデータ構造があるかどうかを誰かが知っていますか？

4

6 に答える 6

8

BSTの方がメモリ効率が高いと思いましたが、ツリーの1つのノードには、辞書の1つのエントリよりも多くのバイトが必要なようです。何が得られますか？BSTが辞書よりも優れている点はありますか？

私は個人的にそのような原則について聞いたことがありません。それでもなお、それは唯一の一般的な原則であり、宇宙の構造に刻まれた明確な事実ではありません。

一般に、辞書は実際にはリンクリストの配列の単なる派手なラッパーです。次のようなものを辞書に挿入します。

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

したがって、ほぼO（1）の操作です。ディクショナリはO（internalArray.Length + n）メモリを使用します。ここで、nはコレクション内のアイテムの数です。

一般に、BSTは次のように実装できます。

  • リンクリスト。O（n）スペースを使用します。ここで、nはコレクション内のアイテムの数です。
  • 配列。O（2h --n）スペースを使用します。ここで、hはツリーの高さ、nはコレクション内のアイテムの数です。
    • 赤黒木はO（1.44 * n）の制限された高さを持っているので、配列の実装は約O（2 1.44n --n）の制限されたメモリ使用量を持つ必要があります

奇妙なことに、C5 TreeDictionaryは配列を使用して実装されており、おそらく無駄なスペースの原因となっています。

何が得られますか？BSTが辞書よりも優れている点はありますか？

辞書にはいくつかの望ましくない特性があります。

  • 使用可能なRAMの合計よりもメモリ要件がはるかに少ない場合でも、辞書を保持するのに十分な連続したメモリブロックがない場合があります。

  • ハッシュ関数の評価には、任意の長い時間がかかる場合があります。たとえば、文字列はReflectorを使用してSystem.String.GetHashCodeメソッドを調べます。文字列のハッシュには、常にO（n）時間がかかります。つまり、非常に長い文字列の場合はかなりの時間がかかる可能性があります。一方、文字列の不等式の比較は、最初の数文字だけを調べる必要がある場合があるため、ほとんどの場合、ハッシュよりも高速です。ハッシュコードの評価に時間がかかりすぎる場合は、ツリーの挿入が辞書の挿入よりも高速になる可能性があります。

    • Int32のGetHashCodeメソッドは文字通りただreturn thisのことなので、intキーを持つハッシュテーブルがツリーディクショナリよりも遅い場合を見つけるのは難しいでしょう。

RBツリーにはいくつかの望ましい特性があります。

  • 辞書を使用したO（n）時間と比較して、O（log n）時間で最小要素と最大要素を検索/削除できます。

  • ツリーが配列ではなくリンクリストとして実装されている場合、ツリーは通常、辞書よりもスペース効率が高くなります。

  • 同様に、O（log n）時間での挿入/ルックアップ/削除をサポートする不変バージョンのツリーを作成するのはばかげています。すべての操作で内部配列全体をコピーする必要があるため、辞書は不変性にうまく適応しません（実際、汎用辞書データ構造の一種である不変のフィンガーツリーの配列ベースの実装を見てきましたが、実装は非常に繁雑）。

  • ツリー内のすべての要素を一定のスペースとO（n）時間で並べ替えられた順序でトラバースできますが、同じ効果を得るには、ハッシュテーブルを配列にダンプして並べ替える必要があります。

したがって、データ構造の選択は、実際には必要なプロパティによって異なります。順序付けされていないバッグが必要で、ハッシュ関数が迅速に評価されることを保証できる場合は、.Netディクショナリを使用してください。注文したバッグが必要な場合、または実行速度の遅いハッシュ関数がある場合は、TreeDictionaryを使用してください。

于 2010-01-28T03:16:38.757 に答える
2

ツリーノードがディクショナリエントリよりも多くのストレージを必要とすることは理にかなっています。二分木ノードは、値と左右両方のサブツリーを格納する必要があります。ジェネリックDictionary<TKey, TValue>はハッシュテーブルとして実装されます。これは、バケットごとにリンクリスト（値と1つのポインター/参照）を使用するか、ある種の再マッピング（値のみ）を使用します。確かにReflectorを覗いてみる必要がありますが、この質問の目的上、それはそれほど重要ではないと思います。

ハッシュテーブルがまばらであるほど、ストレージ/メモリの点で効率が低下します。ハッシュテーブル（ディクショナリ）を作成し、その容量を100万に初期化し、10,000個の要素のみで埋めると、10,000ノードのBSTよりもはるかに多くのメモリを消費すると確信しています。

それでも、ノード/キーの数が数千にすぎない場合は、これについて心配する必要はありません。これは、ギガバイトの物理RAMと比較して、キロバイト単位で測定されます。

質問が「なぜハッシュテーブルの代わりにバイナリツリーを使用したいのですか？」である場合。次に、IMOの最良の答えは、バイナリツリーは順序付けられていますが、ハッシュテーブルは順序付けられていないということです。ハッシュテーブルで検索できるのは、何かとまったく同じキーのみです。ツリーを使用すると、値の範囲、最も近い値などを検索できます。これは、インデックスなどを作成する場合に非常に重要な違いです。

于 2010-01-28T02:39:23.760 に答える
0

あなたは時期尚早の最適化をしているように私には思えます。

私があなたに提案したいのは、実際に使用している構造を分離するためのインターフェースを作成し、次に辞書を使用してインターフェースを実装することです（これは最もうまくいくようです）。

メモリ/パフォーマンスが問題になる場合（おそらく20kの数値では問題になりません）、他のインターフェイス実装を作成して、どれが最適に機能するかを確認できます。コードの残りの部分（使用している実装を除く）では、ほとんど何も変更する必要はありません。

于 2010-01-28T02:26:17.380 に答える
0

ツリーとハッシュテーブルのインターフェイス（これは、ディクショナリのベースになっていると思います）は非常に似ているはずです。キー付きルックアップを常に中心に展開します。

私はいつも、辞書は物事を一度作成してからそれに対して多くのルックアップを行うのに適していると思っていました。ツリーを大幅に変更する場合は、ツリーの方が優れていました。しかし、どこからそのアイデアを思いついたのかわかりません。

（関数型言語では、ツリーに小さな変更を加えるとほとんどのツリーを再利用できるため、コレクションのベースとしてツリーを使用することがよくあります）。

于 2010-01-28T02:40:16.677 に答える
0

「りんごとりんご」を比較しているのではなく、BSTは順序付けられた表現を提供し、辞書を使用するとキーと値のペア（この場合）を検索できます。

2つの間のメモリフットプリントのサイズはそれほど大きくないと思いますが、辞書を使用すると、はるかに高速な検索が可能になります。BSTでアイテムを見つけるには、（潜在的に）ツリー全体をトラバースする必要があります。ただし、ディクショナリルックアップを実行するには、キーに基づいてルックアップするだけです。

于 2010-01-28T03:05:18.783 に答える
0

レイテンシスパイクやハッシュ衝突攻撃からデータ構造を保護する必要がある場合は、バランスの取れたBSTが推奨されます。

前者は、配列に裏打ちされた構造が大きくなり、サイズが変更されたときに発生します。後者は、無限空間から限られた整数範囲への射影としてのハッシュアルゴリズムの必然的な特性です。

.NETのもう1つの問題は、LOHがあり、十分に大きな辞書を使用すると、LOHの断片化に遭遇することです。この場合、BSTを使用して、より大きなアルゴリズムの複雑さのクラスの代償を払うことができます。

つまり、割り当てヒープに裏打ちされたBSTを使用すると、最悪の場合のO（log（N））時間が得られ、ハッシュテーブルを使用すると、最悪の場合のO（N）時間が得られます。

BSTは、平均時間O（log（N））、キャッシュの局所性の低下、ヒープ割り当ての増加という代償を伴いますが、遅延が保証されており、辞書攻撃やメモリの断片化から保護されています。

BSTは、圧縮ガベージコレクターを使用せずに、他のプラットフォームでもメモリの断片化の影響を受けることに注意してください。

メモリサイズに関しては、.NET Dictionary`2クラスは、値とオフセット情報のみを格納するオフヒープリンクリストとしてデータを格納するため、メモリ効率が高くなります。BSTは、オブジェクトヘッダー（各ノードはヒープ上のクラスインスタンスであるため）、2つのポインター、およびバランスの取れたツリー用の拡張ツリーデータを格納する必要があります。たとえば、赤黒木には、色（赤または黒）として解釈されるブール値が必要です。私が間違っていなければ、これは少なくとも6つのマシンワードです。したがって、64ビットシステムの赤黒木にある各ノードは、最小で次のようになります。

ヘッダーの3ワード=24バイト子ポインターの2ワード=16バイト色の1ワード=8バイト値の少なくとも1ワード8+バイト=24+ 16 + 8 + 8 = 56バイト（+8バイトツリーが親ノードポインタを使用している場合）。

同時に、辞書エントリの最小サイズはわずか16バイトになります。

于 2018-12-10T13:18:03.953 に答える