Haskellで単にn回7を掛けるだけでもO(n ^ 2.6)の時間がかかる
追記: このタイトルはミスリーディングで、きっちり末尾再帰にすればO(n ^ 2)になります。
k.inaba (略) とりあえず多倍長とGCと原因切り分けませんか
http://shinh.skr.jp/m/?date=20100721#c01
ということでとりあえず多倍長計算だけしてみた。(追記: これじゃ末尾再帰じゃないからスタックが伸びていってしまうじゃん、と指摘された。光成さんの末尾再帰版のコードではO(n^2)になった。下の方に自分で書いた末尾再帰版を追記。)
import System pow :: Integer -> Integer pow 0 = 1 pow n = (7 *) $! pow (n - 1) main = do args <- getArgs print $ (0 *) $ pow $ read $ args !! 0
ここでf(x) = (x ** a) * b, g(x) = c * x * xで、X軸はコマンドライン引数で与えるn、Y軸は処理にかかった秒数。下記のように作成した。
gnuplot> f(x) = (x ** a) * b gnuplot> fit f(x) "result.txt" via a, b (..snip..) Final set of parameters Asymptotic Standard Error ======================= ========================== a = 2.60015 +/- 0.09175 (3.529%) b = 2.3844e-13 +/- 2.772e-13 (116.3%) (..snip..) gnuplot> g(x) = x * x * c gnuplot> fit g(x) "result.txt" via c (..snip..) c = 4.1331e-10 +/- 1.394e-11 (3.373%) (..snip..) gnuplot> plot f(x), g(x), "result.txt"
なおGHC 6.10.4を使った。
GCプロファイルとやらもやってみるか。
./a.out 200000 +RTS -s 0 7,493,614,152 bytes allocated in the heap 644,664 bytes copied during GC 2,084,040 bytes maximum residency (2 sample(s)) 1,049,272 bytes maximum slop 5 MB total memory in use (1 MB lost due to fragmentation) Generation 0: 13674 collections, 0 parallel, 4.83s, 5.02s elapsed Generation 1: 2 collections, 0 parallel, 0.00s, 0.00s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 7.14s ( 7.35s elapsed) GC time 4.83s ( 5.02s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 11.97s ( 12.37s elapsed) %GC time 40.4% (40.6% elapsed) Alloc rate 1,050,088,044 bytes per MUT second Productivity 59.6% of total user, 57.7% of total elapsed
GCが処理時間の40%を食っていることはわかった。他の見所がよくわからない。
こう書き換えてみる。多倍長演算ではあるが、桁数がO(n)で増えていかないようにしたのだ。
pow n = (77777777777777777777 +) $! pow (n - 1)
実行時間が短くて、イニシャルコストがグラフ上ではっきり見えるくらいあるのはフィッティングとしてどうなのかという気がするが、まあO(n ^ 2.6)じゃなくてO(n ^ 2)だと言っていいだろう。え?O(n ^ 2)???
a = 1.99989 +/- 0.114 (5.703%) b = 2.13455e-12 +/- 3.064e-12 (143.5%) c = 2.13161e-12 +/- 4.891e-14 (2.295%)
GCにはあんまり差がない。
./a.out 200000 +RTS -s 0 28,422,680 bytes allocated in the heap 6,416 bytes copied during GC 2,084,040 bytes maximum residency (2 sample(s)) 1,048,824 bytes maximum slop 5 MB total memory in use (1 MB lost due to fragmentation) Generation 0: 45 collections, 0 parallel, 0.02s, 0.02s elapsed Generation 1: 2 collections, 0 parallel, 0.01s, 0.01s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 0.05s ( 0.06s elapsed) GC time 0.03s ( 0.03s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.08s ( 0.09s elapsed) %GC time 35.1% (33.7% elapsed) Alloc rate 538,644,986 bytes per MUT second Productivity 64.0% of total user, 59.0% of total elapsed
Haskell難しいなぁ。よくわからない。
最初のコードは末尾再帰じゃないじゃないかと指摘されたので書きなおしてみたらO(n ^ 2)になりました。
import System pow :: Integer -> Integer -> Integer pow x 0 = x pow x n = pow (7 * x) (n - 1) main = do args <- getArgs print $ (0 *) $ pow 1 $ read $ args !! 0