2012-10-08-01-アルゴリズムとクロージャと - 2
>> Site top >> weblog >> 月別アーカイブ >> 2012年10月のlog >> 2012-10-08-01-アルゴリズムとクロージャと - 2
最終更新日付:2012/10/08 01:00:00
アルゴリズムとクロージャと - 2
2012 年 10 月 08 日
先日書いた、リストを直接扱うアルゴリズム。これの for_each 版は以下のようなものだった。
(defun for-each (seq func) (labels ((list-imp (lst) (if (null lst) nil (progn (funcall func (car lst)) (list-imp (cdr lst))))) (array-imp (idx cnt) (if (<= cnt idx) nil (progn (funcall func (aref seq idx)) (array-imp (1+ idx) cnt))))) (cond ((listp seq) (list-imp seq)) ((arrayp seq) (array-imp 0 (length seq))) (t (error "not a sequence.")))))
で、クロージャを使って反復子を表現できるなと気付いたという話だった。詳細は後述するとして、それを使うと for_each はざっくり以下のようになる。
(defun for-each2 (itr1 itr2 func) (labels ((imp (itr) (if (iterator:is-equal itr itr2) nil (progn (funcall func (iterator:get-value itr)) (iterator:move-next itr) (imp itr))))) (imp (iterator:clone itr1))))
反復子を操作する is-equal, get-value, move-next などはパッケージ iterator に入っている。これらは CLOS の総称関数のように見えるが、そうではない。反復子はあくまで(現時点では)クロージャだ。これらの操作は、実装を生温く隠蔽するためのマクロに過ぎない たとえば、get-value は以下のようなマクロになっている。
(defmacro get-value (itr) `(funcall ,itr :get-value))
つまり、クロージャである反復子に :get-value というシンボルを渡すことで値を取得するわけだ。他の操作も同様である。そのようなクロージャを作成する関数のリスト版は、例えば以下のようになっている。
(defun list-iterator (cons) (lambda (op-type &optional param) (case op-type (:is-equal (eq cons (funcall param :__get-cons))) (:move-next (setq cons (cdr cons))) (:get-value (car cons)) (:set-value (setf (car cons) param)) (:clone (list-iterator cons)) (:__get-cons cons) (t (error "invalid op-type.")))))
つまり、実行時に渡したシンボルによって処理を分岐させている。これがパフォーマンス的に問題がありそうなのは百も承知だ。とりあえず、これでどれくらいパフォーマンスに差がでるのか、ひとまず試してみた。要素数 10 のリストを用意し、for-each で要素を反復して単純な関数に処理させるというのを 10,000 回繰り返して時間を計測する。
(setq seq '(0 1 2 3 4 5 6 7 8 9)) (setq func (lambda (x) (1+ x))) (time (do ((i 0 (1+ i))) ((> 10000 i) nil) (for-each seq func)))
Real time: 0.28125 sec. Run time: 0.281 sec. Space: 840724 Bytes GC: 1, GC time: 0.047 sec. NIL
(time (let ((itr1 (iterator:list-iterator seq)) (itr2 (iterator:list-iterator nil))) (do ((i 0 (1+ i))) ((> 10000 i) nil) (for-each2 itr1 itr2 func))))
Real time: 0.46875 sec. Run time: 0.469 sec. Space: 1280924 Bytes GC: 2, GC time: 0.094 sec. NIL
どうやら、クロージャを使用した反復子はリストを直接扱うよりも 1.6 倍ほど遅いようだ。正直 Lisp の経験が浅いので、これが「どれくらいマズいのか」も良くわからない。そもそも、リストを直接扱うバージョンでも Space: 840724 Bytes というのには驚いている。しかし、ひとまず改善の余地がありそうだと思うことにしよう。
別の策を考えてみるとしようか‥‥‥それはまた次回。
コメント
g000001 - 10/10/2012 11:16:38 AM
Kagelow IMAWAYA - 10/10/2012 06:22:14 PM
コメントありがとうございます。Lisp の方からコメント頂けるとは、うれしいやら恥ずかしいやら。
なるほど、CLISP がバイトコードコンパイルなのは理解していましたが、そこまで違うものなんですね。そして、declare なんかによる最適化もあまり効果がない、と。
本気で速度が必要な時は C/C++ を使っているのですが、やっぱり SBCLなんかも使ってみたいですね。調べてみます。
たぶん、しばらくは CLISP で迷走を続けると思いますが。(笑
このページのタグ
Page tag : Common Lisp
Copyright(C) 2005-2021 project-enigma.
Generated by CL-PREFAB.
こんにちは、お使いの処理系はCLISPのようですが、CLISPはインタプリタ動作なので関数をコンパイルすると少し速くなるかなと思いました
コンパイル後:
コンパイル前:
ちなみに、SBCLという処理系がありますが、こちらはネイティブコードコンパイラで基本的になんでもコンパイルし、速度は
になります。特にチューニングしなくても20倍位速いです。(少しチューニングするとさらに倍位になります)
CLISPは移植性を重視していて速度はそれ程でもありません。また、型宣言等もそれ程効きません(仕様で宣言等は処理系のポリシーによっては無視しても問題ないため)スピード重視の場合は、SBCLや、CCL、Allegro CL等が好まれることが多いようです。
http://cl.cddddr.org/index.cgi?%E5%87%A6%E7%90%86%E7%B3%BB%3A%E9%81%B8%E3%81%B3%E6%96%B9%E3%81%AE%E7%9B%AE%E5%AE%89