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

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

La mémorisation se réfère effectivement à la mémorisation ("mémorisation" → "mémorandum" → à mémoriser) des résultats d'appels de méthode en fonction des entrées de méthode, puis au retour du résultat mémorisé plutôt que de calculer à nouveau le résultat. Vous pouvez le considérer comme un cache pour les résultats de la méthode. Pour plus de détails, voir page 387 pour la définition dans Introduction To Algorithms (3e), Cormen et al.

Un exemple simple de calcul de factorielles 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 devenir 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]

Alors:

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

factorial = Memoize(factorial)

Une fonctionnalité connue sous le nom de " décorateurs " a été ajoutée dans Python 2.4 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)

La bibliothèque Python Decorator possède un décorateur similaire appelé memoizedqui est légèrement plus robuste que la Memoizeclasse présentée ici.

Nouveau dans Python 3.2 est functools.lru_cache. Par défaut, il met en cache uniquement les 128 plus récemment des appels utilisés, mais vous pouvez définir l' maxsizeà Noneindiquer que le cache ne doit jamais expirer:

import functools

@functools.lru_cache(maxsize=None)
def fib(num):
    if num < 2:
        return num
    else:
        return fib(num-1) + fib(num-2)

Cette fonction en elle-même est très lente, essayez fib(36)et vous devrez attendre une dizaine de secondes.

L'ajout d' lru_cacheannotations 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, tandis que le code n'est pas encombré par les détails de la mise en cache.

Les autres réponses couvrent assez bien ce que c'est. Je ne répète pas ça. Juste quelques points qui pourraient vous être utiles.

Habituellement, la mémoisation est une opération que vous pouvez appliquer à n'importe quelle fonction qui calcule quelque chose (cher) et renvoie une valeur. Pour cette raison, il est souvent mis en œuvre en tant que décorateur . L'implémentation est simple et ce serait quelque chose comme ça

memoised_function = memoise(actual_function)

ou exprimé en tant que décorateur

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

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 continu.

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 l' entrée wikipedia sur la mémorisation .

N'oublions pas la hasattrfonction intégrée, pour ceux qui veulent fabriquer à la main. De cette façon, vous pouvez conserver le cache mem dans la définition de la fonction (par opposition à un global).

def fact(n):
    if not hasattr(fact, 'mem'):
        fact.mem = {1: 1}
    if not n in fact.mem:
        fact.mem[n] = n * fact(n - 1)
    return fact.mem[n]

J'ai trouvé cela extrêmement utile

def memoize(function):
    from functools import wraps

    memo = {}

    @wraps(function)
    def wrapper(*args):
        if args in memo:
            return memo[args]
        else:
            rv = function(*args)
            memo[args] = rv
            return rv
    return wrapper


@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)

fibonacci(25)

La mémorisation consiste essentiellement à sauvegarder les résultats des opérations passées effectuées avec des algorithmes récursifs afin de réduire la nécessité de parcourir l'arbre de récursivité si le même calcul est requis à un stade ultérieur.

voir http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Exemple de mémorisation de Fibonacci en Python:

fibcache = {}
def fib(num):
    if num in fibcache:
        return fibcache[num]
    else:
        fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return fibcache[num]

La mémorisation est la conversion de fonctions en structures de données. Habituellement, on veut que la conversion se fasse de manière incrémentielle et paresseuse (à la demande d'un élément de domaine donné - ou "clé"). Dans les langages fonctionnels paresseux, cette conversion paresseuse peut se produire automatiquement, et ainsi la mémorisation peut être implémentée sans effets secondaires (explicites).

Eh bien, je devrais d'abord répondre à la première partie: qu'est-ce que la mémorisation?

C'est juste une méthode pour échanger de la mémoire contre du temps. Pensez à la table de multiplication .

L'utilisation d'un objet mutable comme valeur par défaut dans Python est généralement considérée comme mauvaise. Mais si vous l'utilisez à bon escient, il peut être utile d'implémenter a memoization.

Voici un exemple adapté de http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

En utilisant un mutable dictdans la définition de la fonction, les résultats intermédiaires calculés peuvent être mis en cache (par exemple lors du calcul factorial(10)après calcul factorial(9), nous pouvons réutiliser tous les résultats intermédiaires)

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]

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 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)))

Solution qui fonctionne avec les arguments de position et de mot-clé indépendamment de l'ordre dans lequel les arguments de mot-clé ont été passés (en utilisant inspect.getargspec ):

import inspect
import functools

def memoize(fn):
    cache = fn.cache = {}
    @functools.wraps(fn)
    def memoizer(*args, **kwargs):
        kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
        key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
        if key not in cache:
            cache[key] = fn(**kwargs)
        return cache[key]
    return memoizer

Question similaire: L' identification de la fonction varargs équivalente appelle la mémorisation en Python

cache = {}
def fib(n):
    if n <= 1:
        return n
    else:
        if n not in cache:
            cache[n] = fib(n-1) + fib(n-2)
        return cache[n]

Je voulais juste ajouter aux réponses déjà fournies, la bibliothèque de décorateur Python a quelques implémentations simples mais utiles qui peuvent également mémoriser des "types non partageables", contrairement à functools.lru_cache.