Haskell de script en cours d'exécution hors de l'espace

Question

J'utilise Euler du projet pour enseigner moi-même Haskell, et je vais avoir quelques problèmes raisonnant sur la façon dont mon code est en cours d'exécution par Haskell. Le deuxième problème m'a calculer la somme de tous les nombres pairs de Fibonacci jusqu'à 4 millions. Mon script ressemble à ceci:

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))

étreintes donne l'erreur « Collecte des ordures ménagères ne parvient pas à récupérer suffisamment d'espace », que je suppose signifie que les entrées de la liste ne sont pas libérés car ils sont consommés par foldr.

Que dois-je faire pour résoudre ce problème? J'ai essayé d'écrire une version récursive queue (je pense) qui a utilisé les accumulateurs, mais n'a pas pu obtenir que travailler soit.

Answer 1

Un certain nombre d'observations / indices:

• les x + sums de même ne sont pas évalués se jusqu'à la fin
• Vous prenez les premiers 4.000.000 bobards, pas les bobards jusqu'à 4.000.000
• Il y a un moyen plus facile de le faire

Modifier en réponse à des commentaires

Je ne vais pas vous dire ce que le plus simple est, puisque c'est le plaisir des problèmes du projet d'Euler. Mais je vais vous poser un tas de questions:

• Combien de même bobards pouvez-vous avoir dans une rangée?
• Combien de temps pouvez-vous aller sans même FIB?
• Si vous additionnez toutes les même bobards et tous les bobards impairs (faire la main), que remarquez-vous au sujet des sommes?

Answer 2

Tout d'abord, vous ne devriez pas utiliser des câlins. Il est un jouet uniquement à des fins d'enseignement.

GHC, cependant, est un compilateur rapide optimisation, multicœur prêt pour Haskell. Recevez votre article ici . En particulier, il fait l'analyse de la rigueur, et compile en code natif.

La principale chose qui se démarque de votre code est l'utilisation de foldr sur une très grande liste. Probablement que vous voulez une boucle récursive de queue. Comme ceci:

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))

En plus de tout cela, le premier 4M même bobards utilisera une quantité d'espace, donc ça va prendre un certain temps.

Voici la somme de la première 400k même bobards , pour sauver vous un certain temps (21s). : -)

Answer 3

Vous avez compris le faux problème. problème réel veut que vous additionnez tous les nombres pairs de Fibonacci tels que le Fibonacci nombre lui-même ne dépasse pas 4 millions (qui se trouve être seulement les 33 premiers nombres de Fibonacci).

Answer 4

Vous évaluez quatre millions d'éléments de fibs. Ces chiffres augmentent de manière exponentielle. Je ne sais pas combien d'octets sont nécessaires pour représenter le millionième numéro Fibonacci; juste le millième numéro Fibonacci a 211 chiffres décimaux, de sorte que ça va prendre 22 seulement des mots de 32 bits pour contenir les chiffres, jamais l'esprit tout gmp frais généraux impose. Et ceux-ci se développent de façon exponentielle.

Exercice:. Calculuate la quantité de mémoire nécessaire pour contenir quatre millions de numéros de Fibonacci

Answer 5

consulter les fonctions Prelude takeWhile, filtre, même, et somme

takeWhile (<40) [0 ..]
filtrer même takeWhile $ (<40) [0 ..]

mettre « em ensemble:

ans = somme filtre $ même takeWhile $ (<4 * 10 ^ 6) fibs