Haskell で単純な dp アルゴリズムを実装しようとしています (これは Project Euler の Collatz 予想問題用です)。同等の c++ は次のとおりです。
map<int,int> a;
int solve(int x) {
if (a.find(x) != a.end()) return a[x];
return a[x] = 1 + /* recursive call */;
}
Haskell で書いたコードは次のようになりました。
solve :: (Memo, Int) -> (Memo, Int)
solve (mem, x) =
case Map.lookup x mem of
Just l -> (mem, l)
Nothing -> let (mem', l') = {- recursive call -}
mem'' = Map.insert x (1+l') mem'
in (mem'', 1+l')
(ここでは状態モナドを再実装しているだけだと思いますが、今のところ気にしないでください。) solve を呼び出すコードは、最大で K=1e6 のパラメーターに与えることができる最大値を見つけようとします。
foldl'
(\(mem,ss) k ->
let (mem',x') = solve (mem, k)
in (mem', (x', k):ss))
(Map.singleton 1 1, [(1,1)]) [2..100000]
上記のコードは、スタック オーバーフローで失敗します。これは、非常に大きな未評価のサンクを構築するため、当然のことです。なので使ってみた
x' `seq` (mem', (x',k):ss)
foldl' 内で、K=1e5 の正しい答えを計算します。しかし、これは K=1e6 では失敗します (12 秒でスタック オーバーフロー)。それから私は使ってみました
mem'' `seq` l' `seq` (mem'', 1+l')
解決の最後の行で、これは違いはありませんでした（スタックオーバーフローはまだです）。それから私は使ってみました
mem'' `deepseq` l' `seq` (mem'', 1+l')
おそらく、deepseq がマップ mem '' 全体をウォークスルーし、アルゴリズムの時間の複雑さが n*log(n) ではなく 2 次になるため、これは非常に遅くなります。
これを実装する正しい方法は何ですか? 計算全体を厳密にする方法がわからず、計算のどの部分でスタックオーバーフローが発生するのかよくわかりませんが、マップであると思われます。たとえば、配列を使用できますが、ここで何が間違っているのかを理解したいと思います。