Hatena::Groupcadr

kozima の日記

2009-06-10

10分でコーディング 続・破壊的操作編

| 00:06

なぜかふと思いついて、ちょうどいいお題だったので勝手に続編にしました。

行列のリストによる表現と転置

行列をリストのリストで表現します。例えば

 \left(\begin{array}{ccc}1&2&3\\4&5&6\\7&8&9\end{array}\right)

((1 2 3) (4 5 6) (7 8 9))

となります。

これの転置行列を計算する方法は、こんなふうに簡単に書けます。

(defun transpose (matrix) (apply #'mapcar #'list matrix))

(transpose '((1 2 3) (4 5 6) (7 8 9)))
;=> ((1 4 7) (2 5 8) (3 6 9))

転置後の

 \left(\begin{array}{ccc}1&4&7\\2&5&8\\3&6&9\end{array}\right)

に相当するリストが出てきてますね。

メモリ食うじゃん

上のように書くと、当然ですがメモリを消費します。転置しても要素数は同じなのだから、破壊的操作を使えばメモリを新たにアロケートすることなく転置できるのではと考えるのは自然でしょう。

じゃあやってみましょう、となるわけですが……実は一般にはできません。次の実行結果を見てください。

(defun make-matrix (m &optional (n m))
  (let ((x 0))
    (loop repeat m collect (loop repeat n collect (incf x)))))

(time (make-matrix 2 3))
;-> Real time: 0.0 sec.
;   Run time: 0.0 sec.
;   Space: 64 Bytes
;=> ((1 2 3) (4 5 6))

(time (make-matrix 3 2))
;-> Real time: 0.0 sec.
;   Run time: 0.0 sec.
;   Space: 72 Bytes
;=> ((1 2) (3 4) (5 6))

ということです。一般にはセルの個数が違うのです。

お題

でも、正方行列なら転置してもセルの個数は同じです。というわけで、正方行列が与えられたとき、それをメモリを消費することなく転置する関数を書いてください。動くものを書くだけなら難しくはないと思います。

実行例

とりあえず書くだけならすぐに書けたので動かしてみました。遅いことは分かっていたので、関数の名前を ntranspose-slow としています。

どのくらい遅いか試すため

(dolist (n '(100 200 300 400 500 600))
  (format t "~&N = ~D...~%" n)
  (let ((m (make-matrix n)))
    (time (ntranspose-slow m))))

こんなのを CLISPコンパイル後に実行してみました。結果は以下の通り。

N = 100...
Real time: 0.0 sec.
Run time: 0.0 sec.
Space: 0 Bytes
N = 200...
Real time: 0.078125 sec.
Run time: 0.078125 sec.
Space: 0 Bytes
N = 300...
Real time: 0.390625 sec.
Run time: 0.390625 sec.
Space: 0 Bytes
N = 400...
Real time: 1.0625 sec.
Run time: 1.0625 sec.
Space: 0 Bytes
N = 500...
Real time: 2.25 sec.
Run time: 2.25 sec.
Space: 0 Bytes
N = 600...
Real time: 4.0 sec.
Run time: 3.96875 sec.
Space: 0 Bytes

たぶん  O(n^3) ぐらいですね。

お題・上級編

上の実行例よりももっと速いやり方があると思います。それを考えてみてください。