van Emde Boas tree （注目度急上昇中！）
「プログラマが知るべき97のこと」でちょこっと紹介されていた
二分探索より高速な検索ができるという van Emde Boas tree（vEB木）を実装してみました。
各操作（挿入・削除・検索、さらに、次のキーの検索・前のキーの検索）を O(lg lg n) で実行可能！
用法用量を守って正しく使えば、かなりのパフォーマンス向上が期待できるかも。
/**
* Copyright o8que ( http://wonderfl.net/user/o8que )
* MIT License ( http://www.opensource.org/licenses/mit-license.php )
* Downloaded from: http://wonderfl.net/c/dNrQ
*/
/* ------------------------------------------------------------------------------------------------
* [reference]
* van Emde Boas tree - Wikipedia, the free encyclopedia
* http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
* ------------------------------------------------------------------------------------------------
*/
package {
import com.actionscriptbible.Example;
import flash.events.MouseEvent;
import flash.utils.getTimer;
[SWF(width="465",height="465")]
public class Main extends Example {
private static const KEY_RANGE:int = int.MAX_VALUE;
private static const NUM_ELEMENTS:int = 1e5;
private static const LOOP_COUNT:int = 2e5;
private var _sortedArray:Array;
private var _vEBTree:VEBTree;
public function Main() {
_sortedArray = [];
_vEBTree = new VEBTree(KEY_RANGE);
for (var i:int = 0; i < NUM_ELEMENTS; i++) {
var key:int = int(KEY_RANGE * Math.random());
// vEB木に重複なしにキーを追加できたら、配列にもキーを追加する（重複キーなら再試行）
if (_vEBTree.add(key)) {
_sortedArray.push(key);
}else {
i--;
}
}
_sortedArray.sort(Array.NUMERIC);
trace("整数のキーの範囲 [0," + KEY_RANGE + ")");
trace("保持キー数 " + NUM_ELEMENTS + " 個");
trace("範囲内のランダムなキーの検索を " + LOOP_COUNT + " 回試行");
runTest();
stage.addEventListener(MouseEvent.CLICK, runTest);
}
/** テストを実行する */
private function runTest(event:MouseEvent = null):void {
var temp:int, i:int;
trace("----------------------------------------");
temp = getTimer();
for (i = 0; i < LOOP_COUNT; i++) {
useBinarySearch(int(KEY_RANGE * Math.random()));
}
temp = getTimer() - temp;
trace("二分探索: " + temp + "ms");
temp = getTimer();
for (i = 0; i < LOOP_COUNT; i++) {
_vEBTree.contains(int(KEY_RANGE * Math.random()));
}
temp = getTimer() - temp;
trace("vEB木検索: " + temp + "ms");
}
/** ソート済み配列を二分探索する */
private function useBinarySearch(key:int):Boolean {
var low:int = 0;
var high:int = _sortedArray.length - 1;
while (low <= high) {
var middle:int = (low + high) / 2;
var middleValue:int = _sortedArray[middle];
if (key < middleValue) {
high = middle - 1;
}else if (key > middleValue) {
low = middle + 1;
}else {
return true;
}
}
return false;
}
}
}
/* ------------------------------------------------------------------------------------------------
* VEBTree
* ------------------------------------------------------------------------------------------------
*/
//package {
//public
class VEBTree {
private var _maxSize:int; // 最大で保持できるキーの数
private var _lowBits:int; // キーの下位ビット数（上位ビット取得用）
private var _lowMask:int; // キーの下位ビットマスク（下位ビット取得用）
private var _children:Vector.<VEBTree>; // サブツリーのコレクション
private var _aux:VEBTree; // サブツリーが空でないかどうかを保持する補助ツリー
private var _min:int; // 最小値のキャッシュ
private var _max:int; // 最大値のキャッシュ
private var _size:int; // 保持しているキーの数
/**
* 指定された数のキーを保持できるvan Emde Boas木を作成します。
* @param maxSize 最大で保持できるキーの数を指定する値です。値は2のべき乗に切り上げられます。
*/
public function VEBTree(maxSize:int) {
// m-bit integer keys
var m:int = Math.ceil(Math.log(Math.max(2, maxSize)) / Math.LN2);
_maxSize = Math.min(int.MAX_VALUE, uint(1 << m)); // Math.pow(2, m)
_lowBits = m >> 1; // int(m / 2)
_lowMask = (1 << _lowBits) - 1;
_children = new Vector.<VEBTree>(1 << Math.ceil(m / 2), true);
_aux = null;
_min = int.MAX_VALUE;
_max = int.MIN_VALUE;
_size = 0;
}
/**
* 指定されたキーをツリーに追加します。
* @param key 追加されるキーの値です。
* @return キーが重複なしにツリーに追加された場合にtrueを返します。
*/
public function add(key:int):Boolean {
// 範囲外のキーか、重複キーなら終了
if ((key < 0 || key >= _maxSize) || (key == _min || key == _max)) { return false; }
// ツリーが空なら、キーをキャッシュして終了
if (_size == 0) {
_min = _max = key;
_size++;
return true;
}
// キーがキャッシュを更新できるなら、キーとキャッシュをスワップする
// スワップ後のキーを、サブツリーに追加する必要が無いなら終了
var temp:int;
if (key < _min) {
temp = key; key = _min; _min = temp;
if (key == _max) {
_size++;
return true;
}
}else if (key > _max) {
temp = key; key = _max; _max = temp;
if (key == _min) {
_size++;
return true;
}
}
// キーをサブツリーに追加する
var i:int = key >> _lowBits;
var j:int = key & _lowMask;
if (!_children[i]) {
_children[i] = new VEBTree(1 << _lowBits);
_aux ||= new VEBTree(_children.length);
_aux.add(i);
}
if (_children[i].add(j)) {
_size++;
return true;
}else {
return false;
}
}
/**
* 指定されたキーをツリーから削除します。
* @param key 削除されるキーの値です。
* @return ツリー内に存在するキーが削除された場合にtrueを返します。
*/
public function remove(key:int):Boolean {
// 範囲外のキーか、ツリーが空なら終了
if (key < _min || key > _max) { return false; }
// キーが唯一のキャッシュ（保持キー数が1）なら、ツリーを空にして終了
if (key == _min && key == _max) {
_min = int.MAX_VALUE;
_max = int.MIN_VALUE;
_size--;
return true;
}
// キーがキャッシュにあり、
// サブツリーが無い（保持キー数が2）なら削除(保持キー数を1に）して終了
// サブツリーがあるなら（最小or最大の）キーを取得、キャッシュを更新してそのキーを削除候補にする
var i:int;
var j:int;
if (key == _min) {
if (!_aux) {
_min = _max;
_size--;
return true;
}else {
i = _aux.min;
j = _children[i].min;
_min = (i * _children[i].maxSize) + j;
}
}else if (key == _max) {
if (!_aux) {
_max = _min;
_size--;
return true;
}else {
i = _aux.max;
j = _children[i].max;
_max = (i * _children[i].maxSize) + j;
}
// キーがキャッシュに無いなら、キーを削除候補にする
// サブツリーが無いなら終了
}else {
i = key >> _lowBits;
j = key & _lowMask;
if (!_children[i]) { return false; }
}
// 削除候補をサブツリーから削除する
// 削除成功後、サブツリーと補助ツリーが空ならそれも削除する
if (_children[i].remove(j)) {
if (_children[i].size == 0) {
_children[i] = null;
_aux.remove(i);
if (_aux.size == 0) {
_aux = null;
}
}
_size--;
return true;
}else {
return false;
}
}
/**
* 指定されたキーがツリー内に存在するかどうか調べます。
* @param key ツリー内に存在するかどうか調べるキーの値です。
* @return 指定されたキーがツリー内に存在した場合にtrueを返します。
*/
public function contains(key:int):Boolean {
// 範囲外のキーか、ツリーが空ならfalse
if (key < _min || key > _max) { return false; }
// キーがキャッシュされているならtrue
if (key == _min || key == _max) { return true; }
// サブツリーを調べる（サブツリーが空ならfalse）
var i:int = key >> _lowBits;
var j:int = key & _lowMask;
return _children[i] && _children[i].contains(j);
}
/**
* 指定された値の、次に存在するキーの値を取得します。
* @param key 次に存在するキーを調べるための基準となる値です。
* @return 次に存在するキーの値を返します。存在しなければ-1を返します。
*/
public function next(key:int):int {
// ツリーが空か、値が最大値以上なら存在しない
if (_size == 0 || key >= _max) { return -1; }
// 値が最小値未満なら最小値を返す
if (key < _min) { return _min; }
// 値と同じサブツリー内にあるなら、そのサブツリーを調べる
var i:int = key >> _lowBits;
var j:int = key & _lowMask;
if (_children[i] && j < _children[i].max) {
return (i * _children[i].maxSize) + _children[i].next(j);
}
// 次のサブツリーがあるなら、そのサブツリーの最小値を返す
if (_aux) {
var nextChild:int = _aux.next(i);
if (nextChild >= 0) {
return (nextChild * _children[nextChild].maxSize) + _children[nextChild].min;
}
}
// サブツリーが無いなら最大値を返す
return _max;
}
/**
* 指定された値の、前に存在するキーの値を取得します。
* @param key 前に存在するキーを調べるための基準となる値です。
* @return 前に存在するキーの値を返します。存在しなければ-1を返します。
*/
public function prev(key:int):int {
// ツリーが空か、値が最小値以下なら存在しない
if (_size == 0 || key <= _min) { return -1; }
// 値が最大値より大きいなら最大値を返す
if (key > _max) { return _max; }
// 値と同じサブツリー内にあるなら、そのサブツリーを調べる
var i:int = key >> _lowBits;
var j:int = key & _lowMask;
if (_children[i] && j > _children[i].min) {
return (i * _children[i].maxSize) + _children[i].prev(j);
}
// 前のサブツリーがあるなら、そのサブツリーの最大値を返す
if (_aux) {
var prevChild:int = _aux.prev(i);
if (prevChild >= 0) {
return (prevChild * _children[prevChild].maxSize) + _children[prevChild].max;
}
}
// サブツリーが無いなら最小値を返す
return _min;
}
/** 最大で保持できるキーの数を取得します。 */
public function get maxSize():int { return _maxSize; }
/** ツリー内に存在する最小のキーの値を取得します。 */
public function get min():int { return _min; }
/** ツリー内に存在する最大のキーの値を取得します。 */
public function get max():int { return _max; }
/** ツリー内に保持しているキーの数を取得します。 */
public function get size():int { return _size; }
}
//}