ループ処理を関数型っぽく書いてみる(2) - sileのブログ
前回の続き。 githubにあるloopの簡易版を載せておく。 基本的な考え方 基本的なJava等のIteratorと似た*1インタフェースを通してループ処理を実現している。 異なるのは全ての関数をinline展開可能にすることで、同等のループを非関数型的に書いた場合と同じくらいに、コンパイラが最適化を行ってくれることを期待していることくらい。 後は、SBCLの最適化の制限上、構造体等は使用せず、極力lambdaで全てを表現するようにしている。 実装 まず、loopパッケージ用のシーケンス生成関数。 ;; 数値の範囲を表現するシーケンス (declaim (inline from)) (defun from (start &key to (by 1)) ; toがnilなら無限シーケンス ;; 全体をlambdaで囲む。このlambdaの呼び出しがシーケンスの初期化処理に相当する。 (la
ループ処理を関数型っぽく書いてみる(1) - sileのブログ
今週は、common lispでループ処理を関数型っぽく、かつ効率良く実装できるかどうかを試していたので、その結果を載せておく。 結論から云えば、処理系の十分な最適化を期待できれば、関数型っぽく書いても、手続き型的に書いた場合と比肩しえる性能が得られそうな感じだった。 成果物 作ったもの: loop 今回はこれの使用例とベンチマーク結果を、次回は実装方法を載せる予定。 使用例 シーケンス(or 無限シーケンス)とmapとかfilterとかを組み合わせてループを表現する。 ;; 1から5までの数値を表示する > (loop:each (lambda (n) (print n)) (loop:from 1 :to 5)) 1 2 3 4 5 => NIL > (loop:from 1 :to 5) => #<CLOSURE (LAMBDA () :IN LOOP:FROM) {10030E0E
マインスイーパー - sileのブログ
端末上で動作するマインスイーパーをCommonLisp(SBCL)で実装してみた。 github: cl-mine-0.0.2 端末操作 端末操作部分のソースコードは以下のような感じ。 基本的には端末のエスケープシーケンスで(カーソル移動や画面クリア、文字色等の)制御を行っている。 ただ、キー入力をリアルタイムで取得可能にするのはエスケープシーケンスでは無理そうだったので、その部分はtcsetattr等のシステムコール(?)を使用している。 (defpackage console (:use :common-lisp :sb-alien) (:shadow :common-lisp format) (:export with-raw-mode clear move set-pos format newline formatln style)) (in-package :console) ;
マージソート(3): 高階関数呼び出し最適化 - sileのブログ
マージソート(1)の改良版。 ソートのような高階関数では、引数で渡した比較関数の間接呼び出しのコストも実行速度にそれなりの影響を与えるので、それを(マクロをほとんど使わずに)できるだけ低く抑えるための試み。 比較関数最適化 まず、比較関数自体の実行コストを下げるために、汎用的な数値比較関数ではなく、より特殊化されたものを使用するようにする。 ;; fixnum用の比較関数 (define-symbol-macro fixnum< (lambda (x y) (declare (fixnum x y)) (< x y))) ;;; fixnum< を使用した場合の処理時間 ;;; ;;; 大量データのソート速度 ;;; 100万要素のリストが対象 (sb-sys:without-gcing (let* ((data (loop REPEAT 1000000 COLLECT (random 1
マージソート(1) - sileのブログ
久々にマージソートを実装してみたら、結構良いものができたので載せておく。 まずはパッケージ定義とグルーバルな宣言。 ;;;; SBCL-1.0.51 (x86-64) (defpackage merge-sort (:use common-lisp) (:shadow :common-lisp sort) (:export sort)) (in-package :merge-sort) (declaim (inline halve merge-lists) (optimize (speed 3) (debug 0) (safety 0))) ユーティリティ関数とマクロ。 ;; 整数nを二分割する関数 ;; => (values n1 n2) ;; ;; nが奇数の場合は (= (1+ n1) n2) となる (defun halve (n) (declare (fixnum n)) (mu
SA-IS: SuffixArray線形構築 - sileのブログ
『Linear Suffix Array Construction by Almost Pure Induced-Sorting』*1という論文を参考にして、Induced-Sortingを用いたSuffixArrayの線形構築アルゴリズム(SA-IS)をCommon Lispで実装した。 以下、そのソースコードとメモ書き。 線形構築 汎用ソートアルゴリズムと今回実装したSA-ISアルゴリズムでのSuffixArray構築時間の簡単な比較。 百文字〜一千万文字の文字数のテキストを入力として与えて、その構築時間を計測。 百文字千文字一万文字十万文字百万文字一千万文字 汎用ソート*20.000 sec0.002 sec0.023 sec0.358 sec5.604 sec94.196 sec SA-IS0.031 sec0.120 sec0.135 sec0.335 sec2.580 sec2
B木 - sileのブログ
B木をWikipediaの記事*1を参考にしてcommon lispで実装してみた。 実装 実装コード。 コメント抜きで140行程度。 オンメモリ。最適化なし。 ※ 末尾に全部まとめた(+ コメント無し)のソースコード有り ;;;; パッケージ定義 (defpackage btree (:use :common-lisp) (:shadow :common-lisp get set remove) (:export make ; B木作成 get ; 検索および挿入(setf (get ...)) remove)) ; 削除 (in-package :btree) ;;;; 補助関数群 ;; 常にnilを返す (defun return-nil (&rest _) (declare (ignore _)) nil) ;; 常に三番目の引数を返す (defun identity3 (_1 _
マルチキークイックソート - sileのブログ
「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも性能が低下しにくい クイックソート + 基数ソート、のような感じ？ ソート方法 基本的には通常のクイックソートと似ていて「ピボット要素*1を選んで、配列を分割する」といったことを繰り返す。 ただし、クイックソートは各段階で配列を二分割(ピボット要素よりも大きいか小さいか*2 )し、そのための比較には要素(文字列)全体を用いるのに対して、マルチキークイックソートでは、配列は三分割(ピボット要素よりも大きいか小さいか、それとも等しいか)され、そのための比較には文字列全体ではなく(各段階で)一文字のみ、が用いられ
クイックソートの内部ループ - sileのブログ
クイックソートの内部ループには(自分が知っている限りでは)二種類あるな、とふと思ったので、思い出して書いてみた。 ;;; 補助マクロ/関数 ;; whileループ (defmacro while (exp &body body) `(loop WHILE ,exp DO (locally ,@body))) ;; 配列をシャッフル (defun shuffle (ary) (loop REPEAT 2 DO (loop FOR i FROM 0 BELOW (length ary) DO (rotatef (aref ary i) (aref ary (random (length ary)))))) ary) ;;; クイックソート１ ;;; 内部ループ: ;;; - 配列の前方と後方から不正な要素を探して、見つかった場合は互いを交換する、ということを繰り返す (defun qsort1
行をバイト列として読み込む - sileのブログ
テキストファイルの各行をバイト列として読み込むマクロを定義。 SBCL等のように文字列を内部的にユニコードとして表現している処理系では、テキストファイルを読み込む際、そのファイルが不正なバイト列を含んでいると読み込みに失敗することがあるので、その対処として。 ;;;; エラーの例 ;;;; sbcl-1.0.40 ;;;; ;; 普通の行読み込みマクロを定義 (defmacro each-file-line ((line filepath) &body body) `(with-open-file (#1=#:in ,filepath) (loop FOR ,line = (read-line #1# nil nil) WHILE ,line DO (progn ,@BODY)))) ;;;; ;; 不正なバイト列を含むテキストファイルの作成 (with-open-file (out "s
構造体のスタックへの割り当て - sileのブログ
SBCLのマニュアル(ver 1.0.37)にも書いてあることだけど ... 。 通常は構造体のインスタンスを作成するとヒープ上にそのための領域が割り当てられる。 これには(おそらく)ヒープ割り当て＋GC処理のコストが伴うので、構造体としてまとめるよりも、その各フィールドを個別に扱った方が、パフォーマンス的には有利だったりする。 ;; sbcl-1.0.40 ;; ;; 構造体のインスタンス作成のコストを測るためプログラム ;; 範囲を表す構造体 (defstruct range start end) ;; 範囲をランダムに複数生成し、それらの距離の合計値を求める ;; 1) 構造体を使う場合 (time (let ((total 0)) (loop REPEAT 1000000 DO (let ((r (make-range :start (random 100) :end (rando
アナフォリックマクロとpacakge(2) - sileのブログ
半年くらい前に書いた「アナフォリックマクロとpacakge」の続き。この方法だとダメなケースを発見したので、その改善策(?)を考えてみる。 以前の方法 以前の方法は、アナフォリックマクロの定義と使用が別パッケージに分かれる場合に、アナフォリック変数のインターンを使用側パッケージで行う、というようなものだった。 (defpackage :util (:use :common-lisp) (:export a.when)) (in-package :util) (defmacro a.when (expr &body body) `(let ((,(intern "IT") ,expr)) ; ITシンボルは、マクロ展開時に使用側パッケージにインターンされる (when ,(intern "IT") ,@body))) この方法の利点は前回書いた通りなのだが、a.whenマクロを使用する関数が
実行可能ファイル作成補助マクロ(sbcl) - sileのブログ
sbcl(1.0.28)では、実行可能ファイルを作成することができる。 > (sb-ext:save-lisp-and-die "実行可能ファイル名" :toplevel #'エントリ関数 :executable t) エントリ関数には(必須引数の数が0個なら?)どのような関数でも指定可能なのだが、いろいろクセがあるため期待通りに動く関数を一から作成するのは、若干手間取ったりする。 なので、エントリ関数作成用のマクロを作成した。 そこまで汎用的ではないので、その時々で手を加える必要があるとは思うが、テンプレートとしては十分だと思う。 以下コード： ;; パスのファイル名部分を取り出す (defun basename (pathstring) (let ((path (parse-namestring pathstring))) (format nil "~A~@[.~A~]" (pathn
apropos+describe - sileのブログ
aproposとdescribeを一緒にしたような関数を作成。 名前はそのままapropos-desc。 aproposを使えば、シンボル一覧が取得できるが、それに(そのシンボルにバインドしている)関数などの簡単な情報(引数、返り値、ドキュメント)も一緒に表示されるようにした。 基本的には、apropos-listの結果にdescribeを適用しただけだが、sbclの標準のdescribe出力は若干量が多すぎることがあるので、自分に必要な情報だけを出力するようにして、一覧性を上げている。 例 ;; 第三引数までは、apropos関数と同様 ;; "multiple"を含むシンボルをcommon-lispパッケージから探して、その名前と簡易的な情報を表示する。 > (apropos-desc "multiple" :common-lisp t) === multiple-value-bind
alpha-char-pの挙動 - sileのブログ
alpha-char-p関数が自分の予想外の挙動をするのを発見。(確認したのは、sbclとclisp) ;; 予想通り > (alpha-char-p #\a) --> T ;; これも > (alpha-char-p #\0) --> NIL ;; 予想外 > (alpha-char-p #\あ) --> T 別に「アルファベット」が、aからzまでの文字だけを指すわけではないので、上の挙動は適切なのだろうが、何となくこういう関数はa〜z,A〜Zの文字にだけtrueを返す印象があった(Cのisalphaとかの影響か?)。 『Common LISP 第2版』には、alpha-char-pの説明として「標準文字（standard-char-pによって定義されるもの）に対しては文字AからZまでとaからzまでがアルファベットである」(p.331)と書かれているので、(and (standard-c
コンパイラノート表示 - sileのブログ
最近のバージョンのSBCL*1では、処理速度を最優先にする宣言を行って関数をコンパイルした場合でも、デフォルトではコンパイラノート*2が表示されないことがある*3。 そのため、最適化を確実に行いたい場合は、コンパイラノートを出力するように明示的に宣言する必要がある。 (declare (optimize (debug 0) (safety 0) (speed 3) (compilation-speed 0)) ;; ↓これが必要 (sb-ext:unmuffle-conditions sb-ext:compiler-note)) また、これはどうやらdeclaimで宣言した場合は無効で、declareを使う必要があるようだ。 *1:今回試したのは1.0.28 *2:最適化を行うために修正が必要な箇所などを教えてくれる *3:多分compile-file関数でコンパイルを行う場合は、デフォル
可変配列 - 微修正 - sileのブログ
可変配列マクロ(?)の最新版。 index部分もS式で指定可能に。ex. @array#(+ 1 1) エラーチェックとかが適当なのは、以前のものと同様。 ※ @array#(incf i)などのように式は、(incf i)が二度評価されてしまうので注意が必要 (defmacro assure-access (vector index) `(locally (declare ,@(if (symbolp index) `((fixnum ,index))) ,@(if (symbolp vector) `((vector ,vector))) (optimize (safety 0))) (when (>= ,index (length ,vector)) (setf ,vector (adjust-array ,vector (* ,index 2)))) ,vector)) (flet
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ゼロ次元配列 - sileのブログ