LISPで配列（APG4b EX18）

呼び水的初心者アウトプット風LISP記事第三弾．第二弾にて，コンスセルやリスト構造について扱ったので，今回は配列にしました．記述例は引き続きCommon Lisp（SBCL）です．

配列を扱う関数・構文

配列表記およびmake-array

1次元配列（ベクタ）は，S式によるリスト表現の頭に（'ではなく）#を付けます．n次元（n≧2）の場合は#nAとします．

* #(A B)
#(A B)
* #2A((A B) (C D))
#2A((A B) (C D))
* #3A(((A B) (C D)) ((E F) (G H)))
#3A(((A B) (C D)) ((E F) (G H)))

S式表記ではなく関数で配列を生成する場合は，make-arrayを用います．要素数を指定する必要があり，2次元以上はリストで示します．初期値は:initial-elementで指定します（デフォルト値は0）．

* (make-array 2)
#(0 0)
* (make-array '(2 2))
#2A((0 0) (0 0))
* (make-array '(2 2 2))
#3A(((0 0) (0 0)) ((0 0) (0 0)))
* (make-array '(2 2 2) :initial-element 'A)
#3A(((A A) (A A)) ((A A) (A A)))

arefおよび値の変更

arefは，添字で配列の値を参照する関数です．

* (aref #(A B) 0)
A
* (aref #(A B) 1)
B
* (aref #2A((A B) (C D)) 0 0)
A
* (aref #2A((A B) (C D)) 1 1)
D
* (aref #3A(((A B) (C D)) ((E F) (G H))) 1 1 1)
H

配列の値を変更する場合は，属性リストの値変更と同じくsetf構文を用います．Common Lispでは，配列に限らず，参照する関数と組み合わせて値を変更するためにsetfを用います．

* (defparameter DIM #2A((A B) (C D)))
DIM
* (aref DIM 1 0)
C
* (setf (aref DIM 1 0) 'Z)
Z
* DIM
#2A((A B) (Z D))

なお，上記実行例のdefparameterは，値に新しく記号を対応付けるための構文です．

利用例：APG4b EX18

配列の利用例として，AtCoderのAtCoder Programming Guide for beginners (APG4b)の多次元配列問題『EX18 - ゲーム大会』の解答例をCommon Lispで書き直してみました．本来はC++学習用ですが，AtCoderではC++以外の多くのプログラミング言語でも解答を提出することができ，結果を得ることができます．下記コードは次のスコアで正解（AC）しています．

【実行時間】23 ms
【メモリ】26264 KB
【コード長】523 Byte

(let* ((N (read))
       (M (read))
       (A (make-array M))
       (B (make-array M))
       (L (make-array (list N N) :initial-element "-")))
  (dotimes (i M)
    (setf (aref A i) (read))
    (setf (aref B i) (read)))
  (dotimes (i M)
    (decf (aref A i))
    (decf (aref B i))
    (setf (aref L (aref A i) (aref B i)) "o")
    (setf (aref L (aref B i) (aref A i)) "x"))
  (dotimes (i N)
    (dotimes (j N)
      (princ (aref L i j))
      (if (eq j (- N 1))
          (terpri)
          (princ " ")))))

上記プログラムのうち，let*は値に記号を一時的に対応付ける構文，dotimesは繰り返しの構文，decfはデクリメントを行う構文，readは入力関数，princは出力関数，terpriは改行を出力する関数です．

（おまけ）リスト処理の場合

参考までに，同じ問題をリスト処理および再帰関数処理のみで記述したのが次のコードです．こちらも正解していますが，実行時間，使用メモリ，コード長共に，配列を用いた記述と比べて数倍となっています．これは，配列を用いた場合は値の書き換えおよび単純な繰り返しで処理を行っているのに対し，こちらは，値を変更するたびにリスト構造をコピーしていることに加え，最適化が行われない非末尾再帰型の関数処理を繰り返しているためです．

【実行時間】423 ms
【メモリ】85992 KB
【コード長】1030 Byte

(labels ((readmatch (m)
           (if (= m 0) nil
               (cons (cons (read) (read))
                     (readmatch (- m 1)))))
         (makecheck (AB n c)
           (if (null AB) "-"
               (let ((r (car AB)))
                 (cond ((equal r (cons n c)) "x")
                       ((equal r (cons c n)) "o")
                       (t (makecheck (cdr AB) n c))))))
         (makematchn (AB n c)
           (if (= n 0) nil
               (cons (makecheck AB n c)
                     (makematchn AB (- n 1) c))))
         (makematch (AB c n)
           (if (= c 0) nil
               (cons (makematchn AB n c)
                     (makematch AB (- c 1) n)))))
  (let ((NM (cons (read) (read))))
    (let ((r (makematch (readmatch (cdr NM))
                        (car NM) (car NM))))
      (mapc (lambda (x)
              (mapc (lambda (c) (princ c) (princ " "))
                    (reverse (cdr x)))
              (princ (car x))
              (terpri))
            (reverse r)))))

備考

更新履歴

• 2020-11-13：初版公開