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

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

最終更新日付：2014/01/02 00:00:00

アルゴリズムとクロージャと - 5

2012 年 10 月 17 日

「こっちの方が速いだろう」と思うものを試すたびにどんどん遅くなっていく。自信をなくしてしまうような経験だが、それはそれでいつか糧になる、と信じてみよう。今度はCLOS を試してみる。

基本的な考え方は、各種の反復子を defclass して、必要なメソッドを defmethod する、というものだ。まず、リストのための反復子。これ自体は表立って使用しないので、変な名前だ。

(defclass __lst-itr ()
  ((cons :accessor __lst-itr-cons
   :initarg  :list)))

で、反復子を作成するための関数 list-iterator。

(defun list-iterator (&optional (lst nil))
  (make-instance '__lst-itr :list lst))

次に、各種の操作を defmethod する。あ、今回からメソッドの名前付けを少し変更している。

(defmethod set-value ((itr __lst-itr) v)
  (setf (car (__lst-itr-cons itr)) v))

(defmethod get-value ((itr __lst-itr))
  (car (__lst-itr-cons itr)))

(defmethod equals ((itr1 __lst-itr)
       (itr2 __lst-itr))
  (eq (__lst-itr-cons itr1) (__lst-itr-cons itr2)))

(defmethod clone ((itr __lst-itr))
  (list-iterator (__lst-itr-cons itr)))

(defmethod increment ((itr __lst-itr))
  (setf (__lst-itr-cons itr) (cdr (__lst-itr-cons itr))))

で、これらが iterator4 パッケージに入っているものとして、for-each4 は以下のような感じ。

(defun for-each4 (itr1 itr2 func)
  (labels ((imp (itr)
             (if (iterator4:equals itr itr2)
                 nil
                 (progn (funcall func (iterator4:get-value itr))
                        (iterator4:increment itr)
                        (imp itr)))))
    (imp (iterator4:clone itr1))))

さて、これまでと同じようにテストしてみよう。処理コストはどうだろう？　今回は自宅のデスクトップPCで実行したので数字が前回までと全然違うが、まぁ比率が問題なので良しとしよう。環境は Windows7 + Cygwin + CLISP だ。おさらいしておくと、type-1 はリストやベクタを直接扱うバージョン、type-2 はクロージャで反復子を表現したバージョン、type-3 は構造体で反復子を表現したバージョン、type-4 はCLOSで反復子をクラス化したバージョンだ。

type-1, list:
Real time: 0.1716 sec.
Run time: 0.172 sec.
Space: 8800088 Bytes
GC: 12, GC time: 0.079 sec.

type-1, vector:
Real time: 0.187201 sec.
Run time: 0.187 sec.
Space: 8800088 Bytes
GC: 11, GC time: 0.094 sec.

type-2, list:
Real time: 0.499201 sec.
Run time: 0.499 sec.
Space: 12800256 Bytes
GC: 17, GC time: 0.109 sec.

type-2, vector:
Real time: 0.655201 sec.
Run time: 0.655 sec.
Space: 13600280 Bytes
GC: 19, GC time: 0.125 sec.

type-3, list:
Real time: 0.655201 sec.
Run time: 0.656 sec.
Space: 9600136 Bytes
GC: 12, GC time: 0.061 sec.

type-3, vector:
Real time: 0.748801 sec.
Run time: 0.748 sec.
Space: 10400160 Bytes
GC: 14, GC time: 0.062 sec.

type-4, list:
Real time: 1.294802 sec.
Run time: 1.295 sec.
Space: 9698336 Bytes
GC: 13, GC time: 0.078 sec.

type-4, vector:
Real time: 1.778404 sec.
Run time: 1.779 sec.
Space: 11657188 Bytes
GC: 16, GC time: 0.048 sec.

あれまぁ、CLOS バージョンはもっとも成績が悪いようだ。CLISP だからなのか、とも思ったが、type-1 から type-3 までは Fedora 上の SBCL でも試しており、比率に多少の差はあるものの同じような結果が出ている。ここまででは、結局のところクロージャで反復子を表現するのが一番ということになるようだ。リストや配列を直接扱う方がもちろん速いが、シーケンスの一部だけを処理したりといった機能の面で違いがあるので、そもそも比較対象にはならない。

というわけで、当面はクロージャによる表現を採用することにしよう。次回以降、Common Lisp を学んでいく上で見つけた別の話題に入るとしようかな。

コメント

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

このページのタグ

Page tag : Common Lisp

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