haskell の fib は遅くない - 白のカピバラの逆極限 S.144-3

http://d.hatena.ne.jp/nishiohirokazu/20100622/1277208908
に驚愕するような話が書かれていて、要するに、

fib = 1:1:zipWith (+) fib (tail fib)

は遅いと。何に驚愕したかというと、3点しかとらずに、「O(N ** 2.6)である。」と結論づけていることだ。空間使用量が O(N**2) で増えていくコードなのだから、そんなの空間計算量が一時的に影響与えたと考えるのが自然だろうに、その可能性も潰さずに原因も考えずに結論を出している。そんな適当な実験をするんだ、ということだ。

ランダウの記号 O(f(n)) は n が無限大でどのような関数で押さえられるか、についての表現だ。なので実行時間を論じているときには、n が 10^6 みたいな小さい値の周辺でフィットする行為は実行時間のオーダーを推測する補助手段でしかない。

fib !! n は、理論的に実行時の動きを考えると O(n**2) になる。
遅延評価ではサンクをつくるがそれは定数倍しか時間に影響を与えないのは当然だと思う。

import System
import List

fib = 1:1:zipWith (+) fib (tail fib)

main = do
  args <- getArgs
  print $ (0 *) $ (fib !!) $ read $ args !! 0

はじめにとったデータ。

10000	0.06
20000	0.16
30000	0.28
40000	0.44
50000	0.66
60000	0.9
70000	1.23
80000	1.62
90000	2.1
100000	2.56
110000	3.18
120000	3.92
130000	4.48
140000	5.31
150000	6.21
160000	7.24
170000	8.33
180000	9.27
190000	10.56

ここまでは、綺麗に O(n**2) にのっている。

perl -e '$i=10000;while($i<10000000){print "$i ".substr(`/usr/bin/time -o /dev/stdout -f "%e %U %S %t %K %p %F %R %c" ./a.out $i +RTS -K200M`,2);$i+=10000;}' | tee out.txt

(ただし、定数はこのままではない)

10000	0.03	0.01	0.00	797	11
20000	0.08	0.06	0.00	836	16
30000	0.19	0.16	0.00	937	37
40000	0.33	0.30	0.01	1277	50
50000	0.50	0.45	0.01	1297	83
60000	0.81	0.71	0.02	1572	137
70000	0.99	0.93	0.02	1978	75
80000	1.32	1.27	0.02	2270	53
90000	1.75	1.70	0.02	2271	46
100000	2.19	2.15	0.02	2564	25
200000	11.23	11.15	0.07	4398	32
300000	30.13	29.99	0.13	6782	68
400000	63.98	63.55	0.22	8004	739
500000	114.39	114.01	0.33	9736	706
600000	180.20	179.69	0.44	11987	892
700000	270.16	269.50	0.59	13974	1217
800000	409.71	408.42	0.74	15703	3437
900000	579.54	578.00	0.93	16923	4353

はじめは O(n**2) にのっているが、3*10**6 あたりからわずかにはずれる。ここをとりだして O(n**2) じゃないと騒いでたって事だね。

遅延評価だと（正格評価のつもりでいると予想しないところでメモリを食う、ので、メモリを食うとGCの影響やメモリ階層の影響がフクザツなので）実行時間が読みづらい、というのはあると思う。けど、実行される演算の回数は、必要な演算は結局最後には全部呼ばれるので、深く考えず普通に数えればok

http://twitter.com/kinaba/status/16854299925