Problem 14 その2

http://projecteuler.net/index.php?section=problems&id=14

コラッツ予想。1〜1,000,000 の数の中で1に収束するまでの遷移数が一番多い数は?

メモリ消費量を改善

n = 1 * 1000 * 1000 - 1

main = print $ maximumBy (\(_, a) (_, b) -> a `compare` b) $ zip [1..] $ collatz n

collatz:: (Integral a) => a -> [Int]
collatz n = memoCollatz
    where memoCollatz:: [Int]
          memoCollatz = 1 : [1 + (f i) | i <- [2..n]]
              where f:: (Integral a) => a -> Int
                    f i = let i' = if even i then i `div` 2 else 3 * i + 1 in
                               if (fromIntegral i') <= n
                                  then memoCollatz !! (fromIntegral (i' - 1))
                                  else 1 + f i'

前のやり方だと、1,000,000 より大きい数に遷移した際のメモリ消費量が多すぎる。
1,000,000 以上は弾くようにした。スタックサイズを30Mに設定

12918.77s user 108.30s system 97% cpu 3:43:03.37 total

4時間弱…。