project euler problem 14

遅延評価の方が遅くなる場合なのがこの問題。

$ echo "main=print $ foldl (+) 0 [1..10^4]" > a.hs; ghc -v0 a.hs ; sleep 1; ./a
50005000
$ echo "main=print $ foldl (+) 0 [1..10^5]" > a.hs; ghc -v0 a.hs ; sleep 1; ./a
5000050000
$ echo "main=print $ foldl (+) 0 [1..10^6]" > a.hs; ghc -v0 a.hs ; sleep 1; ./a
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

１０＾６までメモリが持たない。

正格評価であるfoldl'を使うとできるようになる。
詳しくは http://itpro.nikkeibp.co.jp/article/COLUMN/20070403/267180/?ST=develop&P=1

$ echo "import Data.List;main=print $ foldl' (+) 0 [1..10^6]" > a.hs; ghc -v0 a.hs ; sleep 1; ./a
500000500000

これを使ってとく

import Data.List
main=print $ foldl' g (1,1) [(x,f(x,1))|x<-[1..10^6]]

f (n,m) |n==1=m
	|even n=f (div n 2,m+1)
	|odd n=f (n*3+1,m+1)

g x y=if snd x>snd y then x else y

$ time ./14
(837799,525)
real:0m48.821s,user:0m48.555s,sys:0m0.256s

自分の数より小さいものは一度解いているのにそれを再利用すればもっと速そうなので配列を勉強してみる。

array版

はじめてarrayを使ってみた
結果の再利用をしていないので実行時間もほぼ同じになった。

import Data.Array
import Data.List

main=print$ (\x->(x,a!x)) $ foldl' max2 1 [2..n]

max2 x y | a!x > a!y = x
	 | otherwise = y

f (n,m) |n==1=m
	|even n=f (div n 2,m+1)
	|odd n=f (n*3+1,m+1)

a=array (1,n) [(i,f (i,1))|i<-[1..n]]

n=10^6

$ time ./14
(837799,525)
real:0m49.197s,user:0m48.643s,sys:0m0.172s

とりあえずはここで終了。あとでもう少し工夫してみたい。