Qu'est-ce que la mémorisation et comment puis-je l'utiliser en Python ?

Question

Je viens de commencer Python et je n'ai aucune idée de ce que mémorisation est et comment l'utiliser. En outre, puis-je avoir un exemple simplifié ?

Answer 1

La mémorisation fait effectivement référence au fait de se souvenir ("memoization" → "memorandum" → se souvenir) des résultats des appels de méthode en fonction des entrées de la méthode, puis de renvoyer le résultat mémorisé plutôt que de calculer à nouveau le résultat. Vous pouvez l'imaginer comme un cache pour les résultats des méthodes. Pour plus de détails, reportez-vous à la page 387 pour la définition en Introduction aux algorithmes (3e), Cormen et al.

Un exemple simple pour calculer des factorielles en utilisant la mémorisation en Python serait quelque chose comme ceci :

factorial_memo = {}
def factorial(k):
    if k < 2: return 1
    if k not in factorial_memo:
        factorial_memo[k] = k * factorial(k-1)
    return factorial_memo[k]

Vous pouvez être plus compliqué et encapsuler le processus de mémorisation dans une classe :

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        #Warning: You may wish to do a deepcopy here if returning objects
        return self.memo[args]

Entonces:

def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

factorial = Memoize(factorial)

Une fonction connue sous le nom de " décorateurs " a été ajouté dans Python 2.4, ce qui vous permet maintenant d'écrire simplement ce qui suit pour accomplir la même chose :

@Memoize
def factorial(k):
    if k < 2: return 1
    return k * factorial(k - 1)

En Bibliothèque de décorateurs Python possède un décorateur similaire appelé memoized qui est légèrement plus robuste que le Memoize montré ici.

Answer 2

functools.cache décorateur :

Python 3.9 a publié une nouvelle fonction functools.cache . Il met en cache en mémoire le résultat d'une fonction appelée avec un ensemble particulier d'arguments, ce qui est de la mémoïsation. C'est facile à utiliser :

import functools

@functools.cache
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Cette fonction sans le décorateur est très lente, essayez donc fib(36) et vous devrez attendre une dizaine de secondes.

Ajout de la cache garantit que si la fonction a été appelée récemment pour une valeur particulière, elle ne recalculera pas cette valeur, mais utilisera un résultat précédent mis en cache. Dans ce cas, cela conduit à une amélioration considérable de la vitesse, alors que le code n'est pas encombré par les détails de la mise en cache.

functools.lru_cache décorateur :

Si vous devez prendre en charge d'anciennes versions de Python, functools.lru_cache fonctionne dans Python 3.2+. Par défaut, il ne met en cache que les 128 appels les plus récemment utilisés, mais vous pouvez définir l'attribut maxsize a None pour indiquer que le cache ne doit jamais expirer :

@functools.lru_cache(maxsize=None)
def fib(num):
    # etc

---

Answer 3

Les autres réponses couvrent assez bien ce que c'est. Je ne vais pas répéter cela. Juste quelques points qui pourraient vous être utiles.

En général, la mémorisation est une opération que vous pouvez appliquer à toute fonction qui calcule quelque chose (coûteux) et renvoie une valeur. Pour cette raison, elle est souvent implémentée en tant que décorateur . La mise en œuvre est simple et ressemblerait à ceci

memoised_function = memoise(actual_function)

ou exprimé comme un décorateur

@memoise
def actual_function(arg1, arg2):
   #body

Answer 4

La mémorisation consiste à conserver les résultats de calculs coûteux et à renvoyer le résultat mis en cache plutôt que de le recalculer en permanence.

Voici un exemple :

def doSomeExpensiveCalculation(self, input):
    if input not in self.cache:
        <do expensive calculation>
        self.cache[input] = result
    return self.cache[input]

Une description plus complète peut être trouvée dans le entrée wikipedia sur la mémorisation .

Answer 5

Voici une solution qui fonctionnera avec des arguments de type liste ou dict sans pleurnicher :

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

Notez que cette approche peut être naturellement étendue à n'importe quel objet en implémentant votre propre fonction de hachage comme un cas spécial dans handle_item. Par exemple, pour que cette approche fonctionne pour une fonction qui prend un ensemble comme argument d'entrée, vous pouvez ajouter à handle_item :

if is_instance(x, set):
    return make_tuple(sorted(list(x)))