[PYTHON] Mémo appris

Préface

Récemment, j'ai eu plusieurs opportunités de recevoir une sélection de stagiaires et une sélection finale d'entreprises Web. Il y a eu un test de codage dans la sélection de nombreuses entreprises, et comme j'ai étudié un peu cette fois, je vais le laisser comme mémorandum comme pratique de sortie.

Cette fois à propos de la ** mémorisation **.

Qu'est-ce que le mémo

En termes simples, c'est une technique pour accélérer votre programme.

C'est une technique comme "Lorsque la même fonction est appelée plusieurs fois dans un traitement récursif, etc., le résultat du calcul est enregistré dans le cache (mémo), et la valeur mise en cache est renvoyée pour celle précédemment calculée".

Exemple d'implémentation

Cette fois, à titre d'exemple d'implémentation, je présenterai un programme qui demande ** quel est le nième nombre dans la séquence de Fibonacci.

Séquence de Fibonacci

a_1=a_2=1 \\
a_n=a_{n−1}+a_{n−2}\\
(1\leqq n)

La séquence numérique de Fibonacci peut être exprimée sous la forme d'une formule progressive comme indiqué ci-dessus. Je n'entrerai pas dans les détails, mais les deux premiers termes renvoient 1, et le reste des termes renvoie la somme des deux termes précédents.

Implémenté avec juste récursif

def fibonacci(n):
    if n == 1 or n == 2:
        return 1

    return fibonacci(n - 2) + fibonacci(n - 1)

print(fibonacci(6))  # 8

Mis en œuvre sous forme de mémo

memo = {1: 1, 2: 1}

def fibonacci(n):
 Si n est enregistré dans # memo, sa valeur est renvoyée.
    if n in memo:
        return memo[n]

 # Sinon, enregistrez-le dans un mémo et renvoyez la valeur
    memo[n] = fibonacci(n - 2) + fibonacci(n - 1)
    return memo[n]

print(fibonacci(6))  # 8

image

Lorsqu'il est implémenté par simple récursif, n = 6 est appelé fibonacci (4) deux fois et fibonacci (3) trois fois. Vous pouvez imaginer qu'à mesure que n devient de plus en plus grand, le nombre de calculs augmentera. Si vous créez un mémo, vous n'avez pas à calculer celui calculé une fois à partir de la deuxième fois, vous pouvez donc réduire considérablement le nombre de calculs.

Sommaire

--Memo est l'une des techniques pour accélérer le programme.

• Plus n est grand, plus efficace