Python - Modifier le dictionnaire de la fonction

Question

D'accord, cette question est un peu étrange, mais je me demandais si je pouvais le faire comme ça.

Je travaille sur un simple générateur de nombres Fibonacci pour m'amuser puisque j'étais intéressé à le programmer. J'ai donc écrit ceci:

def f(n): 
    if n == 1: return 1 
    if n == 2: return 2 
    else: 
     return f(n-1) + f(n-2) 

et couru très lentement, en prenant 15 secondes pour faire f(30) sur mon ordinateur. Alors j'ai écrit ceci:

def f(n): 
    global a 
    if n == 1: return 1 
    if n == 2: return 1 
    else: 
     if "fib(%s)" % n in a: 
      return a["fib(%s)" % n] 
     else: 
      z = f(n-1) + f(n-2) 
      a["fib(%s)" % n] = z 
      return z 

qui stocke essentiellement des résultats précédents dans un dictionnaire comme ceci:

{'f(1)':1,'f(2)':2,'f(3)':3,'f(4)':5} et ainsi de suite. Dans la fonction, il vérifierait si ce résultat était dans ce dictionnaire, alors utilisez simplement cela au lieu d'avoir à refaire tous les calculs.

Cela l'a fait beaucoup plus rapide. Je pourrais faire f(100) et il apparaît instantanément. En passant par intervalles de 500, je suis arrivé à f(4000) et c'était encore instantané. Le seul problème était que le dictionnaire devenait stupidement grand.

J'ai donc ajouté a = {} à la fin de la fonction, et cela n'a pas fonctionné; il a encore laissé a comme dict massive.

fait donc ceci:

def f(n): 
    global a 
    if n == 1: return 1 
    if n == 2: return 1 
    else: 
     if "fib(%s)" % n in a: 
      return a["fib(%s)" % n] 
     else: 
      z = f(n-1) + f(n-2) 
      a["fib(%s)" % n] = z 
      return z 
    a = {} 

ne fonctionne pas. mais si je fais ceci:

def f(n): 
    global a 
    if n == 1: return 1 
    if n == 2: return 1 
    else: 
     if "fib(%s)" % n in a: 
      return a["fib(%s)" % n] 
     else: 
      z = f(n-1) + f(n-2) 
      a["fib(%s)" % n] = z 
      return z 
# now run the function 
f(100) 
a = {} 

a obtient remis à un dictionnaire vide. Pourquoi cela arrive-t-il et comment puis-je le réparer?

Answer 1

Votre instruction a = {} à l'intérieur de la fonction n'a jamais été exécutée; chaque chemin d'exécution possible atteint un return auparavant. Si elle était exécutée, vous n'auriez pas aimé les résultats - elle aurait été exécutée dans chaque appel récursif à la fonction, ce qui signifie que votre dictionnaire ne contiendrait jamais plus d'un élément! Vous devriez d'une manière ou d'une autre détecter l'appel le plus externe et seulement effacer le dict, ou (beaucoup plus simple) l'effacer en dehors de la récursion comme dans votre deuxième exemple.

Notez qu'une grande partie de la taille de votre dictionnaire provient de la décision étrange d'utiliser une longue clé de chaîne. L'indexer avec le numéro lui-même (comme dans a[n] = z) le rendrait beaucoup plus compact.

(Pour référence ultérieure:. La technique que vous êtes venu ici, d'enregistrer les résultats des appels de fonctions antérieures, est connu sous le nom « memoization »)

Answer 2

En dépit de votre question, ce que vous voulez vraiment est moyen plus rapide de calculer la séquence de Fibonacci, non? Le problème avec votre approche originale est que la récurrence, bien qu'étant très élégante et rapide à coder, est assez lente. La séquence de Fibonacci a une solution proche de la forme. Vous devriez faire ce calcul directement pour accélérer votre code. Comme convention, considérons la séquence de Fibonacci F (i) comme: F (0) = 0, F (1) = 1, F (k) = F (k-1) + F (k-2) k = 2, 3, ... La solution pour cette suite est (je ne vais pas le démontrer ici, parce que ce n'est pas l'endroit pour ça) F (k) = (1/sqrt (5)) * (a^k - b^k) , où a = (1 + sqrt (5))/2 et b = (1 - sqrt (5))/2. Ainsi, votre code pourrait être mis en œuvre comme ceci:

def f(n): 

    a = (1 + 5**.5)/2 
    b = (1 - 5**.5)/2 
    F = (a**n - b**n)/5**.5 
    F = int(round(F)) #necessary to get an integer without the decimal part of the approximation. Afterall, you are working with irrational numbers. 
    return F 

Cette échelle de code très bien pour les grandes valeurs de n.