2

プロジェクト Euler を使用して Haskell を独学していますが、自分のコードが haskell によってどのように実行されているかについて推論するのに苦労しています。2 番目の問題では、400 万までのすべての偶数フィボナッチ数の合計を計算する必要があります。私のスクリプトは次のようになります。

fibs :: [Integer]
fibs =  1 : 2 : [ a+b | (a,b) <- zip fibs (tail fibs)]

evens  :: Integer -> Integer -> Integer
evens x sum | (even x)   = x + sum
            | otherwise  = sum

main = do
  print (foldr evens 0 (take 4000000 fibs))

Hugs は、「ガベージ コレクションが十分なスペースを再利用できません」というエラーを表示します。これは、foldr.

これを修正するにはどうすればよいですか? アキュムレータを使用する末尾再帰 (と思う) バージョンを作成しようとしましたが、それも機能しませんでした。

4

5 に答える 5

8

まず、ハグを使用しないでください。教育用のおもちゃです。

ただし、GHC は Haskell 用の高速でマルチコア対応の最適化コンパイラです。ここで入手してください。特に、厳密性分析を行い、ネイティブ コードにコンパイルします。

コードで際立っている主な点は、非常に大きなリストでのfoldrの使用です。おそらく、末尾再帰ループが必要です。そのようです：

import Data.List

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

evens x sum | even x    = x + sum
            | otherwise = sum

-- sum of even fibs in first 4M fibs
main = print (foldl' evens 0 (take 4000000 fibs))

これらすべてに加えて、最初の 4M 偶数フィブはかなりの量のスペースを使用するため、しばらく時間がかかります。

時間を節約するために、最初の 400k 偶数 fibs の合計を次に示します(21 秒)。:-)

于 2009-04-10T03:44:59.840 に答える
6

いくつかの観察/ヒント:

  • からのx + sums は最後まで評価されません
  • 4,000,000 までのフィブではなく、最初の 4,000,000 回のフィブを取ります。
  • これを行う簡単な方法があります

コメントに応じて編集

オイラー計画の問題はそれが楽しいので、どちらがより簡単な方法かを説明するつもりはありません。しかし、私はあなたにたくさんの質問をします：

  • 偶数フィブを連続して何回持つことができますか?
  • 偶数フィブなしでどのくらい行くことができますか?
  • すべての偶数フィブとすべての奇数フィブを合計すると (これは手で行います)、合計について何がわかりますか?
于 2009-04-10T02:17:22.547 に答える
4

あなたは問題を間違って理解しました。実際の問題では、フィボナッチ数自体が 400 万を超えないように、偶数のフィボナッチ数をすべて合計する必要があります (これはたまたま最初の 33 フィボナッチ数のみです)。

于 2009-04-10T04:11:18.857 に答える
3

の 400 万要素を評価していfibsます。それらの数は指数関数的に増加します。100 万番目のフィボナッチ数を表すために必要なバイト数はわかりません。1000 分の 1 のフィボナッチ数には 211 桁の 10 進数があるため、桁を保持するだけで 22 個の 32 ビット ワードが必要になりますgmp。そして、これらは指数関数的に成長します。

演習: 400 万のフィボナッチ数を保持するために必要なメモリ量を計算します。

于 2009-04-10T02:14:42.273 に答える
2

Prelude 関数の takeWhile、filter、even、および sum を見てください。

takeWhile (<40) [0..]
フィルタ $ takeWhile (<40) [0..]

それらをまとめる：

ans = sum $ filter even $ takeWhile (< 4* 10^6) fibs

于 2009-04-11T05:19:33.117 に答える