2012-10-08-01-アルゴリズムとクロージャと - 2 - project-enigma

2012-10-08-01-アルゴリズムとクロージャと - 2

>> Site top >> weblog >> 月別アーカイブ >> 2012年10月のlog >> 2012-10-08-01-アルゴリズムとクロージャと - 2

最終更新日付:2014/01/02 00: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

こんにちは、お使いの処理系はCLISPのようですが、CLISPはインタプリタ動作なので関数をコンパイルすると少し速くなるかなと思いました

(compile 'for-each)

コンパイル後:
Real time: 0.04453 sec.
Run time: 0.048003 sec.
Space: 1681304 Bytes
GC: 1, GC time: 0.004001 sec.

コンパイル前:
Real time: 0.289555 sec.
Run time: 0.292019 sec.
Space: 9842120 Bytes
GC: 7, GC time: 0.040003 sec.

ちなみに、SBCLという処理系がありますが、こちらはネイティブコードコンパイラで基本的になんでもコンパイルし、速度は

Evaluation took:
  0.002 seconds of real time
  0.000000 seconds of total run time (0.000000 user, 0.000000 system)
  0.00% CPU
  5,706,036 processor cycles
  0 bytes consed

になります。特にチューニングしなくても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

Kagelow IMAWAYA - 10/10/2012 06:22:14 PM

コメントありがとうございます。Lisp の方からコメント頂けるとは、うれしいやら恥ずかしいやら。

なるほど、CLISP がバイトコードコンパイルなのは理解していましたが、そこまで違うものなんですね。そして、declare なんかによる最適化もあまり効果がない、と。

本気で速度が必要な時は C/C++ を使っているのですが、やっぱり SBCLなんかも使ってみたいですね。調べてみます。

たぶん、しばらくは CLISP で迷走を続けると思いますが。(笑

このページにコメントする

 

このページのタグ

Page tag : Common Lisp

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.