2009-09-01から1ヶ月間の記事一覧

ハッシュテーブル表示

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

~V

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

高速行読込クラス

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

DoubleArray: ソート済みデータからの構築

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

compact-number-list

ここに書かれている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注意書き

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

BloomFilter

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

DoubleArray(3-3): BASEとCHECK配列圧縮

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

SuffixArrayがどんなものかを考えてみる。

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

(declare (special ...))

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

iterateパッケージ

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

skip "SKIP-GPG-CHECK"

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>…