Common Lisp における配列の勉強メモです。

配列

lispのデータ型の１つです。リストと似ていますが、配列の方が特定の要素に高速にアクセスできます。

配列を作る

make-array関数で配列を生成できます。

CL-USER> (make-array 3)
#(NIL NIL NIL)

頭に # をつけることで、リストと区別しています。

最初に要素を指定するには、:initial-contents キーワード引数を使います。

CL-USER> (defparameter *arr* (make-array 4 :initial-contents '(2 3 4 5)))
*ARR*
CL-USER> *arr*
#(2 3 4 5)

あるインデックスの要素を取り出すには、aref関数を使います。インデックスは 0-origin です。次の例はインデックスが１の要素にアクセスしています。

CL-USER> (aref x 1)
NIL

取り出した要素に別の値をセットしたいときは、setf関数を使います。

CL-USER> (setf (aref x 1) 'foo)
FOO
CL-USER> x
#(NIL FOO NIL)

要素の取り出しと、要素の値のセットを同じ形で行なっているのがわかります。このように「同じ形で使える」ことを「ジェネリック」である、と言います。

リストでは、指定したインデックスの要素にアクセスするのに、次のようにします。

CL-USER> (nth 1 '(foo bar baz))
BAR

リストはコンスセルを順番に目的の場所までたどっていくので、特定の要素にアクセスするのに $O(N)$ の時間がかかります。それに対し、配列は定数時間で指定した要素にアクセスできます。