はてなブックマーク

各種アルゴリズムを試す際のベースとなるような(シンプルな)DoubleArrayが欲しくなったので作成した。 構成など 多分、DoubleArrayとしては一番単純な構成*1。 ※ 以下で云う"ノード"は、"ノードのインデックス"の略のような意味合い 静的構築 各キーを改行区切り('\n')で保持するソート済みのファイルを入力に取り、DoubleArrayを構築する BASE配列とCHECK配列から成る BASE配列: 遷移情報およびキーのIDを保持する配列 BASE[ノード] = 遷移のベースとなるノード => 遷移先ノードは、BASE[ノード] + 遷移文字、で求める BASE[ノード]の値がマイナスの場合は、キーの終端を意味し、そのIDが格納されている => キーのIDは、BASE[ノード] x -1、で求める CHECK配列: 遷移の正当性をチェックするための配列 CHECK[ノー

七回目。多分最後。 これまで作ってきたものを他のtrie実装と比較する。 比較対象 louds-trie: LOUDS++によるtrieの実装。五回目を参照 louds-trie-tail: LOUDS++によるtrie(TAIL配列/圧縮有)の実装。六回目を参照 doar-0.0.12: DoubleArray(TAIL配列/圧縮有)によるtrieの実装。まだunstable tx-0.13: LOUDSによるtrieの実装。詳細不明。louds-trieに比べてbit-vectorの実装が省サイズ(1.3Nビットくらい?) darts-32: DoubleArray(TAIL配列無)によるtrieの実装。詳細不明 比較内容 以下の二つの項目の比較を行う。 trie用のバイナリデータのサイズ キー検索速度 データ 比較に用いるtrieのキーセットとしては、Wikipediaのタイトルを利

オンラインで読める『Real World Haskell』という本の目次を眺めていたら、BloomFilterという言葉を発見。 どうやらデータ構造の一種らしいが、聞いたことがなかったので調べてみた(Wikipediaで)。 結果、セット(集合)を表すためのデータ構造だということが分かった。 偽陽性*1はあるが、メモリ使用量が凄く少なくて済むのが特徴で、例えば-目安として、だが- 要素数が100万のセットなら1MB程度のメモリで表現できるようだ。ちなみに、集合中の要素の列挙や削除といった操作は出来ない 実装としては、衝突を考慮しない and 要素を格納しないハッシュ、といった感じ。 BloomFilterの初期化、要素追加、帰属判定を行うcommon lispのプログラムを書いてみたので、下に載せる。 ;; 構造体: ビット配列と要素の追加・判定に用いるハッシュ関数のリストを持つ (def

aproposとdescribeを一緒にしたような関数を作成。 名前はそのままapropos-desc。 aproposを使えば、シンボル一覧が取得できるが、それに(そのシンボルにバインドしている)関数などの簡単な情報(引数、返り値、ドキュメント)も一緒に表示されるようにした。 基本的には、apropos-listの結果にdescribeを適用しただけだが、sbclの標準のdescribe出力は若干量が多すぎることがあるので、自分に必要な情報だけを出力するようにして、一覧性を上げている。 例 ;; 第三引数までは、apropos関数と同様 ;; "multiple"を含むシンボルをcommon-lispパッケージから探して、その名前と簡易的な情報を表示する。 > (apropos-desc "multiple" :common-lisp t) === multiple-value-bind