sceneggiatura Haskell a corto di spazio

Question

sto usando Project Euler a insegnare a me stesso Haskell, e sto avendo qualche problema ragionare su come il mio codice viene eseguito da Haskell. Il secondo problema mi ha calcolare la somma di tutti i numeri di Fibonacci fino a 4 milioni di euro. Il mio script è simile al seguente:

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

Abbracci dà l'errore di "garbage collection non riesce a recuperare lo spazio sufficiente", che presumo significa che le voci di elenco non vengono rilasciati in quanto sono consumati da foldr.

Che cosa devo fare per risolvere questo problema? Ho provato a scrivere una versione ricorsiva in coda (credo) che ha utilizzato gli accumulatori, ma non sono riuscito a convincere quello per funzionare sia.

Answer 1

Una serie di osservazioni / suggerimenti:

• i x + sums da addirittura non sono sempre valutati fino alla fine
• Stai prendendo i primi 4.000.000 FIBS, non le frottole fino a 4.000.000
• C'è un modo più semplice per fare questo

Modifica in risposta al commento

Non ho intenzione di dirvi ciò che il modo più semplice è, dato che è il divertimento di problemi Project Euler. Ma io vi chiedo un sacco di domande:

• Quante frottole anche si può avere in una fila?
• Per quanto tempo si può andare senza nemmeno un FIB?
• Se si somma anche tutte le frottole e tutte le frottole dispari (farlo a mano), cosa che si nota circa le somme?

Answer 2

In primo luogo, non si dovrebbe usare abbracci. Si tratta di un giocattolo solo a scopo didattico.

GHC, tuttavia, è un veloce, multicore-ready compilatore ottimizzato per Haskell. garantita qui . In particolare, lo fa l'analisi rigore, e compilato in codice nativo.

La cosa principale che risalta sul codice è l'uso di foldr su un elenco molto grande. Probabilmente si desidera una coda ciclo ricorsivo. In questo modo:

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

Oltre a tutto questo, il primo 4M anche frottole utilizzerà una discreta quantità di spazio, quindi ci vorrà un po '.

Ecco la somma del primo 400k anche frottole , per salvare un certo tempo (21s). : -)

Answer 3

Hai capito il problema sbagliato. Il problema reale vi vuole sommare tutti i numeri pari di Fibonacci in modo tale che il Fibonacci numero stesso non supera 4 milioni (che risulta essere solo i primi 33 numeri di Fibonacci).

Answer 4

Si sta valutando quattro milioni di elementi di fibs. Questi numeri crescono in modo esponenziale. Non so quanti byte sono necessari per rappresentare il numero milionesimo di Fibonacci; solo il numero di Fibonacci un millesimo dispone di 211 cifre decimali, in modo che sta andando a prendere 22 parole a 32 bit solo per contenere le cifre, non importa ciò che gmp testa impone. E questi crescono in modo esponenziale.

Esercizio:. Calculuate la quantità di memoria necessaria per contenere quattro milioni di numeri di Fibonacci

Answer 5

avere uno sguardo alla funzioni Prelude TakeWhile, filtro, anche, e somma

TakeWhile (<40) [0 ..]
filtrare anche $ TakeWhile (<40) [0 ..]

put 'em insieme:

ans = somma $ filtro anche $ TakeWhile (<4 * 10 ^ 6) frottole