common lisp
半年くらい前に書いた「アナフォリックマクロとpacakge」の続き。この方法だとダメなケースを発見したので、その改善策(?)を考えてみる。 以前の方法 以前の方法は、アナフォリックマクロの定義と使用が別パッケージに分かれる場合に、アナフォリック変数の…
ftype型宣言。 あまり使われているのを見ない気がするが、これを使うと「型宣言なしでは遅いけど、宣言をつけるとコードが汚くなる」というような問題を解決できる時があるので、少し書いておく。以下はsbcl(1.0.34)での挙動。 準備 ;; 処理速度を最優先 (de…
冬休みに作成したgzip圧縮器を整理*1して、パッケージにまとめた。 ・deflate(0.1.0) ※ 依存: common-utils 以下は簡単な計時など。 比較対象は、gzipコマンドとcommon lispのsalza2パッケージ。 # gzip > time gzip -c /path/to/file > file.gz ;; salza2 (…
gzip圧縮/解凍器作成の４。 ようやくgzip圧縮器の作成に着手。 gzipパッケージ 今回は、DEFLATEフォーマットに準拠したデータの作成/書き出し部分の実装が主となるが、それに取りかかる前にgzipファイル作成用のユーティリティパッケージを定義しておく。コ…
RFC1951のDEFLATE圧縮データフォーマットを実装するために作成したビットストリーム。 DEFLATEを実装するのに当面必要な関数だけが定義してあり、インターフェースは適当。 ;;;;;;;;;;;;;;; ;;;; パッケージ (defpackage :bit-stream (:use :common-lisp) (:…
gzip圧縮/解凍器作成の３。 軽く整理 gzipはデータの圧縮に(主に)DEFLATEアルゴリズム(or DEFLATE圧縮データフォーマット)を利用している DEFLATEでは以下のような方法でデータの圧縮が行われる 入力データをLZ77アルゴリズムで圧縮する 上記圧縮データをさ…
冬休み(中に終わらせたい)の取り組み、gzip圧縮/解凍器作成の２。 前回は、RFC 1951(日本語訳)で定義されているDEFLATEフォーマットに準拠したデータを作成するのに必要な符号長の制限付きのハフマン符号化アルゴリズムを実装した。 今回はDEFLATEに関する残…
最近ちょくちょくトライを使いたくなることがあるので、少しまとまったハッシュトライの実装を書いておく。 位置付け的には開発用。使用頻度が高いようなら、もう少しちゃんとしたものに書き直す。 ※ 2010/01/03: print-objectメソッド追加、common-prefix-s…
冬休みの取り組みとして、ZIP*1圧縮/解凍器を作ってみることにした。 ZIPで使われている圧縮アルゴリズム(圧縮フォーマット?)は、DEFLATEアルゴリズムと云って、簡単に云えばLZ77とハフマン符号化を組み合わせたもののようだ。日本語版仕様(RFC1951) ハフマ…
列の要素にキー関数を適用して、その結果が最大(or 最小)となる要素を返す、という関数。 loopマクロのmin/max辺りでやってくれるかなと思ったが、無理そうなので自作した。 マクロをふんだんに使用。 (defmacro find-xxx-helper (empty? first loop compare…
テキストおよびバイナリファイル読込み関数定義。 (defun read-binary-file (path) (with-open-file (in path :element-type '(unsigned-byte 8)) (let ((as (make-array (file-length in) :element-type '(unsigned-byte 8)))) (read-sequence as in) as)))…
仕事柄(かどうかは分からないが)switch分岐を多用したCやC++の文字列(群?)変換関数を書く機会がたまにある。 例えば最近では、Shift_JISの全角文字(カタカナ+記号)を半角文字に変換するCの関数を作成した(このRuby拡張ライブラリの中で使われている関数)。 …
前々回に作成したURLデコード用の関数では、sb-ext:octets-to-string関数が処理のボトルネックとなっていた。 確かsbcl(1.0.28)はバイト列から文字列への変換には、UTF-8でもShift-JISでもEUC-JP(及びその他)でも出来るような汎用的な方法(枠組み?)*1を採用…
URLのエンコード/デコード処理は、時々必要になって、その度に(適当に)自作しているものの一つなので、今回少し真面目に作成してパッケージにまとめてみた。 仕様は『URLEncoder (Java Platform SE 6)』を参考にさせてもらった。 (defpackage :url (:use :co…
sbcl(1.0.28)で文字列のリストのユニークな要素を取ろうとすると、やけに遅い。 リストの要素数は30万くらいなのだが、しばらく待ってもレスポンスがない。 > (length *word-list*) ; *word-list*は文字列のリスト --> 320000 ; この数は適当 > (time (remov…
sbclのソースを読んでいたら、次のようなコードを目にした。 ;;; sbcl-1.0.29/src/code/seq.lispのlist-remove-duplicates*関数からの抜粋 (let* ((result (list '())) (splice result) (current list)) ; listは引数で渡されたリスト #|...|# (do (#|...|#)…
一つ前の記事では、以下のようなmaxf及びminfというマクロを定義して使っていた。 ;;; 定義 (defmacro maxf (a &rest as) `(setf ,a (max ,@as))) (defmacro minf (a &rest as) `(setf ,a (min ,@as))) ;;; 使用例 ;; 「aの値が20よりも小さい場合は、aの値…
本業の方が忙しくて、なかなかまとまったことをする時間がないので、軽いものを一つ。「Get a Rectangular Field」というパズルのような問題を解いてみる。 問題の説明等はここを参照。 途中経過とかは全て飛ばして、とりあえず最初に思いついた解答(を若干…
common lispでは、バイト配列型を(vector (unsigned-byte 8))と表す。 この型は個人的にはかなり使用頻度が高いのだが、見ての通り長くて打ちづらい。今まではその時々によって、上の型をそのまま使ったり、エイリアス型を定義して使ったりしていたのだが、…
形態素解析器の４。 今回は未知語処理+αを扱う。 前回までで作成した形態素解析器では、下の例のように未知語が"_"と表示されてしまうが、これをちゃんと"ocaml"と表示されるようにするのが今回の主たる目的。 ;; 未知語=単語辞書に登録されていない語は、"_…
形態素解析器作成の３。 前回、形態素解析のステップを大まかに二つに分けた。 入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能なので、その全てのパターンを列挙する それらの分割にコスト(優先順位)を付与する。コスト…
形態素解析器作成の２。前回で必要なデータの準備は終わったので、今回からは解析器の実装に入る。 この実装では、形態素解析はおおまかに次の二つの段階に分けられる。 入力テキストを形態素列に分割する。一般に、入力テキストは複数の形態素列に変換可能…
以前に「DoubleArrayと辞書があれば、形態素解析器は案外簡単にできるのではないか」というようなことを書いた。 試してみたところ、実際に結構簡単に(ほぼ)MeCab互換の形態素解析器ができたので、それを何回かに分けて載せていくことにする。 作るもの 未知…
doar-0.0.6のmkdoarコマンドで保存したDoubleArrayデータをロードして検索が行えるcommon lispの関数群を作成して、動かしてみた。検索速度的には、文字列を終始バイト列として扱うことを前提とすれば、C++版に比べて3倍程度遅いだけ(?)なので、まあ許容範囲…
僕が行うデバッグ(及びプログラムの動作確認)のほとんどは、プリントデバッグだ。 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…
ここに書かれている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…
