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

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

最終更新日付：2012/10/15 01:00:00

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

2012 年 10 月 15 日

前回まででクロージャを使用した反復子を使ってみたが、リストを直接扱うアルゴリズムよりもかなり遅かった。さらに別の方法を模索してみる。

そもそも、クロージャを利用した方法というのは、データと処理をまとめて別モノにできるというメリットがあった。前回の list-iterator はリストのための反復子を作成するものだったが、これに対するベクタ用の vector-iterator もあり、同じコンベンションに従いつつ別の振る舞いをするクロージャを作成していた。これらを使い分ける様子は、まるでポリモーフィックなオブジェクトを使っているかのようだ。シビレるじゃないか。しかし、クロージャであるがゆえに入口はひとつ。結果としてどの処理をするかをシンボルで渡し、実行時に内部で分岐をさせていたわけだ。そしてそれが遅い原因ではないか、と考えたわけだ。

‥‥‥で、クロージャをいったんあきらめて他の方法を模索するわけだ。CLOS は最後の楽しみにとっておくことにする。だって折角 Lisp をしているんだから、いきなり CLOS に走りたくないじゃないか。

ポイントは、前回のクロージャ版のような実行時の分岐をしないで済むような構造を考えることだ。そのためには、前回提示した以下の get-value のようなマクロが、明示的に「値を取得するための関数」に解決できなければならない。

(defmacro get-value (itr)
  `(funcall ,itr :get-value))

シンボルの属性リストにクロージャを収めるという方法もあるが、これもやはり遅そうだ。では、構造体はどうだろう？　各種の関数を集めた構造体を反復子として、上記のようなマクロが適切な関数をコールするようにすれば、実行時の分岐は避けられるはずだ。

しかし、それでは反復子の構造体が太り過ぎてしまわないだろうか？　可能ならば、反復子は ── それが構造体であれ他のオブジェクトであれ ── 必要最低限のサイズであってほしい。どうせ固有のものなら、それは共有すれば良いだろう。この考え方を進めていった結果、リストやベクタなどの種類別に関数テーブルを用意し、各反復子はデータと関数テーブルへの参照を保有する、というかたちになった。それって C++ における仮想関数テーブルと同じじゃないか。そのとおりだ。こういうのを「お里が知れる」っていうのかな。

まぁそれはそれとして、実装を簡単に。まずは反復子の実体。iterator-data。これは（ひとまず）コンテナの種類を問わない汎用的なものってことで。まず、vtbl が関数テーブルを保持する。そしてリストであれば pos がそのままコンスを参照するし、ベクタであれば pos がベクタ実体の参照とインデックスからなるドットリストを保有することになるだろう（ここは改善の余地ありだな）。

(defstruct iterator-data
  vtbl
  pos)

で、種類別に用意される関数テーブル。

(defstruct iterator-vtbl
  clone
  is-equal
  get-value
  set-value
  move-next
  move-prev
  distance
  move
  offset
  at)

これだけのものがあると、例のラッパーマクロ get-value は以下のようになる。

(defmacro get-value (itr)
  `(funcall (iterator-vtbl-get-value (iterator-data-vtbl ,itr)) ,itr))

（上の定義には誤りがある。,itr を２回書くのは誤りだ。気づいてはいるので、今はどうか気にしないでほしい）

ではリストのための実装を試してみよう。まずは関数テーブル。Lisp の単方向リストは STL 用語で言うと「前方向反復子」しかサポートできないので、以下のような感じになるだろう。サポートできない処理の部分は nil にしておく。

(defvar *list-iterator-vtbl*)

(setq *list-iterator-vtbl* (make-iterator-vtbl
       :clone     (lambda (itr)
           (list-iterator (iterator-data-pos itr)))
       :is-equal  (lambda (itr1 itr2)
           (eq (iterator-data-pos itr1)
            (iterator-data-pos itr2)))
       :get-value (lambda (itr)
           (car (iterator-data-pos itr)))
       :set-value (lambda (itr val)
           (setf (car (iterator-data-pos itr)) val))
       :move-next (lambda (itr)
           (setf (iterator-data-pos itr)
              (cdr (iterator-data-pos itr))))
       :move-prev nil
       :distance  nil
       :move      nil
       :offset    nil
       :at        nil))

で、これらを使って、リストの反復子を作成する関数 list-iterator は以下に。

(defun list-iterator (lst)
  (make-iterator-data :vtbl *list-iterator-vtbl* :pos lst))

ベクタの場合の実装は割愛するけれども、これらの実装を type-3 として同じテストをやってみた。結果は以下のとおり（比較のために type-2 も再掲）。

type-2, list:
    Real time: 3.625 sec.
    Run time: 3.625 sec.
    Space: 12800256 Bytes
    GC: 17, GC time: 0.939 sec.

type-2, vector:
    Real time: 4.71875 sec.
    Run time: 4.718 sec.
    Space: 13600280 Bytes
    GC: 18, GC time: 1.015 sec.

type-3, list:
    Real time: 3.9375 sec.
    Run time: 3.938 sec.
    Space: 9600136 Bytes
    GC: 13, GC time: 0.718 sec.

type-3, vector:
    Real time: 4.65625 sec.
    Run time: 4.641 sec.
    Space: 10400160 Bytes
    GC: 13, GC time: 0.734 sec.

おやおや、実行時の分岐がなくなったはずなのに、リスト版では微妙にではあるがさらに遅くなっている。一方、ベクタ版はわずかだが速度が向上した。そして、どちらも空間消費は抑えられたようだ。

さて、構造体での実装は結局、C++ の文脈でいうところの仮想関数テーブルを手作りするような結果になった。そして次は CLOS を試すことになる。CLOS が内部的にどうやって実装されているのかは良く知らないが、まぁやってみよう。続きは次回。

コメント

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

このページのタグ

Page tag : Common Lisp

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