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

(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.

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

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

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

このページのタグ

Page tag : Common Lisp

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