Nombres de Fibonacci, avec un one-liner en Python 3?

Un truc rarement vu est qu'une fonction lambda peut se référer à elle-même récursivement:

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

En passant, c'est rarement vu parce que c'est confus, et dans ce cas c'est aussi inefficace. Il est préférable de l'écrire sur plusieurs lignes:

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

J'ai récemment appris à utiliser la multiplication matricielle pour générer des nombres de Fibonacci, ce qui était plutôt cool. Vous prenez une matrice de base:

[1, 1]
[1, 0]

Et multipliez-le par lui-même N fois pour obtenir:

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

Ce matin, en griffonnant dans la vapeur sur le mur de la douche, j'ai réalisé que vous pouviez réduire le temps de fonctionnement en deux en commençant par la deuxième matrice, et en la multipliant par elle-même n / 2 fois, puis en utilisant N pour choisir un index de la première rangée / colonne.

Avec un peu de compression, Je Je l'ai ramené à une ligne:

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 nous considérons la "manière la plus pythonique" comme élégante et efficace alors:

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

Gagne haut la main. Pourquoi utiliser un algorithme inefficace (et si vous commencez à utiliser la mémorisation, nous pouvons oublier le oneliner) lorsque vous pouvez résoudre le problème très bien dans O (1) en approximant le résultat avec le nombre d'or? Bien qu'en réalité je l'écrirais évidemment sous cette forme:

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

Plus efficace et beaucoup plus facile à comprendre.

Il s'agit d'une mémorisation non récursive (anonyme) d'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)

Temps d'Exécution O(n), fib(0) = 0, fib(1) = 1, fib(2) = 1 ...

Un autre exemple, en prenant le signal de la réponse de Mark Byers:

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

Ceci est une expression fermée pour la série de Fibonacci qui utilise l'arithmétique entière, et est assez efficace.

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

>> fib(1000)
4346655768693745643568852767504062580256466051737178
0402481729089536555417949051890403879840079255169295
9225930803226347752096896232398733224711616429964409
06533187938298969649928516003704476137795166849228875L

Il calcule le résultat en opérations arithmétiques O(log n), chacune agissant sur des entiers avec des bits O(N). Étant donné que le résultat(le nième nombre de Fibonacci) est O (N) bits, la méthode est tout à fait raisonnable.

Il est basé sur genefib4 de http://fare.tunes.org/files/fun/fibonacci.lisp , qui à son tour était basé sur une expression entière de forme fermée moins efficace de moi (voir: http://paulhankin.github.io/Fibonacci/)

Voici une implémentation qui n'utilise pas la récursivité, et ne mémorise que les deux dernières valeurs au lieu de l'historique complet de la séquence.

Nthfib() ci-dessous est la solution directe au problème d'origine (tant que les importations sont autorisées)

C'est moins élégant que d'utiliser les méthodes de réduction ci-dessus, mais, bien que légèrement différent de ce qui a été demandé, il gagne la capacité d'être utilisé plus efficacement comme un générateur infini si l'on a besoin de sortir la séquence jusqu'à la nième nombre ainsi (réécrire légèrement comme fibgen() ci-dessous).

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]

Pour résoudre ce problème, je me suis inspiré d'une question similaire ici dans Stackoverflow single Statement Fibonacci , et j'ai eu cette fonction de ligne unique qui peut produire une liste de séquence de fibonacci. Cependant, c'est un script Python 2, non testé sur 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)

Affectez cette fonction lambda à une variable pour la réutiliser:

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 sortie est une liste de séquence 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]

Prenez le signal de Jason S, je pense que ma version a une meilleure compréhension.

Je ne sais pas si c'est la méthode la plus pythonique mais c'est le meilleur que je puisse trouver: - >

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]

Le code ci-dessus n'utilise pas la récursivité, juste une liste pour stocker les valeurs.

Mes 2 cents

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

Ou

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

Pourquoi ne pas utiliser une compréhension de liste?

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

Sans importations mathématiques, mais moins jolie:

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

Je suis un nouveau venu Python, mais j'ai fait une certaine mesure à des fins d'apprentissage. J'ai recueilli un algorithme fibo et pris une certaine mesure.

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

Le résultat est généralement Le même.

Fiboslow_2 avec récursion et cache, l'arithmétique des entiers Fib et les algorithmes Fibfast semblent les meilleurs. Peut-être mon décorateur pas la meilleure chose à mesurer la performance, mais pour un aperçu, il semblait bon.

Similaire:

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

Un simple générateur de nombres de Fibonacci utilisant la récursivité

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

Cela prend une éternité pour calculer fib(100) dans mon ordinateur.

Il y a aussi forme fermée des nombres de Fibonacci.

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

Cela fonctionne presque jusqu'à 72 numéros en raison d'un problème de précision.

Lambda avec des opérateurs logiques

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

Voici comment je le fais, mais la fonction renvoie None pour la partie Ligne de compréhension de liste pour me permettre d'insérer une boucle à l'intérieur .. donc, fondamentalement, ce qu'il fait est d'ajouter de nouveaux éléments de la FIB seq à l'intérieur d'une liste qui est sur deux éléments

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