Project Euler #1, #2
Project EulerをHaskellで解いてみることにする(というか、元々Pythonで解いてて「これなら純関数型の方がやりやすくね？」と思ったのが発端)。
Problem #1は3または5の倍数を取り出す問題。これは特に問題なく書けた:
main :: IO () main = do print $ sum [ n | n <- [1..999], n `mod` 3 == 0 || n `mod` 5 == 0 ]
Problem #2はフィボナッチ数列の問題。Pythonでは既に解いていたので同じことをするだけだと思ったのだが、色々とつまづきポイントがあった。初学者だから仕方ないね。
最初に書いたのはこんなコード:
fib 1 = 1 fib 2 = 2 fib n = fib (n-1) + fib (n-2) main :: IO () main = do print $ sum $ filter even $ takeWhile (< 4000000) $ map fib [1..]
実は無限リストの扱いがよくわからず、ここまででも若干手こずった。当初は 4000000 未満の要素を取り出す処理をリスト内包や filter で書いて無限ループになっており、色々調べた結果 takeWhile が正解だとわかった。リスト内包や filter はあくまでフィルタ条件を指定するだけで、条件を満たさなくなったら打ち切るとは言ってないんだな。
それでさっきのコードだが、答えは正しい。しかし実行速度がクッソ遅い:
$ time python3 fib_even.py 4613732 python3 fib_even.py 0.02s user 0.00s system 88% cpu 0.023 total $ time runghc fib_even.hs 4613732 runghc fib_even.hs 12.82s user 0.08s system 100% cpu 12.889 total
コンパイルしてもまだPythonより遅い(-O2, -O3 は -O と変わらなかったので省略):
$ ghc -o fib_even fib_even.hs $ time ./fib_even 4613732 ./fib_even 1.34s user 0.01s system 99% cpu 1.358 total $ ghc -O -o fib_even fib_even.hs $ time ./fib_even 4613732 ./fib_even 0.35s user 0.01s system 99% cpu 0.368 total
調べてみたらこの件は約6年前に話題になっていたらしい:
この際だから全部読んで完全に理解…
するわけないだろ！いい加減にしろ！のっけからこういう闇が深そうな話には関わりたくないの！
つーわけでリンク先にあった末尾再帰版だけパクって試してみることにする:
fib 1 = 1 fib 2 = 2 fib n = fib' n 1 2 fib' 1 _ y = y fib' n x y = fib' (n-1) y (x+y) main :: IO () main = do print $ sum $ filter even $ takeWhile (< 4000000) $ map fib [1..]
これだと
$ time runghc fib_even.hs 4613732 runghc fib_even.hs 0.13s user 0.02s system 95% cpu 0.151 total
コンパイルなしでもPythonよりわずかに遅い程度で済むようだ。再帰で遅くなりすぎる場合は末尾再帰化を考えてみることにしよう。
というか今回は無限リストも絡んでたので、遅いだけなのか無限ループしてるのかわかりにくかったりして色々面倒だなーと思った（小並感）
