4

Haskell でProject Euler #14の解決にしばらく取り組んでいますが、何らかの理由でそれを機能させることができません。少し前にGroovyを使用して問題を解決しましたが、ここでも基本的に同じ方法を使用していると思います。しかし、プログラムは最初の 10,000 の長さを見つけるだけでも信じられないほど遅く実行され、その理由について今では本当に迷っています。メモ化を正しく使用していると思いますが、GHCI の小さなデータ セットでもメモリが不足しています。

これが私がこれまでに思いついたものです。

collatz = (map collatz' [0..] !!)
    where collatz' n
        | n == 1 = 1
        | n `mod` 2 == 0 = 1 + collatz (n `div` 2)
        | otherwise = 1 +  collatz (3 * n + 1)

map collatz [1..1000000]問題の答えを得るために実行しmap collatz [1..10000]ていましたが、メモリ不足エラーが発生し、実行が完了するまでに数秒かかりました。

このプログラムの問題点について誰かが私に洞察を与えることができれば、それは素晴らしいことです! 私は多くのことを試しましたが、行き詰まっており、手を必要としています。

ありがとう！

4

1 に答える 1

6

メモ化はここでうまく機能しています。実際、それは非常にうまく機能しているため、すべてのメモリがいっぱいになります。コラッツ数列の中間項はかなり大きくなっています。1up toで始まる任意のシーケンスで発生する最大の項1000000は、 number2974984576です。したがって、これはメモリに構築しようとしているリストの長さです。

一方、メモ化せずにCollat​​z関数を直接実装するだけでも、この問題にはうまくいくはずです。

于 2012-08-07T16:30:49.533 に答える