もう七月だけど、五月の頭に掲げた目標に関しては、結局何もしなかった。 近々でやりたいことが他に結構溜まっているので、取り合えずこの目標は打ち切りとしておく。 作りたいとは思ってるんだけど、やっぱり優先順位が低いのかな...。
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 式) = 切り捨て。
LOUDS++*1の三回目。 今回は、LOUDSの改良版であるLOUDS++に関する部分。 LOUDS++ LOUDSでは、木をビット列として表現していた。 参照: tree-to-lbs (defvar *tree* '(:a (:b) (:c (:f) (:g (:i))) (:d) (:e (:h)))) (tree-to-lbs *tree*) --> #*10111100110…
LOUDS++*1実装の続き。 前回はここ。今回は、この論文中に良く出てくるrankとselectという関数を自分なりに(= 間違っている可能性あり*2 )整理してみた。 rank, select rank及びselectは、前回作成したLBS(LOUDS bit-string)から、木のノード情報を取り出す…
あるサイトからの外部リンク一覧を取得する簡単なクローラ(もどき)をsbclで作成。 ;;;; sbcl-1.0.37 (require :puri) ; ver1.5.1 (require :drakma) ; ver1.0.0: HTTPクライアント (require :cl-ppcre) ; ver2.0.1: 正規表現 (require :sb-queue) ; A thread…
『Enginnering the LOUDS Succinct Tree Representaion*』という論文に目を通し終わったので、(まだ理解はしていないが)これから実装に入る。現状での理解は次のような感じ。 Level-Order Unary Degree Sequenceの略 順序木の表現方法の一つ。静的構築。サイ…
charseq。 こことここで書いたことを実際に試しているライブラリ。 大体以下のようなことを目標としている。 部分文字列の作成が容易かつ低コスト 使用者はそれが部分文字列だということを意識せずに扱える 大抵のケース*1で効率的な文字列操作が行われる ※ …
BASE64のエンコード関数を使いたくなったので作成。 ;; 8byte整数を等価なビットリストに変換 ;; ex: 10 = #b00001010 => (0 0 0 0 1 0 1 0) (defun octet-to-bytes (octet) (loop FOR i FROM 7 DOWNTO 0 COLLECT (ldb (byte 1 i) octet))) ;; listがdivisor…
関数を書いていると、引数の型チェックを有効にするかどうかで悩むことがたまにある。 ;;;; sbcl-1.0.37 ;; 足し算を行う関数 ;; 引数が適切な前提としている (defun plus-impl (x y) (declare ((integer 0 1000) x y) (optimize (speed 3) (safety 0))) (+ …
あまり話題に関連性がないが、一応前々回の続き。 sbcl(1.0.37)での文字列関連の型の階層は以下のようになっている*1。 僕は最近までsimple-string型*2が文字列関連型の最下層だと思い込んでいたので、文字列を扱う部分のプログラムを高速化したい場合、(dec…
調べたメモ。 CLikiに登録されているライブラリは、(asdf-install:install ライブラリ名)でインストール可能 CLikiへの登録手順 CLikiのページに移動 「Create New Page」リンクをクリック ページの名前を聞かれるので、ライブラリ名を入力 => ページ編集画…
Javaは文字列(String型)がimmutable。 この仕様は、汎用的な文字列処理関数を書く場合の負担を軽減してくれていると思う。 対してcommon lispの文字列はmutable。 そのため(そのためか?)、common lispの文字列処理関数*1は、Javaに比べてインターフェース(?)…
今日は端末操作用のエスケープシーケンスを調べる機会があったので、その内の自分が良く使いそうな操作をcommon lispのパッケージとしてまとめておくことにする。 (defpackage ppterm (:use :common-lisp) (:export *colorset* color clear cursor)) (in-pac…
四月の半ばくらいからちょこちょこ作っていたバイト列とユニコード文字列の変換ライブラリがようやく完成*1。 名前: creole まとまった情報は上記リンク先のWikiに書く予定なので、ここでは簡単な使い方と計時結果だけを載せておく。 サンプル ;;; sbcl-1.0.…
表題の通り。 ;; sbcl-1.0.28, sbcl-1.0.37 ;; ファイル名: huge.lisp (defun decode-surrogate-pair (high low) (code-char (+ #x10000 (ash (ldb (byte 10 0) high) 10) (ash (ldb (byte 10 0) low) 00)))) $ sbcl * (compile-file "huge") * (quit) $ ls …
最近は仕事が忙しいこともあり、だらけぎみなので、気を引きしめるために目標を設定しておく。 目標 5月・6月で、common lispの全文検索エンジンを実装する。 これ自体は一年以上前からいつか作りたいと考えていたので、この機会に実装してみることにする。 …
funcallを省略するためのマクロ。 実際には使わなそうだけど、一応残しておく。 (defmacro fnlet (letargs &body body) `(macrolet ,(mapcar (lambda (letarg) (destructuring-bind (fn-name fn) (if (listp letarg) letarg `(,letarg ,letarg)) `(,fn-name …
DoubleArray(トライの一種)を利用して、マルチバイト文字列をユニコード文字列にある程度自動的に変換する、という試み(?)。 ちゃんとした形に整理するほどの気力はないので、一応動く程度のソースコードと覚え書きを残しておくことにする。 やること＆概要 …
common lispではハッシュが使い難い(と思う)。 その理由の一つは、リストのようにマッピング関数がない*1せいだと思うので、そのための関数を定義。 ユーティリティ関数っぽくいろいろ装飾。 ※ 宣言はsbcl(1.0.37)用に特化 (declaim (inline maphash-to-list…
