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.lazy
のlappend
を使えばO(1)のはず)。
なお、Schemeには破壊版appendであるappend!もあります。こちらは毎回コピーされないので appendより速いですが、それでもappend!の度にリストを末尾までたどらなければならないので、 あんまり嬉しくはありません。速度よりもメモリ消費を抑えたい場合に使うことが多いです。
- hamayama(2014/10/13 01:02:29 UTC):情報ありがとうございます。参考になります。
直感は、何というか、データを処理する場合は先頭から、データを作る場合は末尾に追加という
先入観がありました。
こう思っていると、car, cdr でリストを処理するプログラムは理解できるのですが、
cons (+ reverse) でリストを作るプログラムについては、何で?となってしまいます。
自分としては、意外とはまりポイントでした。