白のカピバラの逆極限 S.144-3

長文コメントはこれを歓迎します。
とりあえず、quizでも解いていきませんか、古いものほど面白いです

2010-07-16

haskell の fib は遅くない

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

はじめにとったデータ。

100000.06
200000.16
300000.28
400000.44
500000.66
600000.9
700001.23
800001.62
900002.1
1000002.56
1100003.18
1200003.92
1300004.48
1400005.31
1500006.21
1600007.24
1700008.33
1800009.27
19000010.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

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

100000.030.010.00000079711
200000.080.060.00000083616
300000.190.160.00000093737
400000.330.300.010000127750
500000.500.450.010000129783
600000.810.710.0200001572137
700000.990.930.020000197875
800001.321.270.020000227053
900001.751.700.020000227146
1000002.192.150.020000256425
20000011.2311.150.070000439832
30000030.1329.990.130000678268
40000063.9863.550.2200008004739
500000114.39114.010.3300009736706
600000180.20179.690.44000011987892
700000270.16269.500.590000139741217
800000409.71408.420.740000157033437
900000579.54578.000.930000169234353

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

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

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

wd0wd0 2010/07/18 13:59 幸か不幸か、問題の吉永本は版元品切れで、現在は「手に入りやすい本」ではなくなっています。

nucnuc 2010/07/19 02:43 ああ、良くも悪くも私の小さい頃とはだいぶ変わったのですね。