2009-08-01から1ヶ月間の記事一覧
最近は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>…
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))))) …
