はじめに
Introduction to Algorithms に載ってる、wikipedia:en:Van_Emde_Boas_tree の記事がある、日本語のslideshare Nazoki がある、のでそこそこ知名度があるvan Emde Boas Trees (vEB)。私の中での解釈はbit vectorを平方分割し、next / prevを付けたデータ構造。
赤黒木 (std::set) | vEB | bit vector (std::bitset) | |
---|---|---|---|
find | O(log n) | O(log log u) | O(1) |
insert | O(log n) | O(log log u) | O(1) |
erase | O(log n) | O(log log u) | O(1) |
next, prev | O(log n), 平均O(1) | O(log log u) | O(u) |
min, max | O(1) | O(1) | O(u) |
メモリ | O(n) | O(u) | O(u) |
vEBとbit vectorは非負整数しかkeyにできない。ここでnは要素数。uはkeyの最大値。整数であるのでO(1)でbit演算も配列の参照もできる、すごい。
setのprevはイテレータ操作が必要でO(log n)保証されてないかもしれないけど普通の実装ならそうでしょう。
目的
n個の非負整数a[0] .. a[n-1] (n <= 1e6, 0 <= a[i] <= 1e6) またはそれ以下のサイズについて、集合の操作 find / insert / erase / next / prev / min / max がstd::setより高速なデータ構造。ついでにemptyとclearができる。
使い方
- コンストラクタにn <= 2^24の値をあげると0~n-1の整数の集合として扱う
- 初期値は空
- sizeやコピーコンストラクタ、デストラクタは無い
- next / prev / min / max は値が存在しない場合はINVALID (= 2^32 - 1) を返す
- insert / eraseは要素の有無が変更された場合trueを返す
- keyはunsignedなのでnext(-1)などやってはならない
- clearしたら解放し、もう使うことはできない
int main() { VEB veb(100); veb.insert(3); veb.insert(5); veb.insert(8); veb.insert(13); if (!veb.empty()) puts("not empty"); if (veb.find(3)) puts("I have 3."); if (veb.next(4) != veb.INVALID) printf("next(4) is %u\n", veb.next(4)); if (veb.next(5) != veb.INVALID) printf("next(5) is %u\n", veb.next(5)); if (veb.prev(4) != veb.INVALID) printf("prev(4) is %u\n", veb.prev(4)); if (veb.prev(3) == veb.INVALID) printf("prev(3) is INVALID (%u)\n", veb.prev(3)); veb.erase(3); puts("erase(3)"); if (veb.min() != veb.INVALID && veb.max() != veb.INVALID) printf("min %u, max %u\n\n", veb.min(), veb.max()); unsigned u = veb.min(); while (u != veb.INVALID) { printf("I have %u\n", u); u = veb.next(u); } veb.clear(); return 0; }
出力
not empty I have 3. next(4) is 5 next(5) is 8 prev(4) is 3 prev(3) is INVALID (4294967295) erase(3) min 5, max 13 I have 5 I have 8 I have 13
実装
wikipediaの資料から辿って読み漁った。
目的を達成するためには、過度な一般化は控えるべき。オリジナルのvEBでは葉が2要素のvEBでその上が4, 16, 256, … だと思う。メモリを節約するために葉を64要素のbit vector実装のvEBとし、その上は4096、16777216。1e7を超えた使いやすいサイズに成るのも嬉しい。
vEBはwikipediaではHeapに分類されている通り、部分木のminの値はノードに保存され、それ以外の値は子が保存する。とにかくこの条件だけ満たすようにinsert / erase を実装する。wikipediaの擬似コードを写すとあまり良くないかも。
余分な値を持たせたくなかったので、高さごとにそれぞれclassを定義する。
vEBはkeyを保存する位置がほぼ固定で、回転もなく、実装は赤黒木に比べかなり易しい印象。
コードはココにある VEB.cpp · GitHub
終わりに
vEBを実装した。コンストラクタ以外はstd::setよりは高速。1e7程度の非負整数しか扱えないのでsetの代替にはできないが、ありうる問題設定だと思う。ただし多くの場合はstd::setで十分TLEに間に合うだろうが。
今回の実装は拡張が不可能。mapにすることもbagにすることもできない。
ノードを必要になるまで作らなければU = 2^64のvEBを作ることもできるがn = 1e6ではsetのほうがかなり速い。またメモリ制限のため配列は使えずHashMapを使う必要があり、問題によってHashMapを使用してよいかどうかの考察・覚悟が必要になる。適していない。