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

クイックソートの内部ループ

クイックソートの内部ループには(自分が知っている限りでは)二種類あるな、とふと思ったので、思い出して書いてみた。 ;;; 補助マクロ/関数 ;; whileループ (defmacro while (exp &body body) `(loop WHILE ,exp DO (locally ,@body))) ;; 配列をシャッフル …

HAMT: 実装してみた感想等

HAMT(Hash Array Mapped Trie) - sileの日記の続き。 前よりはちゃんとしたものを実装したので、それをうけての感想など。 作成物: hamt-0.2.0 前回からの相違点 基本的には『Ideal Hash Trees』*1に合わせた実装に修正*2。 変更点を挙げると、 HAMTのエント…

構造体のスタックへの割り当て

SBCLのマニュアル(ver 1.0.37)にも書いてあることだけど ... 。 通常は構造体のインスタンスを作成するとヒープ上にそのための領域が割り当てられる。 これには(おそらく)ヒープ割り当て+GC処理のコストが伴うので、構造体としてまとめるよりも、その各フィ…

HAMT(Hash Array Mapped Trie)

『Ideal Hash Trees』*1という論文を(必要なところだけ、だいたい)読み終わったので、そのメモ等。 概要 AMT(Array Mapped Trie)という基盤的なデータ構造を使って、ideal(nearly ideal)なHash Treesを作ろう、というような話。 AMTの応用例として、以下のよ…

短いマクロ定義でシンボル補足を避けるための簡単な方法

シンボル補足を避けるためにたまに使う方法。 uninternされたシンボルとリードマクロのラベル付け/参照機能を併用。 ;; uninternされたシンボル ;; 印字名が同じでも実体は異なるので、衝突は起きない (eq '#:var '#:var) --> NIL ;; #n=および#n#構文を使え…

Packrat Parsing

『Packrat Parsing: Simple, Powerful, Lazy, Linear Time』という論文の流し読みが終わったので、現状での理解を軽く書いておく。 概要 ※ 以下、テキトウな理解なので、間違っている可能性有り Packrat Parsingというパース手法。 再帰下降型の一種。 再帰…

Packrat Parsing: 遅延版

前回の実装ではメモ化をハッシュテーブルを用いて実装していたが、それを論文*1に合わせて遅延実行を利用するものに修正。 こっちの方が(あらかじめ入力テキストの各位置に対して、遅延されたパーサ関数実行を用意しておく必要があるが)メモ化によって既に計…

スキップリスト

スキップリスト(Wikipedia)を実装してみた。説明等は一切抜きでコードだけ。 (defpackage skiplist (:use :common-lisp) (:shadow :common-lisp get rem) (:export *p* make get rem)) (in-package :skiplist) ;;;;;;;;; ;;;; 宣言 (declaim (inline make-no…

行をバイト列として読み込む

テキストファイルの各行をバイト列として読み込むマクロを定義。 SBCL等のように文字列を内部的にユニコードとして表現している処理系では、テキストファイルを読み込む際、そのファイルが不正なバイト列を含んでいると読み込みに失敗することがあるので、そ…

UNF: Common Lisp版

しばらく(私的には)プログラミングから離れた生活が続いていたので、肩慣らしを兼ねてUNF(Unicode正規化ライブラリ)のcommon lisp版(cl-unf)を作成。いつものようにSBCLで作成し、SBCL向けに最適化されているが、UTF-32に対応しているなら、他の処理系でも一…

jada: 二バイトコード(UTF-16)を用いてDoubleArrayを構築する際の最適化メモ

前回からだいぶ間が空いたけど、jadaで試したことのメモ。 二バイトコード Javaは文字を二バイトコード(UTF-16)で表現しているので、jadaで実装されたトライの各ノードで(遷移に)用いられるコード値の最大値も0xFFFFとなっている。 トライの遷移コードが一バ…