Fibonacci rápido en python

No es gran cosa, pero aquí teneis una versión de los números_de_Fibonaccique no se demora mucho para obtener números grandes, por ejemplo, para el número de Fibonacci 10000, tarda 0.1 segundos

(Eliminé los números que hay por el medio para que no quede una imágen excesivamente grande)

El código es simplemente: global fibo

fibo={} # El diccionario, este es el quid de la question

def fibonacci(i):

global fibo

if (i in fibo): # Si esta en el diccionario

   return fibo[i] # No hay que buscarlo

else:

   if (i < 2): # Si es trivial, no hay que memorizarlo

       return 1

   else: # Sino, se busca

       res = fibonacci(i - 1)+ fibonacci(i - 2)

       fibo[i] = res # Se mete en el diccionario

       return res # Y se devuelve

El truco está en el diccionario, que evita que haya que recorrer todos los números muchas veces, a costa, claro, de un gasto de memoria.

Hay una cosa a tener en cuenta, llamar directamente a la función (sin haber llamado a otra, que construyese el diccionario antes) con un número mayor o igual a 1000, producirá una excepción:

=============================================================================== RuntimeError: maximum recursion depth exceeded ===============================================================================

Para evitar eso, se puede construir el diccionario paso a paso (que se hace con apenas pérdida de rendimiento)

import sys

limit = 1000

if (len(sys.argv) > 1):

limit = int(sys.argv[1])

for i in xrange(1, limit):

fibonacci(i)

print fibonacci(limit) # Para demostrarlo :)

O completo

!/usr/bin/env python

global fibo

fibo={} # El diccionario, este es el quid de la question

def fibonacci(i):

global fibo

if (i in fibo): # Si esta en el diccionario

   return fibo[i] # No hay que buscarlo

else:

   if (i < 2): # Si es trivial, no hay que memorizarlo

       return 1

   else: # Sino, se busca

       res = fibonacci(i - 1)+ fibonacci(i - 2)

       fibo[i] = res # Se mete en el diccionario

       return res # Y se devuelve

import sys

limit = 1000

if (len(sys.argv) > 1):

limit = int(sys.argv[1])

for i in xrange(1, limit):

fibonacci(i)

print fibonacci(limit) # Para demostrarlo :)

Este método permite buscar incluso el número_100000sin jubilarse por el camino, en poco más de 2 segundos =P

Hasta otra.

untagged

Clon de LOIC en python » « De Firefox y URL's extrañas [Offtopic]