2009-01-01から1年間の記事一覧
JSONのパーサを作ってみた。 参考にしたのは、こことここ。 今回作成したのはトップダウン(再帰下降)型のパーサ。 ボトムアップ版もいつか作ってみたいという思いを込めて、タイトルに「トップダウン」と入れておく。 割合高速。 実装 ほぼJSONの仕様(?)通り…
DoubleArrayの3-1。 今回はTAIL配列の圧縮を行う。 参考にした(かな?)のは、次の論文: 『ダブル配列におけるキャッシュの効率化』*1。上の論文の中に「後方一致する接尾辞を併合することで、TAILを圧縮することができる」という記述があるが、今回はこの通り…
以前、中途半端にHTMLパーサを実装したが、htmlをS式に変換してくれるcl-html-parseというライブラリが既にあったようだ。 > (asdf-install:install :cl-html-parse) > (net.html.parser:parse-html "<html><head><title>title</title></head><body></body></html>") --> ((:HTML (:HEAD (:TITLE "title")) (:BODY)))
コンパイラの本を流し読みしていたら、中置記法とか前置記法とか後置記法とかが出てきた。これらの記法間の変換処理(正確には中置記法から後置記法への変換)は、だいぶ前に実装しようとして挫折(?)したことがあったのだが、今日試してみたら、(適切なコード…
common lispでは、標準出力にバイナリデータを出力する方法が定義されていない(多分)。unix系(?)のOSの場合は、以下のように/dev/stdoutをopenすればバイナリデータを標準出力に出力できるようだ。 > (sb-ext:string-to-octets "標準出力") --> #(230 168 15…
DoubleArrayシリーズ(?)の続き。 今回は、insert関数の処理速度を改善する。 改善点 前回の実装では、insert関数の処理速度がもの凄く遅かったが、その原因はinsert関数の中(の関数の中)で呼び出されているx-check関数にある。 この関数は、簡単に云えば(要…
最近は少し忙しいので、気分転換を兼ねて簡単な関数を実装する。リストの破壊的なリバース。 以下、ソース。 参照: nlet (defun list-reverse! (lst) (nlet self ((lst lst) head) (if (endp lst) head (self #1=(cdr lst) (progn (setf #1# head) lst))))) …
alpha-char-p関数が自分の予想外の挙動をするのを発見。(確認したのは、sbclとclisp) ;; 予想通り > (alpha-char-p #\a) --> T ;; これも > (alpha-char-p #\0) --> NIL ;; 予想外 > (alpha-char-p #\あ) --> T 別に「アルファベット」が、aからzまでの文字…
あまり好きなわけではないのだが、諸々の事情によりsql(特にmysql)を使わなければならないことが結構あるので、開発補助用のマクロを定義しておく。 (require :clsql) ;; DBに接続(DBの各種情報はハードコーディング) (defmacro with-db (&body body) `(clsq…
SBCLでマシンコードを直接実行で作成したstring-to-alien-functionマクロを使って少し遊んでみる。 SBCL: sbcl-1.0.28-x86-linux-binary.tar.bz2 まずは、指定されたメモリの内容を出力する関数を定義。 ※ もともとは、文字列を出力する関数のつもりだったが…
今日作成したデーモンサーバ作成モジュールを使って、HTTP通信を通して送信されたコマンドを実行するデーモンサーバを実装する。 この記事のものとは少し異なるが、そもそもデーモン用のモジュールを作成したのは、コマンド実行サーバを作りたかったから。 …
以前に書いた『HTTPリクエストの中身を表示するだけのHTTPサーバ』を拡張して、デーモンサーバを作成する機会があったので、それをまとめてpackage化した。 プロセス(サーバ)をデーモン化すること自体は、以下のような処理で出来た。 (require :sb-posix) (d…
今日たまたま見つけた『(Sather を試そう) 1. Sather vs C++: 実行速度の比較』*1というページに触発され、lisp(sbcl-1.0.28)でも同様の比較を行ってみた。 C++のソースコードは、上記ページのものと同様だが、g++のオプションには'-O3'を渡している。 実行…
最近のバージョンのSBCL*1では、処理速度を最優先にする宣言を行って関数をコンパイルした場合でも、デフォルトではコンパイラノート*2が表示されないことがある*3。 そのため、最適化を確実に行いたい場合は、コンパイラノートを出力するように明示的に宣言…
DoubleArrayでの実験用にハフマン符号化を実装。 ※ここの続きでもある ハフマン符号化は、本で良く目にしてはいたのだが、これまで実装したことはなかった。 実際にやってみると案外簡単で、大体以下の四ステップで実装できた。 1. 入力文字列中の各文字の出…
たまに、(正確な用語ではないが)オブジェクトごとに一意なIDを取得したいことがある。 Cで云うポインタがあれば、それが適切なのだが、common lispにはポインタを取得する方法は定義されていない(と思う)。 ただ、SBCLに限れば、ポインタ(アドレス)を取得す…
ちょっとヒープ(優先順位付きキュー)を使いたくなったので、実装。とりあえずは、実装が簡単な(かつ性能が良いらしい)pairing-heapを選択。一群の関数は、後で他のものに変更しやすいようにpackageにまとめておく。 ;;; package (defpackage :pairing-heap (…
どこかで、sbclでメモリ領域に直接マシンコードを書き込んで実行できる、というような話を読んだような気がするので試してみた*1。 まずは、(マシンコードを取得するために)実行したい関数をCで定義する。 簡単なものがいいので、二つの変数を足すだけの関数…
DoubleArray(1)で実装したDoubleArrayのテストも兼ねて、文字のエンコーディング方法の違いによって、どれくらい処理速度やサイズに差が出るのかを簡単に調べてみる。それぞれを厳密に比較しているわけではないので、特に正確な情報が得られるわけではないが…
タイトルの通りのHTTPサーバを作成。 というか、ほとんど何も行っていないので、HTTPサーバとは云えないような気もする...。 ソースコード (require :sb-bsd-sockets) (use-package :sb-bsd-sockets) ;; 定数 (defconstant CRLF (coerce '(#\Return #\Newlin…
しばらくDoubleArrayでいろいろ試してみようと思っているので、今日はそのベースとなるソースコード(+覚え書き)を掲載。 『An Efficient Implementation of Trie Structures』*1を参考に実装した。 前置き DoubleArrayの簡単(かつテキトウ)な説明。 Trieの実…
可変配列マクロ(?)の最新版。 index部分もS式で指定可能に。ex. @array#(+ 1 1) エラーチェックとかが適当なのは、以前のものと同様。 ※ @array#(incf i)などのように式は、(incf i)が二度評価されてしまうので注意が必要 (defmacro assure-access (vector i…
アナフォリックマクロをpackageに分けて使う場合のメモ書き。 カレントパッケージで、定義・使用する場合 (defmacro a.when (expr &body body) `(let ((it ,expr)) (when it ,@body))) > (a.when (member 2 '(1 2 3)) (car it)) --> 2 特に問題なし。 定義と…
HTMLパーサのところで、パース結果のlistをcl-whoに渡せば、HTML文字列が生成できるということを書いたが、整形されていなくても良いなら、変換処理自体はpretty-printを使って*1簡単に実装できる。 準備 参照: nlet ;; 型定義: car部がkeywordならHTMLリス…
今試していることで可変の配列が使いたくなったので、用意。 ;; indexが(length vector)の範囲を越えている場合は、自動で配列を拡張 ;; vectorはsymbolである必要がある (defmacro assure-access (vector index) `(locally (declare ,@(if (symbolp index) …
昨日のブログにあるHTMLパーサを試していたら、(組み込みのものではない)read-xxx系関数がボトルネックとなっていることが分かったので、修正する。一番、大きな影響を与えていたのは、この関数(若干簡略化)。 ;; (funcall fn c)がtになるまで、文字列を読み…
HTMLパーサは、たまに使いたいと思うのだが、なかなか良さそうなのが見つからないので、自分で作ることにした。ソース: html2list(0.0.2) 行数は250行くらいで、依存packageはcommon-utils。 とりあえず、行儀良く(?)書かれているHTMLは、だいたいちゃんとパ…
バイト列を文字列に変換したい時には、sbclではsb-ext:octets-to-stringという関数を使えば良いのだが、これはそのままでは、文字コードの解釈に部分的にでも失敗するとバイト列全体の変換が失敗するという難があった*1。 バイト列のデコードに失敗した場合…
N-Queen問題を、いくつかの方法で解いてみる。とりあえず、一番簡単・簡潔だと思うのは、次のコード。 参照: nlet-acc ;; row番目に新たなqueenを置けるかチェック (defun check (row queens &optional (r 1)) (or (null queens) (and (/= (car queens) row …
良く使うユーティリティ関数・マクロの定義などを書くことにする。*1 一つ目はこれ。 【定義】 (defmacro nlet-acc (fn-name letargs &body body) (let (acc (gensym)) `(let ((,acc '())) ; acc: 結果蓄積用のlist ※1 (flet ((accumulate (x) (push x ,acc)…
