Project Euler in Python. Problema #2


Problema 2

"""
Trovare la somma di tutti i termini pari nella sequenza di Fibonacci
minori di quattro milioni.
"""
import time

def fibonacci(n):
    """ trivial fibonacci implementation """
    if n in (0, 1): return n
    return fibonacci(n - 1) + fibonacci(n - 2)

def solve():
    i=res=sum=0
    while res < 4000000:
        res = fibonacci(i)
        if (res%2) == 0: sum = sum + res
        i=i+1

    return sum

if __name__ == '__main__':
    t1 = time.time()
    s = solve()
    t2 = time.time()
    print s,(t2-t1)*1000

Il codice è corretto ma il programma impiega quasi 24 secondi sul mio MacMini Intel… decisamente troppo! Il problema sta nel fatto che la funzione fibonacci() ogni volta ricalcola dei valori che però avrebbe già a disposizione grazie alle iterazioni precedenti. Ho risolto il problema con una tecnica detta Memoization implementata tramite un decoratore:

"""
Trovare la somma di tutti i termini pari nella sequenza di Fibonacci
minori di quattro milioni.
"""
import time

class memoize:
    """ a class implementing memoization, to be used as a decorator
    """
    def __init__(self, function):
        self.function = function
        self.memoized = {}

    def __call__(self, *args):
        try:
            return self.memoized[args]
        except KeyError:
            self.memoized[args] = self.function(*args)
            return self.memoized[args]

@memoize
def fibonacci(n):
    """ trivial fibonacci implementation """
    if n in (0, 1): return n
    return fibonacci(n - 1) + fibonacci(n - 2)

def solve():
    i=res=sum=0
    while res < 4000000:
        res = fibonacci(i)
        if (res%2) == 0: sum = sum + res
        i=i+1

    return sum

if __name__ == '__main__':
    t1 = time.time()
    s = solve()
    t2 = time.time()
    print s,(t2-t1)*1000

Con questa tecnica il tempo di calcolo scende a 0.43s!

http://en.wikipedia.org/wiki/Memoization

3 thoughts on “Project Euler in Python. Problema #2

  1. Carino, ma ti costringe ad avere un dizionario di di elementi, di cui
    se ne usano sempre solo gli ultimi due. Inoltre ogni chiamata a fibonacci
    genera una eccezzione KeyError, che è relativamente pesante da gestire …

    Io riscriverei fibonacci come un generatore progressivo, qualcosa del tipo (non completamente testato):

    >>> def genera_fibonacci():
    yield 0
    yield 1
    last_two = (0,1)
    while 1:
    res = sum(last_two)
    yield res
    last_two = (last_two[1], res )

    che tra l’altro è appena più complicato della versione ricorsiva ma molto più
    veloce …

    Ciao
    ——
    FB

  2. Effettivamente con un generatore tipo questo:

    def fibonacci(limit):
    n1, n2 = 0, 1
    while (1):
    f = n1+n2
    n1, n2 = n2, f
    if f >= limit: raise StopIteration
    yield f

    il guadagno in termini di tempo è di un ordine di grandezza (~0.03s contro ~0.3s sul mio MacBook Pro Intel).
    Grazie della segnalazione, e grazie a qzerty per lo snippet!

  3. Ahhh.. grazie, ma non c’era bisogno di citarmi.. anche perche` questa versione non sara` gran che piu` veloce (probabilmente non lo e`), ma dovrebbe essere piu` corretta e un po’ piu` curata:

    def fibonacci(limit):
    n, f = 0, 1
    while (f <= limit):
    yield f
    n, f = f, f+n

    Oggi non ci ho neppure fatto caso, ma mi ero pure perso una coppia di conigli (ma 1 non e` pari e il conto tornava lo stesso).. e non c’era alcun bisogno di sollevare esplicitamente una StopIteration dato che viene implicitamente sollevata nel momento in cui si esce dal corpo della funzione generatrice (eventualmente con un “return”).

    Le mie scuse ai tuoi 25 lettori..

Comments are closed.