Gauche:リストの作成例

Gauche:リストの作成例

リストの作成例

リストを順番に作成していくときに、append よりも cons + reverse の方が
効率がよいとのことで、何となく実験してみました。
(参考ページ: http://saito.hatenablog.jp/entry/2014/03/28/184636 )

(use gauche.time)

;; 1からnumまでのりストを append で作成
(define (f1 num)
  (let1 lst '()
    (do ((i 1 (+ i 1)))
        ((> i num) #f)
      (set! lst (append lst (list i))))
    lst))

;; 1からnumまでのりストを cons + reverse で作成
(define (f2 num)
  (let1 lst '()
    (do ((i 1 (+ i 1)))
        ((> i num) #f)
      (set! lst (cons i lst)))
    (reverse lst)))

;; 実行
;(print "(f1 10)  : " (f1 10))
;(print "(f2 10)  : " (f2 10))
;(newline)
(print "(f1 100) : " (time-this 1000 (lambda () (f1 100))))
(print "(f2 100) : " (time-this 1000 (lambda () (f2 100))))
(newline)
(print "(f1 200) : " (time-this 1000 (lambda () (f1 200))))
(print "(f2 200) : " (time-this 1000 (lambda () (f2 200))))
(newline)
(print "(f1 400) : " (time-this 1000 (lambda () (f1 400))))
(print "(f2 400) : " (time-this 1000 (lambda () (f2 400))))
(newline)
(print "(f1 800) : " (time-this 1000 (lambda () (f1 800))))
(print "(f2 800) : " (time-this 1000 (lambda () (f2 800))))

結果は以下となりました(CPU:Celeron 1.73GHz, OS:WinXP, Gauche v0.9.4)

(f1 100) : #<time-result 1000 times/  0.578 real/  0.500 user/  0.047 sys>
(f2 100) : #<time-result 1000 times/  0.000 real/  0.000 user/  0.000 sys>

(f1 200) : #<time-result 1000 times/  2.172 real/  1.891 user/  0.250 sys>
(f2 200) : #<time-result 1000 times/  0.047 real/  0.047 user/  0.000 sys>

(f1 400) : #<time-result 1000 times/  8.750 real/  7.828 user/  0.812 sys>
(f2 400) : #<time-result 1000 times/  0.109 real/  0.109 user/  0.000 sys>

(f1 800) : #<time-result 1000 times/ 34.516 real/ 31.172 user/  2.797 sys>
(f2 800) : #<time-result 1000 times/  0.219 real/  0.204 user/  0.016 sys>

append だと N^2 に比例して時間がかかるようです。
直感的には、appendの方が自然のような気もしましたが。。。

Lisp/Schemeのリストが、片方向連結リストで前に追加しやすいデータ構造であることと、
appendが、引数を破壊的変更しないように最後の引数以外はコピーを行うことから、
このような結果になるようです。
上記の参考ページでは、図を使って分かりやすく書かれていました。

hamayama(2014/09/28 12:08:51 UTC)(2014/10/13 01:02:29 UTC)

Shiro(2014/09/28 14:02:27 UTC): 「直感」は、それまでに知っていることがらに大きく左右されますね。 Lispやリスト構造に限らず、繰り返し追加してゆくときにappendで効率が悪い言語は 多くあります(文字列とか)。基本的に大抵の言語では、 非破壊的appendをするものは繰り返しappendしちゃだめ、と思っていればいいんじゃないでしょうか。 (ただし、遅延評価のHaskellなどでは非破壊的でもappendの操作はO(1)です。 実際のappendは遅延されるのですが、append操作が実際に必要になる時には 既に前のリストの末尾まで読んでしまっているのでコピーの必要がないからです。 Gaucheでもgauche.lazylappendを使えばO(1)のはず)。

なお、Schemeには破壊版appendであるappend!もあります。こちらは毎回コピーされないので appendより速いですが、それでもappend!の度にリストを末尾までたどらなければならないので、 あんまり嬉しくはありません。速度よりもメモリ消費を抑えたい場合に使うことが多いです。

More ...