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時間弱…。