Haskell Skript nicht mehr genügend Speicherplatz

StackOverflow https://stackoverflow.com/questions/736495

  •  09-09-2019
  •  | 
  •  

Frage

Ich verwende Projekt Euler selbst Haskell zu lehren, und ich einige Probleme, Argumentation, wie mein Code von Haskell ausgeführt wird. Das zweite Problem hat mich bis zu 4 Millionen die Summe aller geraden Fibonacci-Zahlen zu berechnen. Mein Skript sieht wie folgt aus: 

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

Umarmungen gibt den Fehler „Garbage Collection nicht ausreichend Platz zurückzuerobern“, die ich übernehmen bedeutet, dass die Listeneinträge werden nicht freigegeben, da sie von foldr verbraucht werden.

Was muss ich dieses Problem beheben tun? Ich habe versucht, einen Schwanz-rekursive zu schreiben (ich glaube) Version, die Akkumulatoren verwendet, konnte aber nicht, dass bekommen entweder zu arbeiten.

War es hilfreich?

Lösung

Eine Reihe von Beobachtungen / Hinweise:

  • die x + sums von selbst nicht bis zum Ende ausgewertet zu werden
  • Sie sind die ersten 4.000.000 fibs nehmen, nicht die fibs bis zu 4.000.000
  • Es ist ein einfacher Weg, um diesen
    • zu tun

Bearbeiten in Reaktion auf einen Kommentar

Ich werde Ihnen nicht sagen, was der einfachere Weg ist, denn das ist der Spaß von Project Euler Problemen ist. Aber ich werde fragen Sie ein paar Fragen:

  • Wie viele sogar fibs können Sie in einer Reihe haben?
  • Wie lange kann man ohne ein gehen sogar fib?
  • Wenn Sie alle selbst fibs zusammenzufassen und alle ungeraden fibs (tun dies von Hand), was fällt Ihnen über die Summen?

Andere Tipps

Zum einen sollten Sie nicht Umarmungen verwenden. Es ist ein Spielzeug für Lehrzwecke nur.

GHC ist jedoch ein schneller, Multi-Core-ready optimierenden Compiler für Haskell. es hier zu Holen. Insbesondere macht es Strikt Analyse und kompiliert zu nativen Code.

Die Hauptsache ist, die über Ihren Code auffällt, ist die Verwendung von foldr auf eine sehr große Liste. Wahrscheinlich wollen Sie einen Schwanz rekursive Schleife. Wie so: 

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

Neben all dies die erste 4M selbst wird fibs eine ganze Menge Raum verwenden, so dass es dann eine Weile dauern.

Hier ist die Summe der ersten 400k sogar fibs , zu speichern Sie einige Zeit (21s). : -)

Sie verstanden das Problem falsch. Die eigentliche Problem möchte, dass Sie alle auch Fibonacci-Zahlen, so dass die Fibonacci zusammenzufassen Nummer selbst nicht 4.000.000 nicht übersteigt (die nur die ersten 33 Fibonacci-Zahlen werden passiert).

Sie evaluieren vier Millionen Elemente fibs. Diese Zahlen wachsen exponentiell. Ich weiß nicht, wie viele Bytes benötigt, um die millionste Fibonacci-Zahl zu repräsentieren; nur die ein Tausendstel Fibonacci-Zahl hat 211 Dezimalstellen, so dass nur das wird 22 32-Bit-Worte zu ergreifen, um die Ziffern zu halten, nie erlegt, was Kopf gmp ausmacht. Und diese exponentiell wachsen.

Übung:. Calculuate die Menge an Speichern benötigte vier Millionen Fibonacci-Zahlen halten

haben einen Blick auf die Prelude Funktionen Takewhile, Filter, auch, und die Summe

Takewhile (<40) [0 ..]
Filter sogar $ Takewhile (<40) [0 ..]

‚em zusammen:

am = Summe $ filter sogar $ Takewhile (<4 * 10 ^ 6) fibs

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top