もう七月だけど、五月の頭に掲げた目標に関しては、結局何もしなかった。 近々でやりたいことが他に結構溜まっているので、取り合えずこの目標は打ち切りとしておく。 作りたいとは思ってるんだけど、やっぱり優先順位が低いのかな...。

BASEとCHECKの表現として、(すぐ思いつくものとしては)以下の二つがあると思う。 // 方法1: BASEとCHECK用にそれぞれ配列を用意する int base[ノード数]; int chck[ノード数]; // 方法2: ノード用に一つの配列を用意し、その各要素がBASEとCHECKフィールドを…

各種アルゴリズムを試す際のベースとなるような(シンプルな)DoubleArrayが欲しくなったので作成した。 構成など 多分、DoubleArrayとしては一番単純な構成*1。 ※ 以下で云う"ノード"は、"ノードのインデックス"の略のような意味合い 静的構築 各キーを改行区…

LOUDS(LOUDS++)とは直接は関係ない。 八回目にLOUDS++に試したこと(+α)をdoarにも適用してみたので、その結果。 試したこと 以下の二つ。 どちらもデータサイズを縮小することを目的とした変更。 無分岐ノードの削除 八回目にLOUDS++のtrieで試したものと基…

試したいことが出てきたので、少し延長して八回目。 目的 今回の目的は六回目で作成したtrieをベースとし、検索速度を向上させること。 結果 最初に結果から載せる。 入力データや計測方法等は七回目のそれらに準拠。 データサイズ検索所要時間(秒) louds-tr…

七回目。多分最後。これまで作ってきたものを他のtrie実装と比較する。 比較対象 louds-trie: LOUDS++によるtrieの実装。五回目を参照 louds-trie-tail: LOUDS++によるtrie(TAIL配列/圧縮有)の実装。六回目を参照 doar-0.0.12: DoubleArray(TAIL配列/圧縮有)…

前回に作成したLOUDS(LOUDS++)を用いたtrieの改良を試みる。 改良案 前回のtrie実装は、まだまだ全然最適化されていないので、改良すべき(or できるであろう)箇所は結構沢山ある。 案として、例えば... bit-vectorの実装方法 ... 他の実装方法の方が効率的(…

四回目まででLOUDS(LOUDS++)の実装方法は分かったので、今回は応用編。 LOUDSを用いてtrieを実装する(というかtrieを実装したソースコードを載せる)。 作るもの 実際に作成するのは以下の二つのコマンド。 mklouds-trie: ソート済みテキストファイルから、LO…

以下のような内容のファイルがあるとする。 # ファイル名: sample.txt ※ この部分はファイルに含まれない ab abc abef 1 1248 126 13579 これは次のような構造を持つトライ木として考えることができる。※'_ROOT_'は仮想的なスーパールート 今回は、上のよう…

FIFOのキュー。 これもたまに使いたくなるので、実装(の一つ)をメモしておく。 (declaim (inline make-queue enqueue dequeue queue-empty-p queue-to-list)) (defun make-queue (&optional initial-contents) (declare (optimize (speed 3) (safety 0))) (l…

LOUDSの四回目。 selectおよびrankが効率的に行えるビット配列(bit-vector)の実装。 参考 一応参考にしたのは、次の二つの論文 『A Simple Optimal Representation for Balanced Parentheses』 『Compressed Prefix Sums』 ただし、良く分からないところや、…

以前に書いたリストを破壊的に反転する関数を少し書き直してみた。 まずは、以前に書いた関数。 参照: nlet (defun list-reverse! (lst) (nlet self ((lst lst) head) (if (endp lst) head (self #1=(cdr lst) (progn (setf #1# head) lst))))) 定義は短いが…

⎡式⎤ = (ceiling 式) = 切り上げ。 ⎣式⎦ = (floor 式) = 切り捨て。