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の全文検索エンジンを実装する。 これ自体は一年以上前からいつか作りたいと考えていたので、この機会に実装してみることにする。 …