Problem 14 （その2：未解決）

わからない・・・どうやっても1000000で処理すると

 *** Exception: stack overflow

がでるか，異常な時間がかかってやってられない・・・むむーー．

前のコード

{-
Project Euler Problem 14 e14.hs
-}

collatz::Integer -> [Integer]
collatz n
    | n == 1    = [1]
    | otherwise = n:((collatz.next) n)
      where next:: Integer->Integer
            next n 
                | n `mod` 2 == 0 = n `div` 2
                | otherwise      = 3*n+1

collatzLengthList::[Integer] -> [(Integer, Integer)]
collatzLengthList = (map (\x -> (head x, (toInteger.length) x))) . (map collatz) 

getMax::[(Integer, Integer)] -> Integer
getMax = maximum .  map (\x -> snd x)

answer n =  filter (\x -> snd x == max) ns
    where ns = collatzLengthList [1..n]
          max = getMax ns

だと

 *Main> answer 100000
[(77031,351)]
(92.81 secs, 3510422796 bytes)
*Main>

時間がかかりすぎるように思います．なお，問題の1000000だと，あえなく

 *Main> answer 1000000
*** Exception: stack overflow
*Main>

となってしまう体たらく．

追記（2008/5/19）

スタックの領域が足りない！というなら増やしてあげればいいので，そうしてみます．mainを

import System.Environment

main = do args <- getArgs
          print $ answer $ read $ head args

と追加して，ghcでコンパイルして実行ファイル（e14）にして，

e14 1000000 +RTS -K30M

とやってみます（30Mは試行錯誤で適当に決定．デフォルトは8M）．stack overflowはでなくなるのですが，やたらと長い間待たされたあと，OSごと落ちてしまいました（苦笑）．やはり，こういう小手先では駄目そうです．

「計算を速くする」のと「stack overflowしない」のをうまく両立させる手を模索する方向で考えます．途中の計算結果を保持して計算量を減らす（キャッシュを作る）のはすでに5通りくらい作ったのですが，全部1000000でstack overflowを起こします（もっと実際はもっと小さい値で駄目）．さらに「キャッシュを作ってそれを保持する」「キャッシュを探索する」方に逆に時間やメモリをとられたり，そもそも「ヒットするキャッシュが少ない？」というケースもあるようで，むずかしいです．