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が求まる」というようことを何箇所かで…