displaced array
Common Lispにはdisplaced arrayと呼ばれるものがあります。
これは他の配列へのポインタのようなもので、CLHSでは以下のように定義されています。
displaced array n. an array which has no storage of its own, but which is instead indirected to the storage of another array, called its target, at a specified offset, in such a way that any attempt to access the displaced array implicitly references the target array.
(CLHS: Glossary-Section D)
試しに使ってみるとこんな感じです。
CL-USER> (defvar *a1* (make-array 5 :initial-contents '(a b c d e))) *A1* ; まずは普通の配列を作ります CL-USER> *a1* #(A B C D E) CL-USER> (defvar *a2* (make-array 3 :displaced-to *a1* :displaced-index-offset 1)) *A2* ; 続いて、*a1*をターゲットにしたdisplaced arrayを作ります CL-USER> *a2* #(B C D) ; *a2*の中身は*a1*の部分配列と同じです CL-USER> (setf (aref *a2* 1) 2009) 2009 ; *a*2の要素を一つ変更してみます CL-USER> *a2* #(B 2009 D) ; 確かに変更されました CL-USER> *a1* #(A B 2009 D E) ; *a1*の方にも影響がでます
これはなかなか面白いですね。
使用する領域も少なそうだし、部分配列を沢山作るような場面では、
displaced arrayを使うと大幅に使用領域を減らせるんじゃないかと思い、試してみました。
(defun s1 (str &optional (n 1)) (let (acc) (dotimes (i (- (length str) (1- n)) (nreverse acc)) (push (subseq str i (+ n i)) acc)))) (defun s2 (str &optional (n 1)) (let (acc) (dotimes (i (- (length str) (1- n)) (nreverse acc)) (push (make-array n :displaced-to str :displaced-index-offset i :element-type (array-element-type str)) acc))))
という訳で、意味はありませんが、とにかく部分配列を沢山作る関数を二つ用意しました。
引数は作成する配列の一つあたりのサイズです。
s1はsubseqを使い、配列のコピーを作るのに対して、
s2はdisplaced arrayを作るようにしています。
で、CLISPで両者を動かしてみました。
CL-USER> (time (progn (s1 *long-long-text* 1) nil)) Real time: 0.0200288 sec. Run time: 0.0200288 sec. Space: 112420 Bytes NIL CL-USER> (time (progn (s2 *long-long-text* 1) nil)) Real time: 0.0100144 sec. Run time: 0.0100144 sec. Space: 179872 Bytes NIL CL-USER> (length *long-long-text*) 5621 CL-USER> (time (progn (s1 *long-long-text* 100) nil)) Real time: 0.0 sec. Run time: 0.0 sec. Space: 640552 Bytes NIL CL-USER> (time (progn (s2 *long-long-text* 100) nil)) Real time: 0.0 sec. Run time: 0.0 sec. Space: 176704 Bytes NIL CL-USER> (time (progn (s1 *long-long-text* 1000) nil)) Real time: 0.0901296 sec. Run time: 0.0901296 sec. Space: 4695952 Bytes GC: 4, GC time: 0.0600864 sec. NIL CL-USER> (time (progn (s2 *long-long-text* 1000) nil)) Real time: 0.0 sec. Run time: 0.0 sec. Space: 147904 Bytes NIL
サイズ1の配列を作る場合はsubseqの方が使用領域が少ないですが、
サイズが大きな配列を作る場合はdisplaced arrayの方が圧倒的に少なくなりました。
Common Lispは(純粋)関数型言語のように副作用をあまり使わないプログラムが書ける一方で、
領域を共有するようなメモリを節約するプログラムも書けるのがいいですね。