リストの弱点

多くの人はリストというデータ構造の第一印象は配列のようなものと考えるでしょう。しかし、リストはコンスセルという小さな部品を使ってデータを繋げた鎖のような構造をしていて、配列のようなひとかたまりのメモリー上の領域を番地にあたるインデックス値で管理するというものとは明確に異なるものです。LISP のリストはどのような型のデータも含めることができるので、再帰関数などの関数型言語の記述スタイルと合わせると、とても便利に利用できるデーター構造です。しかも配列のようなアクセスのためのインデックス値を使用する必要がないため、データの鎖の長さを自由に調整でき、インデックス値の範囲のチェックからも解放されます。これは取り組んでいる問題とは別の所で地味にプログラマの神経をすり減らしてきた問題でした。

リストには良いことが多いのですがメリットの裏には必ずデメリットがあります。それは速度です。リストは鎖のような構造をしていることからデータにアクセスするためにはその鎖をたどらなければなりません。一方、配列はインデックス値からメモリーのアドレスを計算し一足飛びにアクセスできます。またデータの書き換えも配列はそのアドレスのデータを単純に書き換えるだけですが、リストの場合は新しい値を指したコンスセルでデータの鎖をつなぎ換えなければなりません。Common LISP においては破壊的な関数 setf を用いることができるので、この影響は抑えられますが、一切の破壊的関数を排している AutoLISP はこの問題を避けることは不可能です。ただし破壊的関数を導入すると、そのメリットの外に副作用の理解のために本の一章が費やされる程度の複雑さも伴います。言語的な単純さと実際に使われる状況と実用的な速度とを勘案して、破壊的関数を導入しないという選択も十分理解できます。

AutoLISP のリストで具体的にどのような場合に速度が問題になってくるかと言えば、たいへん大きなリストを何度も書き換えている場合、また小さなリストであっても書き換えの回数が非常に多くなっている場合です。このようなケースに陥るとリストの鎖のつなぎ替えに要する時間が問題になるほど集積し、さらに LISP のメモリー管理が実行中のプログラムを自動的に中断してガーベージコレクションという不要なメモリーを解放する作業の時間も加わります。このときプログラムの実行速度が極端に遅くなます。ユーザーから見ると、何か不穏な事が起こったかのようにしか見えませんし、遅くなり具合もユーザーにとって待っていられる限度を超える場合もしばしばです。なかなかやっかいな問題です。

こういったデメリットの影響が大きいとき、やはり配列を使うことを考慮する必要が出てきます。AutoLISP のネイティブには配列というデータ構造はありません。しかし幸いなことに ActiveX のデータ構造からセーフ配列を利用することができます。セーフ配列は ActiveX 対応関数を使って AutoCAD にアクセスするために使われますが、それ以外の計算、アルゴリズムの部分でも利用できます。セーフ配列を利用するための AutoLISP 関数は一通りそろっていますのでそれを使えば済むことで特別なことではありませんが、ここでは AutoLISP でもっと気軽にセーフ配列を使えるよう、 Common LISP のような関数で使えるように環境を整備してみます。

ActiveX のセーフ配列を CommonLISP の配列のように見せかけるといっても制約と単純さのために次のような仕様とします。

1. Common LISP の配列にはいろいろなデータタイプを混在して代入できるが、ActiveX のセーフ配列の制約から作成時に指定した型のみ代入できる
2. ActiveX のセーフ配列は負のインデックス値も指定できるが、Common LISP の配列に倣ってインデックス値の始まりは 0 とする
3. 配列の次元によって関数に渡すインデックス値の数は変わるが、引数の数が固定の関数しか新しく定義できないため、インデックス値はリストで囲んで渡すこととする

配列の作成

配列の作成には次の関数 make-array を使用します。

(setq *array:sym->array-type*
       (list (cons 'INT vlax-vbLong)
             (cons 'REAL vlax-vbDouble)
             (cons 'STR vlax-vbString)
             (cons 'VLA-object vlax-vbObject)
             (cons 'BOOL vlax-vbBoolean)
             (cons 'VARIANT vlax-vbVariant)
       )
)

(defun make-array:initial-element (dimensions / make-list)
  (setq make-list (lambda (counter initial-element)
                    (if (< 0 counter)
                      (cons initial-element (make-list (1- counter) initial-element))
                    )
                  )
  )
  (if (and dimensions (cdr dimensions))
    (make-list (car dimensions) (make-array:initial-element (cdr dimensions)))
    (make-list (car dimensions) initial-element)
  )
)

(defun make-array (element-type dimensions initial-element / atype result)
  (if (setq atype (cdr (assoc element-type *array:sym->array-type*)))
    (progn (setq
             result (apply
                      'vlax-make-safearray
                      (cons atype
                            (mapcar (function (lambda (size) (cons 0 (1- size)))) dimensions)
                      )
                    )
           )
           (vlax-safearray-fill
             result
             (if (vl-consp initial-element)
               initial-element
               (make-array:initial-element dimensions)
             )
           )
    )
    (progn (princ "\n; ERROR : wrong symbol of type") (exit))
  )
)

関数の使い方は、まず第一引数に配列のデータタイプをシンボルで指定します。ActiveX で型を表すシンボルと値が定義されていますが、覚えにくくて不便なので、type 関数で使用されているものと共通のシンボル名を使います。セーフ配列で扱える型なので LISP にはなじまないものもありますが、整数、実数、文字列が使えればほかは忘れていても良いでしょう。

第二引数は配列の次元とサイズを表すリストを指定します。大きさ 3 の一次元の配列ならば「(3)」、2 × 3 の二次元配列ならば「(2 3)」といった具合です。

最後の引数によってデータの初期化が行われます。引数がアトムの場合はその値ですべての配列の値が初期化されます。リストの場合は、リストの値に沿って値が初期化されます。配列の次元とリストの構造は正確に合っていなくてはなりません。

実際の配列の作成例は以下の通りです。戻り値は、指定の仕様で作成され初期化されたセーフ配列です。vlax-safearray->list 関数は、セーフ配列の内容をリストで返す AutoLISP 標準の関数です。

_$ (setq int-array (make-array 'INT '(5) '(0 1 2 3 4)))⏎
#<safearray...>
_$ (vlax-safearray->list int-array)⏎
(0 1 2 3 4)
_$ (setq real-array (make-array 'REAL '(3 3) '((1.0 2.0 3.0) (4.0 5.0 6.0) (7.0 8.0 9.0))))⏎
#<safearray...>
_$ (vlax-safearray->list real-array)⏎
((1.0 2.0 3.0) (4.0 5.0 6.0) (7.0 8.0 9.0))
_$ (setq str-array (make-array 'STR '(3 3) "A"))⏎
#<safearray...>
_$ (vlax-safearray->list str-array)⏎
(("A" "A" "A") ("A" "A" "A") ("A" "A" "A"))

後から配列のデータタイプを確認したい場合は次の関数を使用します。

(setq *array:array-type->sym*
       (list (cons vlax-vbInteger 'INT)
             (cons vlax-vbLong 'INT)
             (cons vlax-vbSingle 'REAL)
             (cons vlax-vbDouble 'REAL)
             (cons vlax-vbString 'STR)
             (cons vlax-vbObject 'VLA-object)
             (cons vlax-vbBoolean 'BOOL)
             (cons vlax-vbVariant 'VARIANT)
       )
)

(defun array-type (array)
  (cdr (assoc (vlax-safearray-type array) *array:array-type->sym*))
)

使用例はは以下の通りです。

_$ (array-type int-array)⏎
INT
_$ (array-type real-array)⏎
REAL
_$ (array-type str-array)⏎
STR

後から配列のサイズと次元を確認したい場合は次の関数を使用します。

(defun array-dimensions (array / range)
  (setq range      (lambda (s e)
                     (if (<= s e)
                       (cons s (range (1+ s) e))
                     )
                   )
  )
  (mapcar (function (lambda (dimension)
                      (1+ (- (vlax-safearray-get-u-bound array dimension)
                             (vlax-safearray-get-l-bound array dimension)
                          )
                      )
                    )
          )
          (range 1 (vlax-safearray-get-dim array))
  )
)

使用例はは以下の通りです。

_$ (array-dimensions int-array)⏎
(5)
_$ (array-dimensions real-array)⏎
(3 3)
_$ (array-dimensions str-array)⏎
(3 3)

値の参照

Common LISP の配列は、一次元の配列を特別に区別してベクタと呼んでいます。そしてベクタの場合は速度の速い専用の関数があります。そのためアクセスのための関数が一次元の場合と多次元の場合とで二種類あります。ここでは実質中身は同じですが二つの関数を用意してみます。svref 関数がベクタ用の関数、aref 関数が一般的な配列用の関数です。sv はシンプルベクタの略と言われています。

(defun svref (array index)
  (vlax-safearray-get-element array index)
)

(defun aref (array index-list)
  (apply 'vlax-safearray-get-element (cons array index-list))
)

使用例はは以下の通りです。

_$ (svref int-array 3)⏎
3
_$ (aref int-array '(3))⏎
3
_$ (aref real-array '(1 2))⏎
6.0

値の書き換え

Common LISP の配列の書き換えは値の参照で使う関数と破壊的関数 setf を組み合わせて行いますので、配列の書き換えのための関数は新たに存在しません。AutoLISP では使えないテクニックなので、参照のための関数名の頭に set- とつけた書き換えのための関数を用意します。set-svref 関数がベクタ用の関数、set-aref 関数が一般的な配列用の関数です。戻り値は、操作対象の配列です。

(defun set-svref (array index value)
  (vlax-safearray-put-element array index value)
  array
)

(defun set-aref (array index-list value)
  (apply 'vlax-safearray-put-element (cons array (append index-list (list value))))
  array
)

使用例はは以下の通りです。

_$ (set-svref int-array 3 30)⏎
#<safearray...>
_$ (vlax-safearray->list int-array)⏎
(0 1 2 30 4)
_$ (set-aref int-array '(3) 300)⏎
#<safearray...>
_$ (vlax-safearray->list int-array)⏎
(0 1 2 300 4)
_$ (set-aref real-array '(1 2) 60.0)⏎
#<safearray...>
_$ (vlax-safearray->list real-array)⏎
((1.0 2.0 3.0) (4.0 5.0 60.0) (7.0 8.0 9.0))

リストと配列の速度比較

実際にリストと配列を使った場合の速度はどのようになるでしょうか。リストが極端に不利になる状況を想定して比較してみます。

この例のように極端に巨大な要素を扱うとき AutoLISP のリストと関数型言語の特徴と喧伝している再帰関数は実用になりません。N/A と示したのはいつまで待っても処理が終わらないので値が得られなかったことを示します。あまりにもリストに不利な例で、不公平ではと考えてしまうほどの結果です。

値の参照・書き換えのどちらのケースにおいても、svref 関数が優秀なのは一連の処理にリストを一度も使わないからと思われます。

値の参照に限って言えばリストの nth 関数は予想に反して配列の aref 関数よりも高速です。aref 関数が思ったより高速にならないのは配列のインデックスをリストにして渡すという関数のインタフェースの問題だと思われます。また nth 関数が AutoLISP のネイティブの関数のため最適化の度合いも有利に働いていると思われます。ただし、要素の大きさがもっと大きくなると配列の場合は時間が変わらないのに対して、リストの場合は比例して時間がかかるようになりますので、今回はたまたま aref 関数が遅かっただけです。

値の書き換えのケースにおいては、AutoLISP では事実上リストで扱うことは不可能です。一方、配列は参照に比べてわずかに時間がかかるようになるだけで誤差の範囲です。この結果だけをみるとリストではなくていつも配列を使えばいいのではないかという考えも浮かびますが、実際に配列を使ったコードを書いてみるとリストの便利さシンプルさを実感することになると思うので、結局、適材適所で使うのが正解です。

実際にはまずリストでプログラムを記述することになるでしょう。そしてテスト段階で実用的な速度が出ないとき、固定長のデータを扱っている、扱っているデータタイプは一種類、ならば配列でプログラムを書き換えるという段階を踏みます。また、大きめのリストを扱っているときに、小さく分割管理したリストで同じアルゴリズムを実装すると速度が数十倍速くなることもあるので、配列とともに検討の価値がある方法です。