リストのコピー(末尾に追加 vs push&nreverse)
sbclのソースを読んでいたら、次のようなコードを目にした。
;;; sbcl-1.0.29/src/code/seq.lispのlist-remove-duplicates*関数からの抜粋 (let* ((result (list '())) (splice result) (current list)) ; listは引数で渡されたリスト #|...|# (do (#|...|#) (#|...|#) ;; ↓ ここは何をしている？ (setq splice (cdr (rplacd splice (list (car current))))) (setq current (cdr current))) #|...|#)
コメントにある通り、最初はこれが何をしているコードなのか分からなかったのだが、よく見てみると何のことはなく、listの要素をコピーして結果をresultに格納しているだけであった。
これを少し整理して、関数にまとめると次のようなものとなる。
;; listの要素を、resultにコピーする関数: ;; コピー先のリスト(result)の末尾を指すポインタ(tail)を保持しておくことで、 ;; リスト(result)の末尾への要素の追加を可能にしている。 ※ <=> push関数は前方への追加のみ可能 (defun copy1 (list) (declare '(optimize (speed 3) (debug 0) (safety 0) (compilation-speed 0))) (let* ((result (list '())) (tail result)) ; tail は result の末尾(の一つ前?)を指している: (eq tail (last result)) ==> T (dolist (elem list) (setq tail (cdr (rplacd tail (list elem))))) ; tail(= result)のcdr部に要素を付け足し、その後tailを一つ進める (cdr result)))
リストの場合、これとは別に(おそらく)より一般的なpush関数とnreverse関数を併用するコピーイディオムもあり、自分は普段はそちらを使用することの方が多い(こちらの方が個人的には分かりやすく、再帰との相性も良いので)。
;; pushとnreverseを併用する方法 (defun copy2 (list) (declare '(optimize (speed 3) (debug 0) (safety 0) (compilation-speed 0))) (let ((result '())) (dolist (elem list) (push elem result)) ; resultの前方に要素を追加していく (nreverse result))) ; 逆順に挿入されているのでリバースする #| ;; ループとpushの代わりに、再帰とconsを使う方法: 実際にはこちらの方が良く使う (defun copy2 (list &optional result) (if (null list) (nreverse result) (copy2 (cdr list) (cons (car list) result)))) |#
以前は、速度が気になるところ*1では、僕も前者の方法を使ったりしていたのだが、最近は後者でも十分速い気がして、そうすることは少なくなった。
今回少し気になったので、両者の速度を比べてみた。
以下、結果:
;; 500万要素のリストを用意 > (defparameter *huge-list* (loop repeat 5000000 collect 0)) ;; リストの末尾に追加してコピーする場合 > (sb-sys:without-gcing (time (progn (copy1 *huge-list*) 'done))) Evaluation took: 0.039 seconds of real time 0.040002 seconds of total run time (0.040002 user, 0.000000 system) 102.56% CPU 124,373,183 processor cycles 40,001,536 bytes consed --> DONE ;; リストの前方に追加して、その後リバースする場合 > (sb-sys:without-gcing (time (progn (copy2 *huge-list*) 'done))) Evaluation took: 0.046 seconds of real time ; 0.007秒遅い: nreverse分? 0.044003 seconds of total run time (0.044003 user, 0.000000 system) 95.65% CPU 144,006,386 processor cycles 40,001,536 bytes consed --> DONE
copy1の方が速かった。ただし、それほど大きな差ということはない。
上の比較では、正確な計時のためにGCを切っているが、実際にはそのための時間も必要になるので、両者の速度差はより曖昧なものになると思われる*2。
なので、大抵のケースではpushとnreverseを併用する方法でも別に問題なさそう。
