Ici, j'ai du code pour renvoyer le dernier chiffre d'un numéro de Fibonacci. Lorsque je place le dictionnaire de cache à l'intérieur de la fonction, le programme fonctionne bien pour la petite n. Quand j'essaye plus grand n comme 300, le programme prend pour toujours. Lorsque je fais le dictionnaire global, cependant, je reçois un résultat instantané pour un plus grand N comme 300. Qu'est-ce qui cause une différence de performance aussi forte entre le dictionnaire étant déclaré dans la fonction vs en dehors de la fonction?
def fib_last_digit_mem(n):
cache = {}
if n in cache:
return cache[n]
if(n <= 1):
return n
fib = (fib_last_digit_mem(n-1) + fib_last_digit_mem(n-2))%10
cache[n] = fib
return fib
3 Réponses :
Comme il s'agit d'une fonction récursive si vous instanciez le cache dans la fonction, il sera instancié à nouveau chaque fois que la fonction recute. Cela signifie également que le cache est toujours vide, vous ne prenez jamais la route courte si n dans le cache
Vous ne mettez pas en train de mettre en train de mettre en train de mettre en train de mettre en train de mettre en train de mettre en train de mettre en train de mettre en train de mettre en cache quelque chose, car le var Vous avez besoin de faire référence à considérer: Ici, le cache n'est pas global; Il est dans la portée où cache est initialisé à un dict vide chaque fois que vous appelez la fonction. Bien sûr, une fois que vous calculez la valeur, vous l'ajoutez à la dicte. Mais alors vous revenez: cache est hors de portée, et le dict est collecté à la poubelle. cache que existe extérieur fib_last_digit_mem , mais cela n'a pas nécessairement besoin d'être une variable globale. fib_last_digit_mem est défini. Une fois make_cached_fib renvoie, la seule référence au cache est celle détenue par fib_last_digit_mem lui-même.
Vous instaniez le cache dans la fonction appelée récursivement. Cela conduit à deux problèmes:
1) Chaque fois que vous effectuez un appel récursif, vous devez instancier un cache qui coûte un peu de performances, mais que le processus de création n'est pas la raison pour laquelle votre code est lent.
2) La vraie raison et encore plus grand problème est que vous ne faites rien avec votre cache. La programmation dynamique vous permet de réutiliser les résultats précédemment calculés, vous n'avez donc pas à les calculer à nouveau. Vous enregistrez ces résultats dans le cache. Mais parce que vous avez l'intiquetant du cache chaque fois que vous appelez la méthode Tous vos appels récursif finissent par avoir un cache local vide vide au lieu de partager un cache global qui vous aide à éviter de calculer à nouveau des résultats calculés à nouveau.
Exemple:
Si vous déclarez le cache globalement et calculez fibonacci (10) la dernière opération Il suffit d'obtenir le résultat de fibonacci (9) hors du cache et ajoutez un autre numéro à celui-ci. Son seul ajout à calculer le prochain N-ème numéro de Fibonacci. Dans votre cas, au lieu de simplement obtenir le résultat de fibonacci (9) et en ajoutant un numéro, vous calculez en réalité fibonacci (9) à nouveau, ce qui signifie que vous devez Calculte fibonacci (8) etc ... qui provoque la mauvaise performance sans programmation dynamique (cache globale)