独学Common Lisp

データ構造と効率、simple-vector

リスト構造が苦手な処理

リスト構造はとても柔軟で強力なデータ構造です。以前に説明した通り、carcdrでできているので、いつでもcdr部分を分離して付け替えることができます。

しかし、リスト構造には苦手な処理もあります。それは「ランダムアクセス」です。

ランダムアクセスとは、データ構造の順番に関係なくN番目のデータを取り出す、というアクセススタイルです。データ構造が簡易的なデータベースのようになっていてリクエストに対して必要なデータを取得して返すようなものが該当します。最初から順番にアクセスするようなものはランダムアクセスではありません。

逆にランダムアクセスが得意なデータ構造があります。それは「配列」です。配列はメモリ上の一定領域を連番で確保しておき、N番目へのアクセスが発生したら先頭のアドレス+N個分のアドレスを計算して、直接そのデータへアクセスしにいきます。その代わり、一連のデータを確保する必要があるので途中でデータを増やしたり減らしたりすることは苦手で、基本的には最初に確保したデータ領域の中で使用します。

Common Lispも配列が標準仕様の中に組み込まれているので、どの処理系でも使うことができます。また、Common Lispの配列は非常に多機能で、途中で要素数を増やしたりすることもできますし、多次元配列をネイティブで扱うことができます。

ただ、現実的には複雑な配列の機能を使うことは少ないと思います。もしそのような機能が必要であれば、リレーショナルデータベースと連携して使う方がはるかに柔軟ですし、実用面でもそのように使われることが多いでしょう。簡易的なものであればリストでも十分な速度が出るはずです。

Common Lispで配列を使う場合はおそらく効率が重要だけれどもリレーショナルデータベースは使わない(または事情により使えない)という場合でしょうから、高速な処理が可能になる非可変長型の1次元配列であるsimple-vectorをよく使うと思います。

今回はsimple-vectorを中心にした簡単な配列の使い方と各種宣言の方法を説明します。

make-array

Common Lispで配列を作るのはとても簡単です。make-arrayだけで作ることができます。

(make-array 10)
; => #(0 0 0 0 0 0 0 0 0 0)

かっこの前にシャープサインがついていると思いますが、これが配列を意味するリーダーマクロ#(です。今作ったのは1次元配列であり、いわゆるベクタです。

リストと同じように、直接記述することでも作成できます。

#(1 2 3)
; => #(1 2 3)

ちなみに、1次元配列ではない配列を作る場合は、シャープサインに続けて次元とaという記号をつけます。

#2a((1 2 3) (4 5 6) (7 8 9))
; => #2A((1 2 3) (4 5 6) (7 8 9))

make-arrayから作る場合は、要素数の代わりに次元と要素数を組み合わせたリストで記述します。

(make-array '(3 3))
; => #2A((0 0 0) (0 0 0) (0 0 0))

3x3の二次元配列です。

aref, svref

配列の要素にアクセスするにはarefを使います。

(aref #(1 2 3) 1)
; => 2
(aref #2a((1 2 3) (4 5 6) (7 8 9)) 2 1)
; => 8

要素番号は0から始まるので、上の例では2番目の要素である2が取得されます。下の事例は二次元配列で、3行目の2列目にアクセスするので8が取得できます。

ちなみに、リストに対してアクセスするにはnthを使いますが、arefとは引数の順番が違うので間違えないようにしてください。個人的にはリストにアクセスするときはsecondthirdなどを使うことの方が多いです。

(nth 1 '(1 2 3))
; => 2

1次元配列の時はarefの代わりにより高速なアクセスを実現するsvrefを使うことができます。

(svref #(1 2 3) 1)
; => 2

実は、ntharefsvrefに対して型を問わずにアクセスできるeltというものもあります。

(elt #(1 2 3) 1)
; => 2

しかし、eltは汎用性が高い分、データの型を調べて分岐する必要があるので、遅くなります。要素番号でアクセスするような場合はほとんど配列でしょうから、arefsvrefを選択することになるでしょう。

これらはアクセッサと呼ばれる関数であり、setfを使って内容の変更に使うこともできます。

(defvar *vec* #(1 2 3))
; => *VEC*
(setf (svref *vec* 1) 5)
; => 5
*vec*
; => #(1 5 3)

time マクロ

Common Lispにはベンチマークを取るマクロも用意されていますので、ここでリストとベクタ(1次元配列)で処理速度を比較してみましょう。

(defun test-list ()
  (let ((lst (make-list 1000000)))
    (time
     (loop repeat 10000
        do (nth (random 1000000) lst)))))

(defun test-vector ()
  (let ((vec (make-array 1000000)))
    (time
     (loop repeat 10000
        do (svref vec (random 1000000))))))

2つの関数を定義したソースコードを用意して、loadしてそれぞれ実行してみてください。私の環境(Macbook Pro, 2.7GHz Intel Core i5, 8GB DDR3 / Clozure CL)で色々立ち上げた状態で計測すると、以下のようになりました。

? (test-list)
(LOOP REPEAT 10000 DO (NTH (RANDOM 1000000) LST))
took 18,741,604 microseconds (18.741604 seconds) to run.
During that period, and with 4 available CPU cores,
     18,722,195 microseconds (18.722195 seconds) were spent in user mode
         16,493 microseconds ( 0.016493 seconds) were spent in system mode
 1 minor page faults, 0 major page faults, 0 swaps.
NIL

? (test-vector)
(LOOP REPEAT 10000 DO (SVREF VEC (RANDOM 1000000)))
took 368 microseconds (0.000368 seconds) to run.
During that period, and with 4 available CPU cores,
     369 microseconds (0.000369 seconds) were spent in user mode
       3 microseconds (0.000003 seconds) were spent in system mode
NIL

loopにはrepeatというキーワードがあり、単純に繰り返すことができます。また、randomという関数は指定した数未満の整数を返します。今回は100万の要素を持つリストとベクタを用意して、乱数で発生させた要素番号の要素を1万回取り出しています。18.7秒と0.0004秒なので、リストとベクタで圧倒的な差があることが分かります。

繰り返しになりますが、これはランダムアクセスだからこそ差が出ます。全ての要素に順番にアクセスするような場合はほとんど変わらないか、リストの方が早くなることがあります(ただし、メモリの使用量は確実に配列の方が低いはずです)。

速度的な問題の大半は適切なデータ構造を使うことで解決します。データ構造を考えて設計するとプログラム全体もすっきりしますし、特にビッグデータ解析や統計的分析の場合にはデータ構造をしっかりと検討してからプログラムを作り始めるべきです。逆に不適切なデータ構造を使った状態で他の効率化を試みてもあまり効果はありません。

型宣言とdeclareによる最適化

Common Lispはもともとかなり速いので、PythonやRuby、Perlと比べて速度的に困ることはないと思います。実際、軽量言語では少し重い処理になるとライブラリをC/C++で書いて、それを呼び出すという扱いになることがほとんどでしょう。PythonのNumpyなどはその代表例であり、言語標準の機能を使うよりもサードパーティ製のライブラリを使った方が数値計算は速くなります。

Common Lispは長い歴史の中で研究されてきた優秀なコンパイラがあるので、データ構造さえきちんと選べばほとんど他の処理は必要がないと思います。しかし、ときにはどうしてもボトルネックになっている関数を最適化したい場合も出てくるかもしれません。Common Lispにはさらに効率化を目指す仕組みが用意されているので、安易にC/C++でライブラリを書かない方がいいと思います。

データ構造以外の検討事項としては、アルゴリズムが挙げられます。代表的なものはすでに紹介した再帰を末尾再帰に書き換えるという手続きです。末尾再帰をループにするのはコンパイラがやってくれますので、ループで書く必要はありませんが、少なくとも末尾再帰とそうでない場合はかなり違いが出ます。

もう一つ効くのが、型を指定してしまうことです。しかし、型を指定するということは指定していない型の時は即時エラーになるというリスクがあります。Common Lispは関数単位で最適化を行うことができるので、本当に必要な箇所だけを最適化してください。

最も単純な型指定は、関数の引数に対するfixnumの指定です。

(defun fib (n)
  (declare (type fixnum n))
  (if (< n 2)
    n
    (+ (fib (- n 2)) (fib (- n 1)))))

これはよくあるベンチマーク用のフィボナッチ数列関数で、普通の再帰を2箇所で使っているのであえて遅い処理にしています。アルゴリズムを変えると一瞬で計算できますが、一瞬ではベンチマークの意味がないので、あえて遅い計算方法を使います。

引数に対して型の宣言を行うには、declareを使います。fixnumは整数を示す型で、データ型を整数に限定するとそれだけで不要なメモリが解放されますから、それなりに高速化できます。今回の場合、宣言なしとありで約20%ほど高速化しました。

型の宣言は様々な場所で使えます。例えばlambdaletlabelsなどでも使えますし、loopにも型宣言機能が付いています。さらに、関数の返り値も型の宣言を行うことができます。ただし、型前言を付けていくとソースコードが汚くなります。

試しに、全ての型宣言を行った関数を作ってみました。経済的な時系列分析における変化率を求める関数です。通常の変化率は、t期の値をV(t)と表すと

(V(t) - V(t-1)) / V(t-1)
= V(t)/V(t-1) - 1

として表すことができます。しかし、このように求めた変化率は例えば長期時系列に変換することができません。t期と(t-1)期の比較ではいいですが、t期と(t-10)期ではその間の変化率を全て足していってもV(t)/V(t-10) - 1とは一致しなくなってしまいます。

そこでlogを用いた計算が使われます。対数の性格上、割り算を引き算に変換できるので、ネイピア数eを用いた対数の引き算で変化率を表します。ネイピア数を用いることで上記の算術的変化率に近似します。つまり、上記の変化率とlogV(t) - logV(t-1)が近似します。これなら隣り合う変化率を足していくとt期と(t-10)期の変化率logV(t) - logV(t-10)に等しくなります。

(defun change (v)
  (declare (type (simple-array double-float *) v))            ; <---
  (let* ((len (length v))
         (rslt (make-array len :element-type 'double-float))) ; <---
    (declare (type fixnum len)                                ; <---
             (type (simple-array double-float len) rslt))     ; <---
    (setf (aref rslt 0) 0d0)
    (loop
       for i fixnum from 0 to (- len 2)                       ; <---
       do (setf (aref rslt (1+ i))
                (- (log (aref v (1+ i)))
                   (log (aref v i)))))
    (the (simple-array double-float len) rslt)))              ; <---

(defvar *data* (make-array 3 :element-type 'double-float      ; <---
                           :initial-contents #(100d0 110d0 120d0)))

(change *data*)
; => #(0.0D0 0.09531017980432477D0 0.08701137698962924D0)

本題は型の宣言です。

配列に対しても型の宣言をすることができます。配列は、配列自体の型と配列の要素の型、それに要素数(と次元)を指定することができます。

最も包括的な配列の型はarrayで、全ての配列はarray型に合致します。このうち非可変長の配列がsimple-array型です。このページの最初に述べたように、配列を使う場合の多くは高速化のために非可変長にすると思いますので、大部分の配列はsimple-arrayになると思います。

一方、配列の次元が1次であるものがベクタであることはすでに述べましたので、vector型がベクタに対応します。ただし、1次元の非可変長配列であるsimple-vector型は、配列の中の要素の型を指定することができません。一方、simple-arrayは配列の要素の型と配列の次元を調整できますので、simple-vectorsimple-arrayで表すことはできますが、逆はできません。(simple-vector 10)(simple-array t 10)(simple-array t (10))と等価です。tは全ての型の根源に当たる型です。

つまり、1次元の非可変長の配列の型はsimple-vectorであり、1次元の非可変長でさらに要素の型も指定するものはsimple-array <type>で指定します。しかしややこしいことに、後者はsvrefではアクセスできません。svrefは要素の型がt、つまりなんでも入る配列でなければなりません。

要素数(次元)は指定しなくても構いせんし、*で包括的に指定することもできます。1次元の配列(ベクタ)において、*(*)は等価です。

小数の型には様々なものがありますが、幸い私の環境ではメモリに困っていないので、'double-floatを用いています。これがC言語のdoubleに相当する型です。なお、数値を'double-float型にするには数の直後にdを付け、指数部分を次に続けます。つまり、3.143.14d0であり、314.153.1415d2になります。

Common Lispの多くの処理系では標準で単精度の'single-floatを用いていますので、外部のデータファイルからデータを取得する場合は大域変数*READ-DEFAULT-FLOAT-FORMAT*を変更します。

(setf *READ-DEFAULT-FLOAT-FORMAT* 'double-float)

これで外部から小数のデータを読み取ったときに'double-floatになります。

まだまだ型宣言は奥が深いです。make-arrayでは型を指定して配列を作ることができます。:element-typeキーワードで型を指定すると、全ての要素が同じ型の配列になります。逆にいうと標準では様々な型を配列に含めることができるので、C言語の配列などとは異なります。

'double-floatquoteをつけるかどうかは、その場所が関数かどうかで判断します。make-arrayのような関数は引数を評価しますから、double-floatのようにquoteがないとシンボルとして評価しようとしてエラーになります。一方、declareはシンボルなので、この中では不要です。

loopマクロの中で使われる変数には、型宣言をつけることができます。ここではiは要素番号を示すだけのfixnumなので変数名の直後で型宣言をしています。

関数の返り値の型を指定するには、theスペシャルオペレータを使用します。ここまで指定すると、関数の引数・内部変数・返り値の全てについて型宣言を行うことになります。Common Lispは基本的に変数に型はなく、データに強い型が存在します。何も指定しなければ変数は全ての型を参照できますが、型を指定すると事実上静的型付けの言語と同じになります。

なお、計測してみなければわかりませんが、引数の型の指定以外はあまり高速化の効果が見られないかもしれません。引数の型は関数には決して分からないので指定する効果が高いですが、関数の中の処理はある程度コンパイラによって型推論が効きます。特に返り値の型指定はソースコードの可読性を一気に低くしますから、あまり使わない方がいいように思います。

optimize宣言

関数内のdeclareによる宣言の代表例として、もう一つoptimize宣言があります。これは、その関数をどのようにコンパイルするかを指示するものです。

例えば、開発段階ではデバッグが重要ですから、エラーの時のメッセージを丁寧に出力してくれることが必要です。逆に運用段階では速度が重要になりますから、速度の重要性を引き上げます。

optimize宣言では以下の項目について0から3までの数字で重要性を指示します。3が最も重要で、0が最も重要でない、ということになります。

以下のように指示します。

(declare (optimize (speed 3) (safety 2) (debug 0)))

型宣言とともに使う場合は、一つのdeclareに入れます。

(declare (optimize (speed 3) (safety 2) (debug 0))
         (type fixnum n)))

declaimとinline

最後にもう一つ、最適化のための方法を紹介しておきます。それは「関数のインライン化」です。関数を呼び出すときには、その関数の大きさに関わらず一定のイニシャルコストがかかりますが、関数の本体が十分に小さい時はその呼び出しコストの割合が大きくなります。そこで、関数の呼び出しを行わずに呼び出し元に関数の定義自体を埋め込んでしまうという処理をするのが「インライン化」です。

このインライン化は効果が大きい処理の一つですが、以下の条件の両方に合致したときにのみ利用してください。

関数のインライン化を行うとデバッグがしにくくなります。また、Comon Lispは動的な言語なので、関数を再定義した場合も呼び出し側はコンパイルし直す必要がありませんが、インライン化していると呼び出し側も全てコンパイルしなければなりません。多くの場合、インライン化するかどうかはコンパイラが判断する方が賢いので、最適化のための最後の手段と考えてください。

インライン化は関数の中ではなく外で行います。使うのもdeclareではなく、declaimです。

(declaim (inline sum))
(defun sum (list)
  ...)

関数のインライン化はマクロのように働きます。つまり、関数の定義が呼び出し元に挿入されるのです。そのため、トレースなどもできなくなります。エラーが発生しても、特定は困難です。

最適化の必要性

今回最適化を重点的に取り上げたのは、プログラミングにとってそれがやはり重要だからです。Common Lispは軽量言語よりもはるかに速いので、速さは強みになります。ハードウェアの負担を軽減し、コスト削減にも直結します。

しかし、多くの場合はデータ構造を改善することが最大の最適化です。今回型宣言を重点的に紹介したのは、それをするとソースコードが見にくくなるということを実感していただきたかったからでもあります。末尾再帰最適化の際もそうでしたが、速度を得るためには簡潔さをトレードオフにしなくてはなりません。

とはいえ、私は最適化を気持ちの良いものと感じています。Pythonで計算すると数十秒もかかるフィボナッチ数列がCommon Lispなら1秒足らずで終わるといえば、やはり気持ちがいいと感じるはずです。ソースコードやデータ構造の改善によっていくばくかでも改善ができたら、やはりそれは気持ちの良いものでしょう。計算機の性能が進化するとはいえ、トヨタ生産方式のカイゼンのように、最適化への飽くなき探求はいつの時代も変わらないような気がします。

もっとも、プログラム全体の進行にとってあまり重要でない部分を最適化しても意味はありません。人は誰でも簡単なところに流れますから、データ構造を根本的に見直すとか、アルゴリズムを設計し直すというような努力よりも、些細な型宣言で済ませてしまおうとしがちです。しかし、そのようなカイゼンは実はあまり十分な効果をあげられないこともあるということを分かった上で行うようにしてください。

参考文献


Copyright © 2017- satoshiweb.net All rights reserved.