Cからlispの関数を呼ぶ方法を調べた。 最終的には、lisp環境を動的ライブラリ形式っぽく保存して、Cで作成した実行ファイルから任意の関数を呼び出せるようにしたいのだが(そこまでやるかどうかは分からないが...)、とりあえず今日は、lisp関数を呼び出すCの…

doar-0.0.6のmkdoarコマンドで保存したDoubleArrayデータをロードして検索が行えるcommon lispの関数群を作成して、動かしてみた。検索速度的には、文字列を終始バイト列として扱うことを前提とすれば、C++版に比べて3倍程度遅いだけ(?)なので、まあ許容範囲…

doar実装関連雑記。 今日は、(形態素解析には必須の?)common-prefix-search関数の実装に取り組んでいた。 ;; common-prefix-searchの動作を示すための例 (defvar *data* '("自転車" "自動車" "自動" "自" "時刻" "自動車免許" "免許" "車")) (defun common-p…

SourceForgeにDoubleArrayのC++ライブラリ用のプロジェクトを作成した。 名前は、DOubleARrayでDoar。 とりあえず現状のソース*1とごく簡単なドキュメントが載せてある。まだまだ安定版には遠いけど...。 10月中には、主要な開発は終わらせたい...。 *1:動的…

僕が行うデバッグ(及びプログラムの動作確認)のほとんどは、プリントデバッグだ。 common lispのprint系の出力関数は、引数の値を出力した後(?)そのまま返してくれるので、ある式の値を手軽に知りたいときは、その式を(print exp)といったように出力関数で囲…

前回、ハッシュテーブル用にprint-objectメソッドを定義したが、これには重大な欠点があった。次の例を見てもらえば分かると思うが、要素数がある程度大きくなると出力が極めて見にくくなってしまう。 ;; 30要素のハッシュを作成する > (let ((hash (make-ha…

今日、会社の同僚や先輩と、通常のものより比較回数が少なくてすむ二分木探索の実装方法や性能について、(以前見た or 書いた覚えはあるが忘れていたので)あれこれ話していた。 その結果、(一部は自分の中で)一応の結論を得たので、書いておく。 ※ 以下に書…

sbcl(1.0.28)では、ハッシュテーブルを表示する際に、テスト関数名と要素数(+ ID)しか出てこない。 > (make-hash-table) --> #<HASH-TABLE :TEST EQL :COUNT 0 {AFA2A89}> この(要素の確認し辛さの)ために*1、ついつい連想リストを(代わりに)使うことが多くなってしまうのだが、やはりハッシュを使いた</hash-table>…

V。フォーマット指示子に与えることのできるパラメータ。 対応する位置の引数(数値)に置換される。 再帰・繰返し的な出力処理を行いたい場合に便利(だけどよく忘れるし、ドキュメントからも探しにくい)。 サンプルコード > (format t "~V%###" 3) ; = (forma…

ベンチマークを取る時には、対象となる部分以外に掛かる処理時間を極力抑えたい。 標準のファイル入力クラスであるifstreamは、結構便利でそこそこ高速ではあるのだが、大量の行を読み込む場合、少なくはないオーバヘッドが出てしまう。 なので、今回は、ベ…

近況 ここしばらくは、ひたすらC++でDoubleArrayの実装に取り組んでいる。もともとは、シンプルなものを一つ作って終わりにしようかと考えていたのだが、検索・挿入効率とかメモリ使用量(ファイルサイズ)とか大きい(千万程度)のキーセットに対して効率的な実…

ここに書かれているcompact-number-listという関数をcommon lispで実装してみた。 (defun compact-number-list (list &aux (beg (car list))) (labels ((get-end (num list &optional (sole? t)) (if (eql (1+ num) (car list)) ; XXX: 数値の比較とlistのni…

Haskellのモナドの簡単なものをcommon lispで実装してみたので、コードを載せておく。 ※ 対象としたのは、maybeモナド、listモナド、stateモナド、continuationモナドの四つで、それぞれの定義は『All About Monads』の第三部を参考にさせてもらった。(各モ…

ensure-directories-existは、pオプション付きのmkdirコマンドと同じような動作をすると思っていたのだが、少し違ったのでメモ。 mkdirコマンドは、引数のパスをディレクトリ名として解釈する。※以下の例では、全て空の/tmpディレクトリのみが存在すると仮定…

オンラインで読める『Real World Haskell』という本の目次を眺めていたら、BloomFilterという言葉を発見。 どうやらデータ構造の一種らしいが、聞いたことがなかったので調べてみた(Wikipediaで)。 結果、セット(集合)を表すためのデータ構造だということが…

ふと思い立って、カリー化を行う関数を書いてみた。 (defun curry (fn &rest args) (lambda (&rest rest-args) (apply fn (append args rest-args)))) ;;; > (curry #'cons :first) -->#<CLOSURE (LAMBDA (&REST REST-ARGS)) {B3BC96D}> > (funcall * :second) --> (:FIRST . :SECOND) カリー化関数は他の誰</closure>…

aproposとdescribeを一緒にしたような関数を作成。 名前はそのままapropos-desc。aproposを使えば、シンボル一覧が取得できるが、それに(そのシンボルにバインドしている)関数などの簡単な情報(引数、返り値、ドキュメント)も一緒に表示されるようにした。基…

以前DoubleArrayのTAIL圧縮を取り扱った時に参考にした『ダブル配列におけるキャッシュの効率化』*1という論文には、TAIL配列の他に、BASE配列とCHECK配列を圧縮する方法も載っていた*2。 それほど長くないので、該当個所を引用させてもらう。 ダブル配列は…

SuffixArrayという言葉を最近知ったのだが、それが意味するところはいまいち分かっていない。 とりあえず、現状の認識としては以下のような感じ。※間違っている可能性が大いにあり TAIL配列を使うDoubleArrayに似ている。 転置インデックスを作成せずに可変…

『Let Over Lambda』を読んでいたら、p.22の脚注に次のような記述を発見した。 We can also indicate the specialness of variables by using declarations to make them locally special. declareで宣言すれば、"locally"なspecial変数が使える、というよう…

Wikipediaのcommon lispの項目を読んでいたら、iterateというパッケージの存在を知った。少し興味を引かれたのでマニュアルに(簡単に)目を通してみた。 名前の通り、繰り返し処理を行うためのパッケージで、立ち位置的にはloopマクロに近いようだ。 >(iter (…

asdf-installを使ってパッケージをインストールしようとすると、下のように「GPGのキーがありません」(?)とよく云われる。 >(asdf-install:install "cl-ppcre") ...略... debugger invoked on a ASDF-INSTALL::KEY-NOT-FOUND in thread #<THREAD "initial thread" RUNNING {AB6E569}>: No key found for </thread>…

最近はJSONばっかりだが、一昨日書いたC++版のJSONパーサのrubyバインディングを作ってみた。ソースコードは(ruby用にいろいろ変更が加わっているが)今まで書いてきたJSONのそれと基本的には同じものなので割愛する。 インストール用のファイル一式はここに…

以前作成したC++のJSONパーサの高速化試行。 C++のデフォルトのnewは、小さいサイズのメモリを大量に割り当てるのが遅いということは有名(?)なので、JSONパーサ用に、専用のallocatorクラスを作成することにした。今回作成したallocatorクラスのテンプレート…

以前作成したC++のJSONパーサをもっと速くできないかと思い、いろいろ試してみた。結構速くなったので、以前のものとの比較、変更点概要、ソースコードを載せておくことにする。 以前のJSONパーサとの比較 以前のJSONパーサや比較条件などに関しては、以前の…

JSONのようにデータの記述だけからなる言語の場合、パーサさえ書いてしまえば、それをcommon lispに組み込むことは容易だ。例えば、『JSONデコード: トップダウン』で作成したJSONパーサを使った場合は、以下の4行だけで、common lispがJSONを解釈するように…

数日前にcommon lispでJSONパーサを実装したが、そのC++版を書いてみた。実装的には、common lisp版とほとんど変わらないが、サロゲート・ペアに対応したり、エンコード関数も(おまけ程度)に作成したり、と若干以前よりは高機能になっている。ソースコードは…

今までのDoubleArrayの実装では、当然のように(vector (unsigned-byte 8))をキーとして利用してきた。文字列(キー)を扱う場合は、1byte(=8bit)を単位として扱うのが自然なので、悪くはない(むしろ良い?)とは思うのだが、2byte以上を単位として扱うのも、それ…

最近はパーサを書くことが割合多く、そして(僕が書くような)パーサでは、read-char関数の呼び出し部分が、全体の中で一番大きなボトルネックになっていることが少なくない。そういった場合、これまではread-char関数の呼び出し回数を減らす(アルゴリズムやロ…

mmapは便利なので(C++を使うときは)割合よく利用する。 ただ、初期化が面倒で毎回リファレンスなどを調べるはめになるので、クラス(struct)としてまとめておくことにする。 ↓ // mmap_t.h #include <sys/stat.h> #include <sys/mman.h> #include <fcntl.h> #include <unistd.h> struct mmap_t{ mmap_t(co</unistd.h></fcntl.h></sys/mman.h></sys/stat.h>…