【Common Lisp】
make-array で作る多次元配列の
基本の使い方
（座標と行列）

by
  • Common Lispの多次元配列は make-array に次元リストを渡して作ります。
  • 要素へのアクセスは aref にインデックスを複数渡すだけで、1次元と同じ関数が使えます。
  • 2次元はグリッド・DPテーブル・隣接行列、3次元は時間軸付き盤面や画像バッファに向いています。
  • 4次元以上になったら、構造体やハッシュテーブルへの切り替えを検討する場面が増えます。

関連記事

1. 多次元配列を作る

make-array に次元リストを渡すと多次元配列を作れます。

1次元のときは整数を渡しましたが、多次元では '(行 列) の形でリストを渡します。

;; 3×4 の2次元配列（全要素を0で初期化）
(make-array '(3 4) :initial-element 0)
;=> #2A((0 0 0 0) (0 0 0 0) (0 0 0 0))

(defun make-grid (rows cols &optional (init 0))
  (make-array (list rows cols) 
              :initial-element init))

(make-grid 2 3)
;=> #2A((0 0 0) (0 0 0))Code language: Lisp (lisp)

サイズが変数の場合は、クォートできないので (list a b)の形で渡します。

#2A という表示は「2次元配列」を意味するリーダーマクロの接頭辞です1。
3次元なら #3A、N次元なら #NA になります。

1.1. initial-contents でまとめて初期化する

:initial-contents にネストしたリストを渡すと、内容をまとめて指定できます。

(make-array '(2 3) :initial-contents '((1 2 3)
                                       (4 5 6)))
;=> #2A((1 2 3) (4 5 6))

;; 要素数が合わないとエラー
(make-array '(2 3) :initial-contents '((1 2) (3 4)))
;; => error: Not enough elements...Code language: Lisp (lisp)

ただし、リストの構造が次元と完全に一致していないとエラーになります2。

多次元配列の#2A(...) という形式はありますが、変数を埋め込めません。
実行時に値が決まる場合は make-array を使います。

1.2. 次元に関する関数

1次元配列の length に相当するものは、array-dimensionsです。

(defparameter *grid* (make-array '(3 4) :initial-element 0))

(array-dimensions *grid*)
;=> (3 4)Code language: Lisp (lisp)

array-dimensions は各次元のサイズをリストで返します。

array-rank は次元数を返し、特定の次元のサイズを取り出すには、array-dimension を使います。

(array-rank *grid*)
;=> 2

(array-dimension *grid* 0)   ; 行数
;=> 3

(array-dimension *grid* 1)   ; 列数
;=> 4

(array-total-size *grid*)
;=> 12Code language: Lisp (lisp)

全要素数は array-total-size で求められます3。

2. aref で読み書きする

2次元配列でも、1次元のときと同じ aref と setf aref を使います。

(defparameter *board* (make-array '(3 3) :initial-element 0))

;; 書き込み（1行目、2列目）
(setf (aref *board* 0 1) 5)

;; 読み出し
(aref *board* 0 1)
;=> 5Code language: Lisp (lisp)

ただ、arefでは、インデックスを必要な次元数だけ渡します4。
範囲外のインデックスを渡すと実装固有のエラーになる点は、1次元と同じです。

3. 2次元配列の使い方

2次元配列は行と列のある表形式のデータを自然に扱えます。

3.1. 条件を満たすセルの座標を返す

グリッド全体を走査して、条件に合うセルの座標をリストで集めるパターンです。

loop の when 節と collect を組み合わせると簡潔に書けます。

(defun find-cells-if (grid predicate)
  "条件を満たすセルの座標を (r c) のリストで返す"
  (let ((rows (array-dimension grid 0))
        (cols (array-dimension grid 1)))
    (loop for r below rows
          nconcing (loop for c below cols
                         when (funcall predicate (aref grid r c))
                           collect (list r c)))))

(let ((g (make-array '(3 4)
                     :initial-contents '((10 50 30 80)
                                         (20 90 40 60)
                                         (70 15 85 25)))))
  (find-cells-if g (lambda (v) (>= v 70))))
;=> ((0 3) (1 1) (2 0) (2 2))Code language: Lisp (lisp)

nconcing は各行のリストを破壊的に連結して1つのリストにまとめます。

元のグリッドは変更しません。

述語を差し替えるだけで用途が変わります。
特定の値に一致するセルを探すなら値を直接渡します。

(defun find-cells (grid value)
  "指定した値を持つセルの座標をすべて返す"
  (find-cells-if grid (lambda (v) (eql v value))))

(let ((g (make-array '(3 3)
                     :initial-contents '((1 0 1)
                                         (0 1 0)
                                         (1 0 0)))))
  (find-cells g 1))
;=> ((0 0) (0 2) (1 1) (2 0))Code language: Lisp (lisp)

3.2. 条件を満たす最初のセルを返す

最初に一致したセルだけが必要な場合は、見つかった時点でループを抜けます。

loop の thereis を使うと、条件を満たした最初の値をそのまま返せます。

(defun find-cell-if (grid predicate)
  "条件を満たす最初のセルの座標を返す。
見つからなければ nil"
  (let ((rows (array-dimension grid 0))
        (cols (array-dimension grid 1)))
    (loop for r below rows
          thereis (loop for c below cols
                        when (funcall predicate (aref grid r c))
                          return (list r c)))))

(let ((g (make-array '(3 4)
                     :initial-contents '((10 50 30 80)
                                         (20 90 40 60)
                                         (70 15 85 25)))))
  (find-cell-if g (lambda (v) (>= v 70))))
;=> (0 3)Code language: Lisp (lisp)

thereis は内側のループが nil 以外を返した時点で外側のループも終了します。

全走査する find-cells-if と違い、最初の一致で打ち切られるため、大きなグリッドで早期終了が期待できます。

特定の値を探す場合は述語を省略した形にできます。

(defun find-cell (grid value)
  "指定した値を持つ最初のセルの座標を返す"
  (find-cell-if grid (lambda (v) (eql v value))))

(let ((g (make-array '(3 3)
                     :initial-contents '((0 0 1)
                                         (0 1 0)
                                         (1 0 0)))))
  (find-cell g 1))
;=> (0 2)Code language: Lisp (lisp)

4. 型特化と効率化

多次元配列でも element-type・declare・optimize の三点セットが有効です。

4.1. element-type で型を絞る

:element-type を指定すると、SBCLが要素をunboxした形で格納します。5
汎用配列より演算が速くなり、型に合わない値を入れると type-error が出ます。

;; fixnum 特化の2次元配列
(make-array '(100 100)
            :element-type 'fixnum
            :initial-element 0)

;; 浮動小数点の3次元配列
(make-array '(10 10 10)
            :element-type 'single-float
            :initial-element 0.0)Code language: Lisp (lisp)

4.2. declare で多次元配列の型を宣言する

(simple-array fixnum (* *)) は「fixnum の固定長2次元配列」を表す型指定です。

コンパイラがインデックスチェックや間接参照を省ける場合があります。

(defun sum-matrix (m)
  (declare (type (simple-array fixnum (* *)) m)
           (optimize (speed 3) (safety 0)))
  (let ((rows (array-dimension m 0))
        (cols (array-dimension m 1))
        (sum 0))
    (declare (type fixnum sum))
    (loop for r below rows
          do (loop for c below cols
                   do (incf sum (aref m r c))))
    sum))

(sum-matrix
  (make-array '(3 3) :element-type 'fixnum
                     :initial-contents '((1 2 3) (4 5 6) (7 8 9))))
;=> 45Code language: Lisp (lisp)

3次元配列は (simple-array fixnum (* * *)) のように * を増やします。6

4.3. array-element-type で型を確認する

(array-element-type
  (make-array '(3 3) :element-type 'fixnum))
;=> FIXNUM

(array-element-type
  (make-array '(3 3)))
;=> TCode language: Lisp (lisp)

5. 多次元配列を走査するループ

5.1. 多重ループ

行優先で全要素を走査するには多重ループを書きます。

(defun map-grid (f grid)
  "グリッドの全要素に f を適用して新しいグリッドを返す"
  (let* ((rows (array-dimension grid 0))
         (cols (array-dimension grid 1))
         (result (make-array (list rows cols))))
    (loop for r below rows
          do (loop for c below cols
                   do (setf (aref result r c)
                            (funcall f (aref grid r c)))))
    result))

(map-grid #'1+ (make-array '(2 3)
                            :initial-contents '((1 2 3) (4 5 6))))
;=> #2A((2 3 4) (5 6 7))Code language: Lisp (lisp)

多次元配列には loop across は使えません。across はベクタ専用です。7
次元を問わず全要素を走査したいときは row-major-aref を使います。

5.2. array-row-major-index と行優先順

多次元配列の内部では要素が1列に並んでいます。

この並び順を「行優先」といい、一番右の次元が最も速く変化します。8

array-row-major-index は多次元インデックスを行優先の通し番号に変換し、row-major-aref は通し番号で要素にアクセスします。

(defun flatten-grid (grid)
  "グリッドを行優先で1次元ベクタに変換する"
  (let* ((total (array-total-size grid))
         (v (make-array total)))
    (loop for i below total
          do (setf (aref v i) (row-major-aref grid i)))
    v))

(flatten-grid (make-array '(2 3)
                           :initial-contents '((1 2 3) (4 5 6))))
;=> #(1 2 3 4 5 6)Code language: Lisp (lisp)

全要素を一括で処理したいだけなら、row-major-aref を使ったループが多重ループより簡潔に書けます。

(defun grid-sum (grid)
  (loop for i below (array-total-size grid)
        sum (row-major-aref grid i)))

(grid-sum (make-array '(3 3)
                      :initial-contents '((1 2 3) (4 5 6) (7 8 9))))
;=> 45Code language: Lisp (lisp)

6. 実用例

6.1. グリッド・盤面

迷路やゲームの盤面を表現するのが典型的な用途です。

行を外ループ、列を内ループにするのが行優先の走査になります。

(defun make-grid (rows cols &optional (init 0))
  (make-array (list rows cols) :initial-element init))

(defun print-grid (grid)
  (let ((rows (array-dimension grid 0))
        (cols (array-dimension grid 1)))
    (loop for r below rows
          do (loop for c below cols
                   do (format t "~a " (aref grid r c)))
             (terpri))))

(let ((g (make-grid 3 4 0)))
  (setf (aref g 1 2) 1)
  (print-grid g))
; 0 0 0 0
; 0 0 1 0
; 0 0 0 0Code language: Lisp (lisp)

6.2. 4近傍の探索

グリッド上で上下左右の隣接セルを調べるパターンです。

範囲チェックを関数に切り出しておくと、迷路の BFS や塗りつぶしで使い回せます。9

(defun neighbors-4 (grid r c)
  "セル (r, c) の4近傍で範囲内のものをリストで返す"
  (let ((rows (array-dimension grid 0))
        (cols (array-dimension grid 1)))
    (loop for (dr dc) in '((-1 0) (1 0) (0 -1) (0 1))
          for nr = (+ r dr)
          for nc = (+ c dc)
          when (and (<= 0 nr) (< nr rows)
                    (<= 0 nc) (< nc cols))
            collect (list nr nc))))

(let ((g (make-grid 3 4)))
  (neighbors-4 g 1 1))
;=> ((0 1) (2 1) (1 0) (1 2))Code language: Lisp (lisp)

6.3. DPテーブル

動的計画法のテーブルとして2次元配列を使うのも定番です。

ナップサック問題や編集距離の計算がよくある例です。10

(defun edit-distance (s t-str)
  "文字列 s と t-str の編集距離を返す"
  (let* ((m (length s))
         (n (length t-str))
         (dp (make-array (list (1+ m) (1+ n)) :element-type 'fixnum
                                               :initial-element 0)))
    ;; 初期化
    (loop for i from 0 to m do (setf (aref dp i 0) i))
    (loop for j from 0 to n do (setf (aref dp 0 j) j))
    ;; DP
    (loop for i from 1 to m
          do (loop for j from 1 to n
                   do (setf (aref dp i j)
                            (if (char= (char s (1- i)) (char t-str (1- j)))
                                (aref dp (1- i) (1- j))
                                (1+ (min (aref dp (1- i) j)
                                         (aref dp i (1- j))
                                         (aref dp (1- i) (1- j))))))))
    (aref dp m n)))

(edit-distance "kitten" "sitting")
;=> 3Code language: Lisp (lisp)

6.4. 隣接行列

グラフの辺を2次元配列で表現します。

頂点数が少ないとき、隣接リストより単純に書けます。11

(defun make-adjacency-matrix (n)
  (make-array (list n n) :element-type 'bit :initial-element 0))

(defun add-edge (matrix u v)
  (setf (aref matrix u v) 1)
  (setf (aref matrix v u) 1))

(defun edge-p (matrix u v)
  (= 1 (aref matrix u v)))

(let ((m (make-adjacency-matrix 4)))
  (add-edge m 0 1)
  (add-edge m 1 2)
  (add-edge m 2 3)
  (list (edge-p m 0 1) (edge-p m 0 2)))
;=> (T NIL)Code language: Lisp (lisp)

element-type 'bit にするとメモリを節約できます。

重みつきグラフなら 'fixnum や 'single-float を指定します。

7. 3次元配列の使い方

3次元配列は「2次元の平面が複数枚ある」と考えると直感的です。

(深さ 行 列) の順にインデックスを取るのが一般的です。

7.1. 時間軸付き盤面（時間DP）

時刻ごとに盤面の状態を保持するパターンです。

「時刻 t のセル (r, c) の値」を (aref dp t r c) で参照します。12

(defun make-time-grid (time-steps rows cols &optional (init 0))
  (make-array (list time-steps rows cols) :initial-element init))

(defun time-dp-example (t-max rows cols)
  "時刻ごとの各セルの到達コスト（最小化）を計算する例"
  (let ((dp (make-time-grid t-max rows cols most-positive-fixnum)))
    ;; 時刻0の開始点を初期化
    (setf (aref dp 0 0 0) 0)
    dp))

(let ((dp (time-dp-example 3 4 4)))
  (aref dp 0 0 0))
;=> 0Code language: Lisp (lisp)

7.2. RGB画像バッファ

(高さ 幅 チャンネル) の3次元配列で画像を表現します。

チャンネルは R・G・B の3値なのでサイズ3です。

(defun make-image (height width)
  (make-array (list height width 3)
              :element-type '(unsigned-byte 8)
              :initial-element 0))

(defun pixel-ref (img r c channel)
  (aref img r c channel))

(defun set-pixel (img r c r-val g-val b-val)
  (setf (aref img r c 0) r-val
        (aref img r c 1) g-val
        (aref img r c 2) b-val))

(let ((img (make-image 4 4)))
  (set-pixel img 1 2 255 128 0)
  (list (pixel-ref img 1 2 0)
        (pixel-ref img 1 2 1)
        (pixel-ref img 1 2 2)))
;=> (255 128 0)Code language: Lisp (lisp)

(unsigned-byte 8) は 0〜255 の整数に型を特化させる指定です。13
SBCLでは内部表現が最適化され、メモリ効率が改善します。

7.3. ボクセルデータ

3次元空間を格子状に区切ったボクセルも同じ構造で表現できます。

(x y z) の順でインデックスを割り当てます。14

(defun make-voxel-grid (x-size y-size z-size)
  (make-array (list x-size y-size z-size)
              :element-type 'bit
              :initial-element 0))

(defun voxel-set (grid x y z)
  (setf (aref grid x y z) 1))

(defun voxel-get (grid x y z)
  (= 1 (aref grid x y z)))Code language: Lisp (lisp)

8. 4次元以上の配列

make-array は次元数に制限がなく、4次元以上も同じ構文で作れます。

動画データの例として、(フレーム 高さ 幅 チャンネル) の4次元配列が考えられます。

(defun make-video-buffer (frames height width)
  (make-array (list frames height width 3)
              :element-type '(unsigned-byte 8)
              :initial-element 0))

;; フレーム0 のピクセル (10, 20) のR値を取り出す
(let ((video (make-video-buffer 30 480 640)))
  (setf (aref video 0 10 20 0) 200)
  (aref video 0 10 20 0))
;=> 200Code language: Lisp (lisp)

次元が増えるほど、インデックスの意味を覚えにくくなります。

4次元以上になったら、構造体やハッシュテーブルで意味のある名前をつけた方が管理しやすくなります。15

;; 4次元配列より、構造体で管理する方が読みやすいケースも多い
(defstruct video-frame
  data      ; 2次元配列
  timestamp
  index)Code language: Lisp (lisp)

9. displaced-to で行を切り出す

displaced-to で多次元配列の一部をコピーなしで参照できます。

2次元配列から1行だけを1次元配列として切り出す用途が典型的です。16

(defun row-view (matrix r)
  "行列の r 行目を1次元ベクタとして参照する（コピーしない）"
  (let ((cols (array-dimension matrix 1)))
    (make-array cols
                :displaced-to matrix
                :displaced-index-offset (* r cols))))

(let* ((m (make-array '(3 4)
                      :initial-contents '((1  2  3  4)
                                          (5  6  7  8)
                                          (9 10 11 12))))
       (row1 (row-view m 1)))
  row1)
;=> #(5 6 7 8)Code language: Lisp (lisp)

このビューへの書き込みは元の行列に反映されます。

コピーが不要な分、大きな行列を扱うときにメモリを節約できます。

10. まとめ表

多次元配列に関係する関数と操作を整理します。17

用途関数・オプション
作成make-array '(r c ...) :initial-element :initial-contents
読み書きaref setf aref row-major-aref
次元情報array-rank array-dimensions array-dimension array-total-size
型確認arrayp array-element-type
行切り出しdisplaced-to displaced-index-offset
行優先変換array-row-major-index row-major-aref
型特化:element-type 'fixnum 'single-float 'bit '(unsigned-byte 8)
型宣言(simple-array fixnum (* *)) declare optimize

次元ごとの主な用途です。

次元代表的な用途
2次元グリッド、DPテーブル、隣接行列、行列演算
3次元時間軸付き盤面、RGB画像バッファ、ボクセル
4次元動画バッファ（フレーム×高さ×幅×チャンネル）
5次元以上構造体やハッシュテーブルへの切り替えを検討
  1. #nA の n は次元数を表す整数で、#2A・#3A のように書きます。リーダーマクロとしての #nA 構文は CLHS で規定されており、#(...) と同様にコードの読み込み時に処理系がオブジェクトを生成します。 – CLHS: 2.4.8.12 Sharpsign A
  2. CLHSでは「initial-contents はシーケンスのネスト構造で構成され、構造のレベル数は配列のランクと等しくなければならない」と規定されています。各葉は element-type で指定した型でなければならず、initial-element と同時には指定できません。 – CLHS: Function MAKE-ARRAY
  3. CLHSでは配列の次元数の上限を array-rank-limit という定数で規定しており、最低でも8以上であることが保証されています。つまりすべての処理系でランク0〜7の配列が使えます。同様に各次元のサイズの上限は array-dimension-limit、全要素数の上限は array-total-size-limit で参照でき、いずれも少なくとも1024以上の正の fixnum です。 – CLHS: Constant ARRAY-RANK-LIMIT
  4. CLHSでは aref に渡すインデックスの個数は配列のランクと一致しなければならないと規定しています。多次元配列に対してインデックスが1つだけの場合は型エラーになります。インデックスの評価順序は左から右の順に保証されています。 – CLHS: Function AREF
  5. SBCLでは fixnum 特化配列の要素はタグなしの整数としてメモリに直接並びます。汎用配列はすべての要素がLispオブジェクトへのポインタとして格納されるため、数値演算のたびにボックス化とアンボックスが発生します。element-type を絞ることでこの変換コストがなくなります。 – The Common Lisp Cookbook – Performance Tuning and Tips
  6. CLHSでは optimize の safety 品質を0にすると、実行時エラーチェックが処理系の裁量で省略されます。値0は「まったく重要でない」、3は「最重要」を意味します。(safety 0) と (speed 3) の組み合わせは型宣言が正しいことを前提に最大限の最適化を行うため、宣言と実際の型が食い違うとクラッシュや不定動作の原因になります。 – CLHS: Declaration OPTIMIZE
  7. CLHSの loop 仕様では across 節はシーケンスを対象としており、多次元配列はシーケンスではないため対象外になります。シーケンスとはリスト・ベクタ・文字列を指す概念で、多次元配列はこれに含まれません。 – CLHS: 6.1.2.1.3 The across subclause
  8. 行優先順（row-major order）はC言語の多次元配列と同じ並び順です。対してFortranやMATLABは列優先順（column-major order）を採用しています。Common LispのCLHSでは行優先順が明示的に規定されており、array-row-major-index はこの順序に基づいてインデックスを計算します。 – CLHS: Function ARRAY-ROW-MAJOR-INDEX
  9. BFSは幅優先探索（Breadth-First Search）の略で、始点から近い順にノードを探索するアルゴリズムです。グリッド上の最短経路問題では、キューを使って隣接セルを順に調べ、訪問済みフラグで重複を防ぐのが基本パターンになります。 – Breadth First Traversal (BFS) on a 2D array – GeeksforGeeks
  10. 編集距離はレーベンシュタイン距離とも呼ばれ、ソビエトの数学者ウラジーミル・レーベンシュタインが1965年に定義したアルゴリズムです。1文字の挿入・削除・置換の最小操作数で2つの文字列の差異を計測します。"kitten" から "sitting" への編集距離3という結果はこのアルゴリズムの例としてよく引用されます。 – Levenshtein distance – Wikipedia
  11. 隣接行列は頂点数 n に対して O(n²) のメモリを消費しますが、辺の有無を O(1) で判定できます。一方、隣接リストは辺数 e に対して O(n + e) のメモリで済む代わりに、辺の有無の確認は O(degree) になります。グラフが疎な場合は隣接リストの方がメモリ効率に優れます。 – Graph representations using set and hash – GeeksforGeeks
  12. most-positive-fixnum はSBCLの64bit環境では 4611686018427387903（2の62乗 – 1）です。初期値として使うことで「未到達」を表現するのが時間DPの定番パターンです。CLHSでは most-positive-fixnum は少なくとも 2¹⁵ – 1 以上と規定されており、実際の値は処理系依存になります。 – The Common Lisp Cookbook – Numbers
  13. (unsigned-byte 8) は CLHSで定義された型指定子で、0以上255以下の整数を表します。SBCLではこの型特化配列を内部的にバイト配列として格納するため、汎用配列と比べてメモリ使用量が大幅に小さくなります。これは画像や音声のような大規模なバイト列を扱う際に特に有効です。 – CLHS: Type UNSIGNED-BYTE
  14. ボクセルは3次元のピクセルに相当する概念で、立体データを均一な格子で表現します。医療用CT・MRI画像の3次元再構成、3Dゲームのマインクラフト型地形表現、科学的シミュレーションでの流体・密度場のモデリングなどに使われます。 – Voxel – Wikipedia
  15. CLHSでは defstruct によって定義された構造体はスロットごとにアクセサ関数が自動生成されます。配列インデックスの数値ではなくスロット名でアクセスできるため、次元数が多いデータのコードの可読性が上がります。多次元配列と構造体の組み合わせも有効で、構造体の各スロットに2次元配列を持たせる設計も一般的です。 – CLHS: Macro DEFSTRUCT
  16. CLHSによると、displaced arrayは自分自身の記憶領域を持たず、参照先の配列に処理系が暗黙的にアクセスします。displaced arrayを参照している限り、GCは参照先の元配列を回収できません。逆にいえば、displaced arrayが生存している間は元配列を明示的に保持しなくても解放されません。元配列を adjust-array でサイズ変更するとdisplaced arrayの内容が未定義になる点にも注意が必要です。 – CLHS: Function MAKE-ARRAY
  17. 多次元配列を扱うサードパーティライブラリとして array-operations（Quicklisp経由で入手可能）があります。generate・permute・displace・flatten・reshape などの関数を提供しており、CLHSの標準関数だけでは書きにくい変形・スライス操作を簡潔に記述できます。 – array-operations – GitHub