¿Números de Fibonacci, con una sola línea en Python 3?

Un truco raramente visto es que una función lambda puede referirse a sí misma recursivamente:

fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)

Por cierto, rara vez se ve porque es confuso, y en este caso también es ineficiente. Es mucho mejor escribirlo en varias líneas:

def fibs():
    a = 0
    b = 1
    while True:
        yield a
        a, b = b, a + b

Recientemente aprendí sobre el uso de la multiplicación de matrices para generar números de Fibonacci, lo cual fue bastante genial. Se toma una matriz base:

[1, 1]
[1, 0]

Y multiplíquelo por sí mismo N veces para obtener:

[F(N+1), F(N)]
[F(N), F(N-1)]

Esta mañana, garabateando en el vapor en la pared de la ducha, me di cuenta de que se podía reducir el tiempo de funcionamiento a la mitad comenzando con la segunda matriz y multiplicándola por sí misma N/2 veces, luego usando N para elegir un índice de la primera fila/columna.

Con un poco de apretamiento, yo lo bajé a una línea:

import numpy

def mm_fib(n):
    return (numpy.matrix([[2,1],[1,1]])**(n//2))[0,(n+1)%2]

>>> [mm_fib(i) for i in range(20)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Si consideramos que la" forma más pitónica " es elegante y efectiva, entonces:

def fib(nr):
    return int(((1 + math.sqrt(5)) / 2) ** nr / math.sqrt(5) + 0.5)

Gana sin duda. ¿Por qué usar un algoritmo ineficiente (y si comienzas a usar la memoización podemos olvidarnos del oneliner) cuando puedes resolver el problema muy bien en O(1) aproximando el resultado con la proporción áurea? Aunque en realidad obviamente lo escribiría de esta forma:

def fib(nr):
    ratio = (1 + math.sqrt(5)) / 2
    return int(ratio ** nr / math.sqrt(5) + 0.5)

Más eficiente y mucho más fácil de entender.

Este es un no recursivo (anónimo) memorizando un liner

fib = lambda x,y=[1,1]:([(y.append(y[-1]+y[-2]),y[-1])[1] for i in range(1+x-len(y))],y[x])[1]

fib = lambda n, x=0, y=1 : x if not n else fib(n-1, y, x+y)

Tiempo de Ejecución O(n), fib(0) = 0, fib(1) = 1 fib(2) = 1 ...

Otro ejemplo, siguiendo el ejemplo de la respuesta de Mark Byers:

fib = lambda n,a=0,b=1: a if n<=0 else fib(n-1,b,a+b)

Esta es una expresión cerrada para la serie de Fibonacci que usa aritmética de enteros, y es bastante eficiente.

fib = lambda n:pow(2<<n,n+1,(4<<2*n)-(2<<n)-1)%(2<<n)

>> fib(1000)
4346655768693745643568852767504062580256466051737178
0402481729089536555417949051890403879840079255169295
9225930803226347752096896232398733224711616429964409
06533187938298969649928516003704476137795166849228875L

Calcula el resultado en operaciones aritméticas O(log n), cada una actuando sobre enteros con O(n) bits. Dado que el resultado (el enésimo número de Fibonacci) es O(n) bits, el método es bastante razonable.

Se basa en genefib4 de http://fare.tunes.org/files/fun/fibonacci.lisp , que a su vez se basó en una expresión entera de forma cerrada menos eficiente de la mía (ver: http://paulhankin.github.io/Fibonacci/)

Aquí hay una implementación que no usa recursión, y solo memoriza los dos últimos valores en lugar de todo el historial de secuencias.

Nthfib () a continuación se muestra la solución directa al problema original (siempre que se permitan las importaciones)

Es menos elegante que usar los métodos de reducción anteriores, pero, aunque ligeramente diferente de lo que se pidió, gana la capacidad de ser utilizado de manera más eficiente como un generador infinito si uno necesita generar la secuencia hasta el enésimo número también (reescribiendo ligeramente como fibgen () a continuación).

from itertools import imap, islice, repeat

nthfib = lambda n: next(islice((lambda x=[0, 1]: imap((lambda x: (lambda setx=x.__setitem__, x0_temp=x[0]: (x[1], setx(0, x[1]), setx(1, x0_temp+x[1]))[0])()), repeat(x)))(), n-1, None))    

>>> nthfib(1000)
43466557686937456435688527675040625802564660517371780402481729089536555417949051
89040387984007925516929592259308032263477520968962323987332247116164299644090653
3187938298969649928516003704476137795166849228875L

from itertools import imap, islice, repeat

fibgen = lambda:(lambda x=[0,1]: imap((lambda x: (lambda setx=x.__setitem__, x0_temp=x[0]: (x[1], setx(0, x[1]), setx(1, x0_temp+x[1]))[0])()), repeat(x)))()

>>> list(islice(fibgen(),12))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]

Para resolver este problema me inspiré en una pregunta similar aquí en Stackoverflow Single Statement Fibonacci, y obtuve esta función de línea única que puede generar una lista de secuencias de fibonacci. Sin embargo, este es un script de Python 2, no probado en Python 3:

(lambda n, fib=[0,1]: fib[:n]+[fib.append(fib[-1] + fib[-2]) or fib[-1] for i in range(n-len(fib))])(10)

Asigne esta función lambda a una variable para reutilizarla:

fib = (lambda n, fib=[0,1]: fib[:n]+[fib.append(fib[-1] + fib[-2]) or fib[-1] for i in range(n-len(fib))])
fib(10)

La salida es una lista de la secuencia de fibonacci:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

def fib(n):
    x =[0,1]
    for i in range(n):
        x=[x[1],x[0]+x[1]]
    return x[0]

Sigue el ejemplo de Jason S, creo que mi versión tiene una mejor comprensión.

No se si este es el método más pitónico pero este es el mejor que se me ocurrió:- >

Fibonacci = lambda x,y=[1,1]:[1]*x if (x<2) else ([y.append(y[q-1] + y[q-2]) for q in range(2,x)],y)[1]

El código anterior no usa recursión, solo una lista para almacenar los valores.

Mis 2 centavos

# One Liner
def nthfibonacci(n):
    return long(((((1+5**.5)/2)**n)-(((1-5**.5)/2)**n))/5**.5)

O

# Steps
def nthfibonacci(nth):
    sq5 = 5**.5
    phi1 = (1+sq5)/2
    phi2 = -1 * (phi1 -1)
    n1 = phi1**(nth+1)
    n2 = phi2**(nth+1)
    return long((n1 - n2)/sq5)

¿Por qué no usar una comprensión de lista?

from math import sqrt, floor
[floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))) for n in range(100)]

Sin importaciones matemáticas, pero menos bonitas:

[int(((1+(5**0.5))**n-(1-(5**0.5))**n)/(2**n*(5**0.5))) for n in range(100)]

Soy un recién llegado de Python, pero hice alguna medida con fines de aprendizaje. He recopilado algunos algoritmos de fibo y tomado alguna medida.

from datetime import datetime
import matplotlib.pyplot as plt
from functools import wraps
from functools import reduce
from functools import lru_cache
import numpy


def time_it(f):

    @wraps(f)
    def wrapper(*args, **kwargs):
        start_time = datetime.now()

        f(*args, **kwargs)

        end_time = datetime.now()
        elapsed = end_time - start_time
        elapsed = elapsed.microseconds

        return elapsed
    return wrapper


@time_it
def fibslow(n):
    if n <= 1:
        return n

    else:
        return fibslow(n-1) + fibslow(n-2)


@time_it
@lru_cache(maxsize=10)
def fibslow_2(n):
    if n <= 1:
        return n

    else:
        return fibslow_2(n-1) + fibslow_2(n-2)


@time_it
def fibfast(n):
    if n <= 1:
        return n

    a, b = 0, 1

    for i in range(1, n+1):
        a, b = b, a + b

    return a


@time_it
def fib_reduce(n):
    return reduce(lambda x, n: [x[1], x[0]+x[1]], range(n), [0, 1])[0]


@time_it
def mm_fib(n):
    return (numpy.matrix([[2, 1], [1, 1]])**(n//2))[0, (n+1) % 2]


@time_it
def fib_ia(n):
    return pow(2 << n, n+1, (4 << 2 * n) - (2 << n)-1) % (2 << n)


if __name__ == '__main__':

    X = range(1, 200)
#    fibslow_times = [fibslow(i) for i in X]
    fibslow_2_times = [fibslow_2(i) for i in X]
    fibfast_times = [fibfast(i) for i in X]
    fib_reduce_times = [fib_reduce(i) for i in X]
    fib_mm_times = [mm_fib(i) for i in X]
    fib_ia_times = [fib_ia(i) for i in X]

#    print(fibslow_times)
#    print(fibfast_times)
#    print(fib_reduce_times)

    plt.figure()
#    plt.plot(X, fibslow_times, label='Slow Fib')
    plt.plot(X, fibslow_2_times, label='Slow Fib w cache')
    plt.plot(X, fibfast_times, label='Fast Fib')
    plt.plot(X, fib_reduce_times, label='Reduce Fib')
    plt.plot(X, fib_mm_times, label='Numpy Fib')
    plt.plot(X, fib_ia_times, label='Fib ia')
    plt.xlabel('n')
    plt.ylabel('time (microseconds)')
    plt.legend()
    plt.show()

El resultado suele ser el mismo.

Fiboslow_2 con recursión y caché, la aritmética de enteros Fib y los algoritmos de Fibfast parecen los mejores. Tal vez mi decorador no es lo mejor para medir el rendimiento, pero para una visión general parecía bueno.

Similar:

    def fibonacci(n):
      f=[1]+[0]
      for i in range(n):
        f=[sum(f)] + f[:-1]
      print f[1]

Un generador de números Fibonacci simple usando recursión

fib = lambda x: 1-x if x < 2 else  fib(x-1)+fib(x-2)
print fib(100)

Esto toma una eternidad calcular fib(100) en mi computadora.

También hay forma cerrada de los números de Fibonacci.

fib = lambda n: int(1/sqrt(5)*((1+sqrt(5))**n-(1-sqrt(5))**n)/2**n)
print fib(50)

Esto funciona casi hasta 72 números debido a un problema de precisión.

Lambda con operadores lógicos

fibonacci_oneline = lambda n = 10, out = []: [ out.append(i) or i if i <= 1 else out.append(out[-1] + out[-2]) or out[-1] for i in range(n)]

Así es como lo hago ,sin embargo la función devuelve None para la parte de la línea de comprensión de lista para permitirme insertar un bucle dentro .. así que básicamente lo que hace es agregar nuevos elementos de la fib seq dentro de una lista que está sobre dos elementos

>>f=lambda list,x :print('The list must be of 2 or more') if len(list)<2 else [list.append(list[-1]+list[-2]) for i in range(x)]
>>a=[1,2]
>>f(a,7)