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