Dans le livre Python que je lisais, j'ai mentionné la séquence de Fibonacci, je vais donc la résumer avec un contenu léger comme un mémo tout en l'examinant.
Puisque je suis diplômé en design, sachez qu'il peut y avoir différents points si vous êtes diplômé d'une université en mathématiques ou en informatique.
Il s'agit d'une séquence nommée d'après le mathématicien italien Leonardo Fibonacci (séquence de Fibonacci en anglais).
C'est une séquence de valeurs telles que «0, 1, 1, 2, 3, 5, 8, 13, 21 ...».
Le premier (indice de 0) est 0, le suivant (indice de 1) est 1, et après cela, le précédent et 2 Écrit dans une expression, il ressemble à ce qui suit (en supposant que la valeur $ n $ th dans la colonne numérique est $ F_n $).
F_0 = 0\\
F_1 = 1\\
F_n = F_{n - 1} + F_{n - 2}
De plus, cette séquence de nombres est étroitement liée à la soi-disant direction du design, en particulier au nombre d'or (1: 1,618 ...), et elle apparaît dans les livres liés au design.
Même dans le monde naturel, il y a diverses choses telles que les graines de tournesol et les perroquets, qui sont proches des valeurs de ce nombre de rangées, et on dit que le ratio donne aux gens une sensation naturelle et belle.
De plus, si vous divisez un rectangle de nombre d'or en deux, un carré et un rectangulaire, le rectangle deviendra un rectangle qui maintient à nouveau le nombre d'or, et possède diverses autres propriétés intéressantes (les détails sont omis dans cet article). Si vous recherchez des articles et des livres liés aux mathématiques et au design, vous trouverez diverses choses, veuillez donc vérifier si nécessaire).
Tout d'abord, sans penser à rien, écrivons un processus pour obtenir la valeur de la position de l'index n de la séquence de Fibonacci en Python en appelant la fonction récursivement.
def fib(n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
Comme dans la formule ci-dessus, lorsque n est 0 et n est 1, 0 et 1 sont renvoyés, respectivement, et après cela, la somme des valeurs de la séquence de Fibonacci aux positions n -1 et n -2 est utilisée. Il y a.
Lançons-le et voyons le résultat.
if __name__ == '__main__':
for n in range(7):
print(f'n = {n}dans le cas de:', fib(n=n))
n =Si 0: 0
n =En cas de 1: 1
n =En cas de 2: 1
n =En cas de 3: 2
n =En cas de 4: 3
n =En cas de 5: 5
n =En cas de 6: 8
Vous pouvez voir que la valeur attendue est prise.
À ce rythme, si n devient grand, le calcul prendra beaucoup de temps.
Par exemple, pour calculer la valeur de n = 5, vous devez calculer les valeurs de n = 4 et n = 3, et pour calculer n = 4, trouver les valeurs de n = 3 et n = 2. Chaque fois que n augmente de un, les conditions qui doivent être calculées augmentent de façon exponentielle comme un diagramme de famille.
Voyons combien de fois la fonction préparée a été exécutée. J'ai préparé une variable appelée count en tant que variable globale.
from datetime import datetime
count: int = 0
def fib(n: int) -> int:
global count
count += 1
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
Si vous essayez de l'exécuter avec n = 34 et n = 35, vous pouvez voir que le nombre d'exécutions de fonctions a augmenté de manière significative simplement en augmentant n de 1.
n=Exécuter l'échantillon sur 34
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=34)
print('Nombre d'exécutions de la fonction:', count)
print(datetime.now(), 'ended')
2020-08-30 15:45:15.097393 started
Nombre d'exécutions de la fonction: 18454929
2020-08-30 15:45:17.980419 ended
n=Exécuter l'échantillon à 35
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=35)
print('Nombre d'exécutions de la fonction:', count)
print(datetime.now(), 'ended')
2020-08-30 15:49:25.628928 started
Nombre d'exécutions de la fonction: 29860703
2020-08-30 15:49:30.307930 ended
Comme mentionné ci-dessus, il existe différentes méthodes pour accélérer le calcul lorsque n devient grand, et l'une d'entre elles consiste à mettre en cache le résultat de l'exécution de la fonction.
Par exemple, si la valeur de n est la même, la valeur de retour sera la même, et lors du calcul de la valeur de grand n, la valeur la plus petite peut être calculée encore et encore, donc un n spécifique est déjà spécifié. Si le cas de la valeur de est déjà agrégé, il peut être mis en cache et le calcul peut être ignoré, de sorte que le traitement puisse être terminé en peu de temps même si n augmente.
Vous pouvez le mettre en cache à l'aide d'un dictionnaire, mais en Python, vous pouvez utiliser le module intégré functools et spécifier le décorateur pour lru_cache.
C'est facile à utiliser, il suffit de définir la fonction lru_cache comme décorateur sur la fonction que vous souhaitez mettre en cache. lru est une abréviation de moins récemment utilisé, et c'est une méthode de mise en cache sous la forme de laisser un nouveau résultat d'exécution (dans ce cas, en laissant le résultat du calcul de n mis en cache vers la fin).
Cette fois, puisque l'ancien cache n'est pas supprimé mais que tous sont mis en cache, None est spécifié pour l'argument maxsize.
from datetime import datetime
from functools import lru_cache
count: int = 0
@lru_cache(maxsize=None)
def fib(n: int) -> int:
global count
count += 1
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
Lorsque vous l'exécutez, vous pouvez voir que le processus est terminé en un instant et que le nombre de fois qu'il est passé à l'intérieur de la fonction a diminué à la fois.
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=35)
print('Nombre d'exécutions de la fonction:', count)
print(datetime.now(), 'ended')
2020-08-30 16:39:49.109241 started
Nombre d'exécutions de la fonction: 36
2020-08-30 16:39:49.110240 ended
Recommended Posts