common lisp

RustとSBCLでのDAWG構築性能の比較メモ

Rustの勉強を兼ねて、cl-dawgというDAWGのCommon Lisp実装を移植して、rust-dawgというライブラリを作ってみた。 (DAWGは末尾部分を共有可能にしたトライの亜種。上記ライブラリでは、そのトライ木をDoubleArray形式で表現している。DAWGやDoubleArrayの構築…

ソート済みのリストに対する破壊的マージソートの改良

以前に載せたマージソート(をベースとしたもの)をSBCL(1.0.58)にコミットしてくれたPaul Khuongさんが、こんな記事を書いていて、なるほどなー、と思ったので、表題に関係する部分を参考にさせて貰って変更前後での比較を行ったメモ。 オリジナルのマージソ…

Lock-Free Queue

compare-and-swap操作を用いたロックフリーなキューの実装。 SBCLでのみ動作*1。 (defpackage lock-free-queue (:use :common-lisp) (:export queue make enq deq empty-p element-count to-list)) (in-package :lock-free-queue) ;; compare-and-swap: 成功…

エラトステネスの篩

loop*1を使って、エラトステネスの篩を実装してみたメモ。 以下、処理系にはSBCLのver1.0.54(x86-64bit)を使用。 ;; 引数nまでの範囲の素数のシーケンス(ジェネレータ)を作成する (declaim (inline make-prime-sequence)) (defun make-prime-sequence (n) (l…

ループ処理を関数型っぽく書いてみる(2)

前回の続き。 githubにあるloopの簡易版を載せておく。 基本的な考え方 基本的なJava等のIteratorと似た*1インタフェースを通してループ処理を実現している。 異なるのは全ての関数をinline展開可能にすることで、同等のループを非関数型的に書いた場合と同…

ループ処理を関数型っぽく書いてみる(1)

今週は、common lispでループ処理を関数型っぽく、かつ効率良く実装できるかどうかを試していたので、その結果を載せておく。 結論から云えば、処理系の十分な最適化を期待できれば、関数型っぽく書いても、手続き型的に書いた場合と比肩しえる性能が得られ…

逆FizzBuzz

逆FizzBuzz問題 (Inverse FizzBuzz)というものがあるのを知ったので解いてみた。 結構力技。 あと、本当に合っているかは不明。 ;; 逆FizzBuzzを解く関数 ;; listは fizz,buzz,fizzbuzz のいずれかを要素に持つリスト ;; ;; 処理内容は、 ;; - 1: 開始数値を…

簡易スタック型VM(JITコンパイラもどき)でのフィボナッチ数計算速度

前々々回でスタック型言語をバイトコードにコンパイルする部分を、前々回でCommonLispアセンブラによるマシン語生成を、前回でそのアセンブラ上にスタック型言語のラップするところを扱った。 今回はそれらをまとめて、最初に作成したバイトコードインタプリ…

CommonLispアセンブラ上にスタック型言語(っぽいもの)

前回のCommonLispアセンブラを使って、アセンブラ上に簡単なスタック型言語(っぽいもの)を組み立てて、それを使ってフィボナッチ数を計算するプログラムを書くと、どのような感じになるかを試してみた。 cl-asmはバージョンを更新して0.0.2を使用*1。 0.0.1(…

アセンブリ言語でフィボナッチ数

前回は、C++で単純なVMを書いて、その上でのフィボナッチ数の計算時間を測定した。 そのVM部分をネイティブコードに置き換えたら、どの程度処理速度が改善するのかを測ってみたかったので、その前にまずネイティブコード(x86)の勉強も兼ねて、common lispで…

簡易スタック型VM(バイトコードインタプリタ)でのフィボナッチ数計算速度

今年はlisp系のプログラミング言語(及びその処理系)を作ってみようと考えていて、かつ(少なくとも)当面の間はスタック型VMを基盤として実装していくことになると思われるので、まずは単純なスタックマシンのバイトコードインタプリタで、どの程度の処理速度…

fletとlabels

CommonLispのfletとlabels的なものを(あらかじめ使えるものはlambdaしかない状況で)自分で実装する必要が出てきたので、その際のメモ。 なお、以下では煩雑になるためfuncall呼び出しの記述を省略している(実際にはScheme処理系で動作確認を行っていた)。 le…

マインスイーパー

端末上で動作するマインスイーパーをCommonLisp(SBCL)で実装してみた。 github: cl-mine-0.0.2 端末操作 端末操作部分のソースコードは以下のような感じ。 基本的には端末のエスケープシーケンスで(カーソル移動や画面クリア、文字色等の)制御を行っている。…

N-Queen: 高速化

こちらの記事に刺激を受けて、以前に実装したN-Queenを高速化してみた(Common Lisp版のみ)。 (defvar *fastest* '(optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0))) (deftype max-board-size () '(mod #x100)) (declaim (inline check)) ; …

文字列/バイト列用のハッシュ関数ライブラリ

A Hash Function for Hash Table Lookupに載っているハッシュ関数(Jenkins Hash)をCommon Lispで実装した。 github: jenkins-hash(0.0.2) 作成の主な動機は以下の二つ: SBCLにはバイト列用のハッシュ関数がない *1 一つのキーから複数のハッシュ値を得たい場…

N-Queen (Haskell + Common Lisp)

Etsukata blog: Haskellでlist monadを使ってN-Queens問題を解いてみました を見たのをきっかけに久しぶりにN-Queen問題を解くプログラムをHaskellで書いてみた。 ---- ファイル名: nqueen.hs ---- コンパイル: ghc -O2 -o nqueen nqueen.hs # Glasgow Haske…

マージソート(3): 高階関数呼び出し最適化

マージソート(1)の改良版。 ソートのような高階関数では、引数で渡した比較関数の間接呼び出しのコストも実行速度にそれなりの影響を与えるので、それを(マクロをほとんど使わずに)できるだけ低く抑えるための試み。 比較関数最適化 まず、比較関数自体の実…

マージソート(2): 要素数が少ない部分リストの特別扱い

昨日に作成したマージソートに手を加えたもの。 要素数が少ない部分リスト*1には、(再帰的な)マージソートではなく、ソーティングネットワーク的なソートを適用することで高速化を図った。 けど、結果的にはほとんど効果がなかった。 計時 まず計測結果から…

マージソート(1)

久々にマージソートを実装してみたら、結構良いものができたので載せておく。 まずはパッケージ定義とグルーバルな宣言。 ;;;; SBCL-1.0.51 (x86-64) (defpackage merge-sort (:use common-lisp) (:shadow :common-lisp sort) (:export sort)) (in-package :…

Forthでハノイの塔

Forthを触ってみたくなったので、試しにハノイの塔を実装してみた。 ついでにcommon lispとC++でも実装し、Forthとの処理速度を比較してみた。 ※ common lispの処理系にはSBCLを、Forthの処理系にはgforth及びVFX-Forthを使用した Forthでの実装(gforth) gfo…

ソート済みファイルからO(1)のメモリ使用量でDoubleArrayを構築する方法 #APPENDIX

前半および後半で実装を省略していたパッケージのソースコードをここに載せておく。 buffered-outputパッケージとnode-allocatorパッケージの二つ。 buffered-output ランダムアクセス可能なバイナリファイル出力用のパッケージ。 DoubleArray構築時に使われ…

ソート済みファイルからO(1)のメモリ使用量でDoubleArrayを構築する方法 #後半

昨日の続き。 今回は主に、前回のtrieパッケージでは未定義だったchange-active-node関数を埋めていくことになる。 ※ ちなみに今回は'後半'となっているけど、まだ後続がある・・・。詳しくはソースコード内のコメントを参照。 実装: DoubleArray構築パッケ…

ユニコード文字列をバイトストリームとして扱うためのパッケージ

タイトル通りのパッケージ。 実装の前に使用例。 ;;;; sbcl-1.0.49 ;; 例で使用する文字列(および対応するバイト列) (sb-ext:string-to-octets "下書き") --> #(228 184 139 230 155 184 227 129 141) ;; 作成 (defparameter *in* (octet-stream:make "下書…

ソート済みファイルからO(1)のメモリ使用量でDoubleArrayを構築する方法 #前半

格納するキー数に大してO(1)のメモリ使用量で、DoubleArrayを構築する方法を思いついたので、その実装メモ。 今回はその前半。 いきなりDoubleArrayの実装を行うとやや複雑となるので、まずはより単純な通常のトライ(オンメモリ)の実装から始める。 基本的な…

ジェネレータっぽいものを使ったループ

ジェネレータを使ったループっぽいものをcommon lispで実装してみた。 実装は適当で制限も多いけど、処理効率は(通常のループと同程度に)良い。まず動作例。 ;; 1: ".profile"の各行を出力する (for (x (each-line ".profile")) (print x)) "# ~/.profile: e…

ネイティブバイトオーダー取得ユーティリティファイル

マシンのネイティブのバイトオーダーを自動的に判定できるユーティリティ関数があると便利かと思ったので作成してみた。 ;# <- バイトオーダー判定用文字列 ;; ファイル名: byte-order.lisp (defun guess-byte-order (sample-file) (with-open-file (1byte s…

All the common prefixes

『Pearls of Functional Algorithm Design』の15章「All the common prefixes」に目が止まったので、その要件を満たすものをcommon lispで実装してみたメモ(かなり雑)。以下、15章の冒頭から引用した「All the common prefixes」の概要。 Let llcp xs ys den…

Gomoku: 辞書込みの形態素解析器

IgoをベースにしてJARファイルに辞書データを同梱した形態素解析器を作成した。 名前は同系統のGomoku(ver 0.0.1)。 特徴 開発コンセプト(?)は「JARファイルのみで形態素解析」と「サイズを(比較的)小さく」の二点。 このJARファイル一つで形態素解析が行え…

昇順数値列のunary表現と定数時間アクセス

数値列の圧縮に関するメモ書き。 サンプル数値列 要素が昇順に並んだ数値列があるとする。 (defvar *numbers* #(0 1 2 4 5 8 9 10 11 14)) 前準備: 差分列への変換 このような数値列を圧縮する場合は、その前準備として、もともとの数値列を各要素間の差分を…

SA-IS: SuffixArray線形構築: 訂正

以前に書いたSA-ISの記事(及びソースコード)には明確な間違いがあったので訂正しておく。 間違い 確か以前の記事では「入力文字列の各LMS部分文字列が互いにユニークなら、初めのinduced-sortを終えた段階でSuffixArrayが求まる」というようことを何箇所かで…

SA-IS: SuffixArray線形構築

『Linear Suffix Array Construction by Almost Pure Induced-Sorting』*1という論文を参考にして、Induced-Sortingを用いたSuffixArrayの線形構築アルゴリズム(SA-IS)をCommon Lispで実装した。 以下、そのソースコードとメモ書き。 線形構築 汎用ソートア…

ゼロ次元配列

common lispではゼロ次元の配列が作れることを知った。 ;; dimentionsに空リストを渡して配列を作成するとゼロ次元配列となる (make-array '()) --> #0A0 (aref *) --> 0 (make-array '() :initial-element "string") --> #0A"string" (aref *) --> "string"…

B木: バランス具合

前回のB木の実装中にはほとんど気にしていなかったけど、どうやらB木は挿入のみなら常にバランス状態を維持できるようになっているようだ(おそらく)。 今回はB木のバランス具合を確かめるために試したこと(+考えたこと)のメモ。 ※ いつもの通り正しくない可…

B木

B木をWikipediaの記事*1を参考にしてcommon lispで実装してみた。 実装 実装コード。 コメント抜きで140行程度。 オンメモリ。最適化なし。 ※ 末尾に全部まとめた(+ コメント無し)のソースコード有り ;;;; パッケージ定義 (defpackage btree (:use :common-l…

erlterm: Erlang項とCommon Lispオブジェクトの相互変換

Erlang -- External Term Formatを参考にして、Erlangの項(のバイナリ表現)とCommon Lispのオブジェクトを相互変換するライブラリを作成。 ・erlterm-0.0.1 ポートを用いた外部接続での利用を想定。 細かい作り込みや最適化はまだまだだけど、一応一通りの変…

浮動小数点数のIEEE754形式への変換

倍精度浮動小数点数をIEEE754形式のビット表現(整数値)にエンコードする方法。 (defun encode-double-float (float) (declare (double-float float)) (multiple-value-bind (fraction exponent sign) (integer-decode-float float) (let ((code 0)) (setf (l…

llvm: ビットコードのデコード

LLVM Bitcode File Format — LLVM 3.4 documentationを読んでllvmのビットコードをデコード(パース)してみたので、そのメモ(あくまでも個人用メモ。用語とかは結構自分の好き勝手に書いているので、ちゃんと知りたい人はオリジナルのドキュメントを参照のこ…

DAWG2(2): ソート済みファイルからのDAWG構築

前回はトライだったけど、今回はDAWGを構築。 Nをキーセットに含まれる文字の総数*1だとして、DAWGはトライと同様にO(N)で構築可能(多分間違っていないはず...)。 ただし、子ノード(サブトライ)が共有可能かどうかの判定が入るので、実際には一桁程度遅くな…

DAWG2(1): ソート済みファイルからのトライ構築

七月にやっていたDAWG(Direct Acyclic Word Graph)シリーズ(?)の続き。 結構長い間中断していて自分でも内容がうろ覚えなので、仕切り直してもう一度。 今回はDAWGの前段階として、ソート済み(かつ各行がユニーク)なファイルからトライを構築する。 DAWG 軽…

dict: ハッシュテーブル

前回にErlangで作成したhashtrieをcommon lispに移植していたら、いつのまにかただのハッシュテーブルになっていた。 もともとはHAMTから始まったはずなのに...。ソースコード等: dict-0.0.1 実装 キー衝突時にAMTを使わないで、リンクリストを使うHAMT。 初…

マルチキークイックソート

「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも…

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

クイックソートの内部ループには(自分が知っている限りでは)二種類あるな、とふと思ったので、思い出して書いてみた。 ;;; 補助マクロ/関数 ;; 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のエント…

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に対応しているなら、他の処理系でも一…