van Emde Boas Trees を実装する

はじめに

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を使用してよいかどうかの考察・覚悟が必要になる。適していない。

両端優先度付きキューのInterval-Heap実装

ヒープ / Double-Ended Priority Queue

優先度付きキュー、使い勝手が良くヒープ実装も簡単でデータ構造の入門書に書いて有ることも多いと思う。実装したのは勉強しだした最初の頃の1回だけな気がするので復習のために実装する。
G++のstd::priority_queueはmaxを取ることのできるヒープ構造であるが、今回の実装ではmax/minのどちらでもget/popのできる「両端優先度付きキュー」 wikipedia:en:Double-ended_priority_queue を実装したい。
実装はinterval heap が実装量・実行時間・メモリすべて良さそう。
stdにあるヒープは

  • make_heap(first, last): 引数のvectorなどをヒープ構造に成るように並び替える。特に先頭を優先度最大の要素にする。
  • push_heap(first, last): [first, last-1) がヒープのときに、末端の要素をpushして[first, last)をヒープにする。
  • pop_heap(first, last): ヒープから優先度最大(先頭)の要素をpopして残りの要素でヒープにする。

これらをラップするとstd::priority_queueになるが、近いインターフェースで実装したい。両端キューにするのでget/popはget_min, get_max, pop_min, pop_max を実装することにする。

計算量

make_heap O(n)
push O(log n) amortize
pop_min, pop_max O(log n)
get_min, get_max O(1)
メモリ 2 * n * sizeof(T) + c

stdではget_minとpop_minができないのでそこが最大の違い。vectorで実装するためメモリ使用量は最大2倍としているが、データをコピーして複数持つようなことはしない。また、vectorのためpush_heapは償却計算量である。

面白いのはmake_heap、適当なデータ列が与えられたときにヒープを作るのはO(n)であるというところ。1要素づつpushしていくとO(n log n)であるところをmax-heap構造でもinterval-heap構造でもうまく実装するとO(n)に改良できる。

Interval-Heap

ヒープは木構造であるが、配列上でインデックスを操作するだけで親や子に移動できる。Interval-Heapは厳密には木構造ではない気もするがほぼ同じ。
interval-heapでは配列の偶数インデックス上にmax-heapを作り、奇数インデックス上にmin-heapを作る。
f:id:natsugiri:20161010032645p:plain
画像は9要素で作られたinterval-heapの例。矢印の始点が終点より大きい優先度を持つように適切なswapを繰り返す。
この構造はDAGでindex 0から1までの距離がO(log n)、更に次数も少なくpushやpopのときにO(log n)でヒープの条件を満たすように値を置き換えることができる。

コード

template<class T> struct PriorityQueue {
    vector<T> d;

    PriorityQueue() {}

    PriorityQueue(const vector<T> &d_) : d(d_) {
	make_heap();
    }

    template<class Iter> PriorityQueue(Iter first, Iter last) : d(first, last) {
	make_heap();
    }

    void push(const T &x) {
	int k = d.size();
	d.push_back(x);
	up(k);
    }

    void pop_min() {
	if (d.size() < 3u) {
	    d.pop_back(); 
	} else {
	    swap(d[1], d.back()); d.pop_back();
	    int k = down(1);
	    up(k);
	}
    }

    void pop_max() {
	if (d.size() < 2u) { 
	    d.pop_back();
	} else {
	    swap(d[0], d.back()); d.pop_back();
	    int k = down(0);
	    up(k);
	}
    }

    const T& get_min() const {
	return d.size() < 2u ? d[0] : d[1];
    }

    const T& get_max() const {
	return d[0];
    }

    int size() const { return d.size(); }

    bool empty() const { return d.empty(); }

    void make_heap() {
	for (int i=d.size(); i--; ) {
	    if (i & 1 && d[i-1] < d[i]) swap(d[i-1], d[i]);
	    int k = down(i);
	    up(k, i);
	}
    }

    inline int parent(int k) const {
	return ((k>>1)-1)&~1;
    }

    int down(int k) {
	int n = d.size();
	if (k & 1) { // min heap
	    while (2*k+1 < n) {
		int c = 2*k+3;
		if (n <= c || d[c-2] < d[c]) c -= 2;
		if (c < n && d[c] < d[k]) { swap(d[k], d[c]); k = c; }
		else break;
	    }
	} else { // max heap
	    while (2*k+2 < n) {
		int c = 2*k+4;
		if (n <= c || d[c] < d[c-2]) c -= 2;
		if (c < n && d[k] < d[c]) { swap(d[k], d[c]); k = c; }
		else break;
	    }
	}
	return k;
    }

    int up(int k, int root=1) {
	if ((k|1) < (int)d.size() && d[k&~1] < d[k|1]) {
	    swap(d[k&~1], d[k|1]);
	    k ^= 1;
	}

	int p;
	while (root < k && d[p=parent(k)] < d[k]) { // max heap
	    swap(d[p], d[k]);
	    k = p;
	}
	while (root < k && d[k] < d[p=parent(k)|1]) { // min heap
	    swap(d[p], d[k]);
	    k = p;
	}
	return k;
    }
};

終わりに

std::multisetでは同様の操作ができるがそれよりは機能を特化している分、効率のよいデータ構造である。復習のために書いたが両端優先度付きキューは使いどころがなさそう。今まで必要になったことがないので経験上これからも必要にならない。wikipedia先生によれば大量のデータをソートするときにpivotをメモリいっぱい取りキューに突っ込むという応用があるらし。

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選 参加しなかった記

寝食も忘れて、なけなしの社交性も忘れて、プログラミングコンテストに励んでいた1年前の自分、今ではすっかり更生しプログラミングコンテストに出ることも減ってしまった。しかしICPCは解かずには居られない。
※ 私は参加者・選手では無い

リンク

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, H 解答

H: プレゼント交換会

問題

無向グラフがある。全ての辺に向きをつけなさい。そのとき、すべての頂点の入次数の最大値と最小値の差が最小に成るようにし、その時の最大値・最小値を出力せよ。
複数ある場合は最小値を最大化せよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, G 解答

G: ワープ航法

問題

平面上に2つのワープ場を設置したい。ワープ場にたどり着いた航空便は平面の任意の位置に瞬時に移動する事ができる。今、2次元平面上に n箇所の街がある。m本の航空便があり、航空便はある街a_iから他の街b_iへ、速さv_iで直線距離で最短のルートを選択し、移動するものである。
任意のワープポイントの置き方に対し、「各便について最短時間の2乗」の総和を最小化せよ。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, F 解答

F: 文字解読

問題

グリッドの2値画像が与えられる。この画像は「文字」として認識することができる。

  1. 白マスは4方向に連結する
  2. 黒マスは8方向に連結する
  3. 画像の外側は無限に白マスとし、背景と呼ぶ

また、白マスや黒マスの連結成分について包含の条件がある(省略)。
包含関係を連結成分同士の二項関係とすると、その二項関係を「文字」の定義とする。

2つの画像が与えられたとき、その画像が同じ「文字」かどうか判定せよ。
同じ「文字」であるとは、二項関係が保存される連結成分の全単射が存在することである。

続きを読む

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, E 解答

E: 3D プリント

問題

3次元空間に1辺長さsの立方体の設計図が n個ある。全ての立方体は3つの軸に平行で、頂点は整数座標。
ある2つの立方体が共通部分を持つとき連結しているといい、複数の立方体が次々に連結していれば大きな一つの立体になる。
n個の設計図からk個選んで立体を置いたとき、一つの立体に成るようにしなければならない。
このとき、その大きい立体の表面積の最小値を出力せよ。
入力のn個の立方体は次の条件を満たしている。

  1. 各立方体は0個・1個・2個の立方体と連結することはあるが、3個以上の立方体と連結することはない
  2. ある立方体が2個の立方体と連結するとき、その2つは連結していない
  3. どの2つの立方体も頂点・辺・面で接することはない。真に離れているか、真に共通部分を持つかのどちらかである
続きを読む