読者です 読者をやめる 読者になる 読者になる

リストのコピー(末尾に追加 vs push&nreverse)

common lisp sbcl speed

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を併用する方法でも別に問題なさそう。

*1:かつ、リストを破壊的に修正できないところ

*2:実際、GC処理が入った場合は、全体の時間の3/4以上はGCが占めていた。その時のゴミの状況によって処理時間もだいぶ変わるので、copy1とcopy2の総処理時間が逆転することは珍しくなかった。