7

私は常に基数ツリーのスペース使用法に関心を持っていましたが、これに関する有益な議論は見つかりませんでした。

ここで、linux radix-tree.c と同じ基数ツリーの実装があるとしましょう。これは整数を取り、6 ビットごとに使用してツリー内の次の位置にインデックスを付けます。基数ツリーのスペース使用量が二分探索ツリーよりもはるかに多い場合は簡単に思いつきます。私が間違っている場合は修正してください：

ユースケース: (0,1,1,1,1)、(1,1,1,1,1)、(2,1,1,1,1)、... (63,1,1,1) 、1)。

ここでは便宜上、(a,b,c,d,e) を使用して 30 ビット整数キーを表し、各要素は 6 ビット値を表します。a は MSB、e は LSB です。

基数ツリー:

この使用例では、基数ツリーの高さは 5 で、各キーはルートの異なるサブツリーにあるため、4 つの個別のノードを使用します。したがって、((5-1) * 64 + 1) = 257 ノードになります。

各ノードには 2^6 = 64 個のポインターが含まれているため、257 * 64 * 4Byte = 65KB を使用します。

二分探索木

キーの数だけが重要です。この場合、64 個のキーがあります。

各 BST ノードがノードごとに 3 つのポインターを使用すると仮定すると、64 * 3 * 4 バイト = 768 バイトを使用することになります。

比較

基数ツリーは非常にスペース効率が悪いようです。同じ数のノードが与えられた場合、二分探索木よりも ~100 倍の空間を使用します! なぜLinuxカーネルでも使われるのか理解できません。

何か不足していますか？ありがとう。

4

3 に答える 3

8

あなたはスペースの複雑さを求めたので、それを解決しましょう。

リーフの null 以外のポインターを対象の値と見なす場合、矛盾によって、最悪のケースがリーフ ノードごとに 1 つの値を持つ完全に入力されたツリーであることを証明することは難しくありません。

分岐が N 方向 (ユース ケース 64) で高さが H (ユース ケース 5) の場合、このツリーには N^(H-1) 個のリーフ ノードがあり、同じ数の値が格納されます。ノードの総数は

1 + N + N^2 + ... N^(H-1) = (N^H - 1) / (N-1)

したがって、ポインターで測定されるストレージ要件は、この量の N 倍になります。

(N^H - 1)  [N / (N-1)]

これにより、次のストレージ効率が得られます。

(N^H - 1)  [N / (N-1)]  
--------------------
       N^(H-1)

これは、ポインタの総数を有効なデータ ポインタの数で割ったものです。

N が大きくなるにつれて、これは N に近づきます。ユース ケースの例では、実際には 65.01 (N=64 の場合) です。したがって、ストレージの複雑さは O(NV) であると言えます。ここで、V は格納されるデータ値の数です。

第一原理分析でここまでたどり着きましたが、それは完全に理にかなっています。完全なツリーのリーフ レベルのストレージは、ほぼ N の係数で残りを支配します。そのストレージのサイズは NV です。

もちろん、このような巨大な分岐因子を持つツリー (およびデータベースの B ツリーなど) の利点は、正しいリーフに到達するために必要なノードのトラバーサルが少ないことです。

さらに、各トラバーサルが基数ツリーのように単一の配列ルックアップである場合、それほど高速になることはありません。

あなたのユースケースでは、完全にバランスの取れた二分探索木には、パイプラインをフラッシュする付随するブランチとの最大 30 回の比較が必要です。これは、5 つの配列インデックス操作と比較すると、はるかに遅くなる可能性があります。配列のインデックス付けは、非分岐コードであるため、比較よりも高速になる傾向があります。しかし、それらが同じであっても、2^30 要素を含む基数ツリーと同じ量のインデックス作成作業を引き起こすために、バイナリ ツリーは 2^5=32 要素しか必要としません。

これを一般化すると、キー比較と配列インデックス操作のコストが同じ場合、2^H 要素のバイナリ ツリーは、N^(H-1) 要素を保持できるインデックス ツリーと同じルックアップ作業が必要になります。

他の人が言ったように、ツリーの最上位レベルのインデックス ビットがいくつかの一般的なプレフィックスの傾向がある場合 (つまり、同じ VM 空間のアドレスの最上位ビットである場合)、基数ツリーの最悪の場合の格納動作は発生しません。 .

于 2013-12-17T21:20:57.373 に答える
0

基数ツリーは、共通/共有プレフィックスを持つ長い文字列を保持するために多く使用されます。この場合、基数ツリーの方がはるかに経済的です。

指定している種類のデータについては、別の話です。

編集

プレフィックス付きの長い文字列の良い例は、すべてのファイル名をフル パスと共にコンピューターに保存することです。このようなデータを使用すると、他の方法よりも経済的で、ファイル名が存在するかどうかを非常に高速に見つけることができます。場合によっては、ハッシュ テーブルよりも高速になることもあります。

次の 2 つのファイルを見てください。

  • "c:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\streambuf"
  • "c:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\string"

それらの共有プレフィックスは「c:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\include\str」で、一度だけ保存されます。

于 2013-12-13T19:33:15.453 に答える