5

私は Haskell の初心者で、それを使用してProject Eulerの約 50 の問題を解決しましたが、今は問題 66で立ち往生しています。問題は、コンパイルされたコード ( ghc -O2 --make problem66.hs) が 10 ～ 20 秒後にマシンの空きメモリをすべて使用することです。私のコードは次のようになります。

-- Project Euler, problem 66

diophantine x y d = x^2 - d*y^2 == 1

minimalsolution d = take 1 [(x, y, d) | y <- [2..],
                            let x = round $ sqrt $ fromIntegral (d*y^2+1),
                            diophantine x y d]

issquare x = (round $ sqrt $ fromIntegral x)^2 == x

main = do
    print (map minimalsolution (filter (not . issquare) [1..1000]))

のリスト内包表記内の無限リストに問題があるという予感がありますminimalsolution。

私は実際、怠惰のために、Haskell は 1 つの要素が見つかるまで ( のためtake 1) リストを評価し、途中で がdiophantine評価されるすべてのものを破棄すると考えていましたFalse。私は間違っていますか？

興味深いことに、ghci ではこの動作は見られませんでした。ghci 内の処理が非常に遅いため、メモリ消費が爆発的に増加するのを確認するまで待たなければならないからですか?それとも別の理由でしょうか?

ネタバレはご遠慮ください。私が知りたいのは、極端なメモリ消費の原因と、それを修正する方法だけです。

4

3 に答える 3

1

の各値に不要な Double インスタンスを作成する内包表記の内部y。

スペースブローアップのないリスト内包表記を使用した解決策を見つけることができませんでした。ただし、再帰を使用して書き換えると、安定したメモリ プロファイルが得られます。

diophantine :: Int -> Int -> Int -> Bool
diophantine x y d = x^2 - d*y^2 == 1

minimalsolution ::  Int -> (Int, Int, Int)
minimalsolution d = go 2
  where
    d0 = fromIntegral d
    go a =
      let y = fromIntegral a
          x = round $ sqrt $ (d0*y^2+1) in
      if diophantine x y d then
        (x, y, d)
      else
        go (y+1)
于 2013-09-13T06:00:41.213 に答える