sile / veb-tree Goto Github PK
View Code? Open in Web Editor NEWvan Emde Boas tree
van Emde Boas tree
============ === 概要 === ・common lispによるVan Emde Boas Tree(vEB-tree)の実装 ・Van Emde Boas Tree ・多分木 ・要素の挿入/検索/削除がO(log log M)で行える ・要素は正の整数値に限定 => 本来は整数値のキーと値を紐付けたマップ(or 連想配列)的な使い方をするのだろうが 今回の実装では未対応 ・Mは要素の最大値 ・優先順序付きキューとして利用可能 ・「次に小さい要素」の検索もO(log log M)で行える ※ 以降はメモ ・メリット ・平衡二分木よりも処理オーダーが良い ・要素セットが大きい場合はサイズ効率も良い => 二分木よりもポインタ(参照)のために必要な領域が少なくなるため ・デメリット ・要素セットが小さい場合(or 要素セットが疎な場合)には、オーバヘッドが大きい ・要素の最大値をあらかじめ指定しておく必要がある ・実装 ・(配列を用いた)トライ木と似ており、各ノードの探索時に先頭からxビットずつを使って、対象となる子ノードを検出する ・ただし、トライ木は全てのノードで一律に同じサイズのxビットを使うのに対して、 vEB木は、最初のノードでは、キーのビット長さの半分を使い、次は残りのビットのさらに半分を・・・、と キーのビット長さに合わせてxビットの幅を変えているため、より効率的となる ・トライ木: キービット長/定数 => O(キービット長) ・vEB木: log(キービット長) ・また、vEB木は各ノードで要素の最小値・最大値および、どの子ノードに要素が挿入されているかを管理しているため、 (配列版のトライ木と異なり)有効な子ノードの検出が効率的に行える ・子ノードの有効無効(要素の有無)を管理するためにも、vEB木が利用されている ・bit-arrayを使った方が(環境によっては?)効率的になるかもしれない ================== === バージョン === ・0.0.1 =========== === API === # (veb-tree:make capacity) => tree veb木を作成する - capacity: 挿入される要素の最大値 # (veb-tree:size tree) => size veb木に挿入された要素の数を取得する # (veb-tree:empty-p tree) => boolean veb木が空なら真を返す # (veb-tree:push element tree) => tree veb木に要素を挿入する 既に同じ要素が挿入されている場合は、要素の追加は行われない element: 正の整数値。make関数に渡したcapacity以内の値である必要がある # (veb-tree:pop tree) => element veb木の先頭要素(一番小さい要素)を取り除いて返す # (veb-tree:head tree) => element veb木の先頭要素を返す # (veb-tree:remove element tree) => tree veb木から指定された要素を削除する # (veb-tree:find element tree) => boolean veb木に指定された要素が存在するかどうかを判定する # (veb-tree:next element tree) => element veb木内の存在するelement以上で一番小さい要素を返す 該当する要素がない場合はnilが返る # (veb-tree:to-list tree) => list veb木をリストに変換して返す 返ってくるリストは、ソート済みの状態 # (veb-tree:from-list capacity tree) => tree veb木をリストから作成する # (veb-tree:each (var tree &optional return-form) &body body) veb木内の各要素を昇順に走査する - var: 各走査で、要素が束縛される変数 - tree: 走査対象のveb木 - return-form: 走査終了後に評価される式。この式の評価結果がeachの返り値となる。 - body: 各走査毎に実行される処理本体 ============ === 参考 === ・http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.