週刊 spaghetti_source

Trie for Fixed Universe Set

19:14

要素の追加・削除・存在判定に答えるためのデータ構造として平衡二分探索木がありますが，与えられるものが有限集合：{0, ..., 2^M-1 (=U)} の元である，という情報がある場合はより高速なデータ構造が設計できます．この手の問題は Fixed Universe Problem などと呼ばれています．

この手の問題の最も基本的な方針は，数字の上位ビットと下位ビットに分けて，上位ビットをキーとする再帰構造に下位ビットを突っ込む，というものです．van Emde Boas木として知られている構造はMビットユニバースに対する上位ビットサイズを H(M) = M/2 に選んだデータ構造で，木の深さが log(M) = log log(U) となります．ところが，vEB木はその計算量インパクトと比べてほとんど実用はされていません．これはvEBの計算量ゲイン：log(U) vs loglog(U) が効いてくるには十分大きなユニバースでないといけないのに対し，そのような大きなデータの処理では，データアクセスのオーバーヘッド（ファイルの読み出し等）が支配的になってしまい，もっと単純でデータ配置に即したB木などの構造のほうがトータルで早くなるからだと思っています（see: 参考文献）．

※vEB拡張系（＝log log U系）で実測すると結構早い，というのもどこかで聞いた気はしますが，忘れてしまいました．実用しているという話は聞かないので，多分そういうことだと思います．

...

ここでは最もシンプルな fixed universe problem の実装として，上位ビットを固定で H ビットとする構造の実装を示します．これは数を H ビットごとで切った文字列と見たときの Trie です．

切るビット数 H の設定ですが，子が全部で 2^H 子あり，どの子が居るか居ないかの状態が 2^2^H 状態あるので，2^2^H = 2^31 から H = 7 程度にします．このようにすると，たとえば「自分の子の中で空でない最小の子」とかがビット演算によって非常に高速に求まります（＝最小値探索・successor探索なども高速）．このときの木の深さは 31/7 < 5 より，深さ高々 5 が従います．これは 2^31 に対するvEB木と同じ深さ： log(32) = 5 なので，この範囲では完全に有利になっています．

実測

普通の平衡二分探索木（std::set）と insert/remove/find の比較を行います．1,000,000個の乱数をランダムに挿入・削除・検索する，という試行を10回行ったときの合計時間を見ています（※削除・検索が自明にならないように，乱数範囲は適当に設定）．この結果から，insertは19倍，removeは4倍，findは9倍ほど早くなっていることがわかります．

name	insert	remove	find
trie	0.129	0.099	0.136
std::set	2.426	0.398	1.279

実装例

const int B = 7;
const int MAXBIT = 32;
struct IntegralTree {
  struct Node {
    Node *child[(1<<B)];
    int S;
    Node() : S(0) { fill(child, child+(1<<B), (Node*)0); }
  } root;
  void insert(Node *n, int x, int R) {
    int h = (x >> (R-B)) & ((1 << B)-1);
    n->S |= (1 << h);
    if (R > B) {
      if (!n->child[h]) n->child[h] = new Node;
      insert(n->child[h], x, R-B);
    }
  }
  void remove(Node *n, int x, int R) {
    int h = (x >> (R-B)) & ((1 << B)-1);
    if (!(n->S & (1 << h))) return;
    bool cond = true;
    if (R > B) {
      remove(n->child[h], x, R-B);
      if (n->child[h]->S != 0) cond = false;
    }
    if (cond) n->S &= ~(1 << h);
  }
  bool find(Node *n, int x, int R) {
    int h = (x >> (R-B)) & ((1 << B)-1);
    if (!(n->S & (1 << h))) return false;
    if (R > B) return find(n->child[h], x, R-B);
    else       return true;
  }
  void insert(int x) { insert(&root, x, MAXBIT); }
  void remove(int x) { remove(&root, x, MAXBIT); }
  bool find(int x) { return find(&root, x, MAXBIT); } 
};

参考文献

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2009): "Introduction to Algorithms", The MIT Press; 3rd ed.
• P. Patel and D. Garg (2012): Comparison of Advance Tree Data Structures, International Journal on Computer Applications, vol.41, no.2.
• J. Levandoski, D. Lomet, and S. Sengupta (2013): "The Bw-Tree: A B-tree for New Hardware", In: 2013 IEEE 29th International Conference on Data Engineering (ICDE).