Le lru_cache de Python était lent (je l'ai étudié parce que je l'ai mal compris)

TL;DR Il n'est pas tard Notez que si vous ne définissez pas «maxsize» pour «lru_cache», il sera défini sur «128» par défaut. Référence

Quand j'ai utilisé functools.lru_cache dans la méthode de planification dynamique, c'était TLE

la mise en oeuvre

Dans D of AtCoder Beginner Contest184, le problème de DP a été posé.

from functools import lru_cache

def solve(n1: int, n2: int, n3: int) -> float:
    @lru_cache
    def expect(a: int, b: int, c: int) -> float:
        if 100 in (a, b, c):
            return 0

        return (a/(a+b+c)) * (expect(a+1, b, c) + 1) \
                + (b/(a+b+c)) * (expect(a, b+1, c) + 1) \
                + (c/(a+b+c)) * (expect(a, b, c+1) + 1)

    return expect(n1, n2, n3)

if __name__ == '__main__':
    a, b, c = map(int, input().split())
    print(solve(a, b, c))

Si vous le mettez en œuvre dans une telle atmosphère, TLE ...

def solve(n1: int, n2: int, n3: int) -> float:
    memo = [[[-1]*101]*101]*101
    def expect(a: int, b: int, c: int) -> float:
        if memo[a][b][c] >= 0:
            return memo[a][b][c]
        elif a == 100 or b == 100 or c == 100:
            memo[a][b][c] = 0
        else:
            memo[a][b] = (a/(a+b+c)) * (expect(a+1, b, c) + 1) \
                + (b/(a+b+c)) * (expect(a, b+1, c) + 1) \
                + (c/(a+b+c)) * (expect(a, b, c+1) + 1)
        return memo[a][b]

    return expect(n1, n2, n3)

if __name__ == '__main__':
    a, b, c = map(int, input().split())
    print(solve(a, b, c))

Je l'ai avec ça. Pourquoi?

Jetez un œil à functools.lru_cache

L'implémentation est ici [https://github.com/python/cpython/blob/master/Lib/functools.py#L479).

J'essaie de prendre en charge le traitement multi-thread, mais le traitement spécifique est le suivant.

Informations détenues

L'encapsuleur de lru_cache stocke les états suivants:

• cache cache Un objet de dictionnaire qui utilise un argument comme clé et un argument déroutant (root) qui inclut une valeur de retour comme valeur.

• hits / misses Peut être appelé avec cache_info (). «hits» est le nombre de fois où le cache a été utilisé. «Misses» est le nombre de fois où la fonction set a été appelée. Il est réinitialisé par cache_clear ().

• full Lorsque len (cache) dépasse maxsize, il devient True. Chaque fois que la fonction set est appelée après cela, la plus ancienne appelée est supprimée de root.

• root Ceci est très déroutant, mais dans un tableau de NEXT, PREV KEY, RESULT, les pointeurs sont récursivement dans l'ordre dans lequel ils ont été appelés dans NEXT et dans l'ordre inverse dans lequel ils ont été appelés dans PREV. Il est stocké. Autrement dit, root [PREV] [NEXT] devient root. De plus, le haut «KEY» et «PREV» sont toujours «None».

Exemple de root

Par exemple, supposons que la séquence de Fibonacci soit appelée comme suit.

from functools import lru_cache

@lru_cache
def fib(n):
    if n == 1 or n == 0:
        return 1

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

print(fib(3))

A ce moment, l'ordre de renvoi des résultats est fib (2) -> fib (1) -> fib (3). À ce stade, root est

{
  "PREV": {
    "PREV": {
      "PREV": {
        "PREV": self,
        "NEXT": self,
        "KEY": 2,
        "RESULT": 1
      },
      "NEXT": self,
      "KEY": 1,
      "RESULT": 1
    },
    "NEXT": self,
    "KEY": 3,
    "RESULT": 2
  },
  "NEXT": {
    "PREV": self,
    "NEXT": {
      "PREV": self,
      "NEXT": {
        "PREV": self,
        "NEXT": self,
        "KEY": 3,
        "RESULT": 2
      },
      "KEY": 1,
      "RESULT": 1
    },
    "KEY": 2,
    "RESULT": 1
  },
  "KEY": null,
  "RESULT": null
}

Je l'ai écrit comme JSON, mais c'est en fait un type de liste. Ici, écrire «self» signifie que le pointeur de «root» lui-même est stocké. Je ne savais pas comment l'écrire, alors je l'ai écrit comme ça. En regardant PREV, c'est 3-> 1-> 2 dans l'ordre de l'extérieur, et en regardant NEXT, c'est 2-> 1-> 3 de l'extérieur. Cet ordre change lorsqu'une fonction est appelée avec un argument mis en cache. Voir le code source pour une implémentation détaillée. Ce que nous faisons ici, c'est sauvegarder l'ordre dans lequel ils ont été appelés.

Comportement de maxsize

Premièrement, maxsize est le nombre d'enregistrements à mettre en cache dans lru_cache. Si cela est défini, chaque fois que «manque» est compté, il vérifie «len (cache)» pour voir s'il dépasse «maxsize». Chaque fois qu'il devient «plein», il supprime les informations les plus anciennes de «racine» et du cache.

Définition de maxsize

Jusqu'à présent, c'est en fait le comportement lorsque maxsize est défini. La valeur par défaut est maxsize = 128 sans aucun paramètre spécial. Si vous définissez d'abord maxsize = None, le comportement sera complètement différent. Il est facile à mettre en œuvre car il n'est plus nécessaire de considérer la commande. Puisqu'il y a des «hits» et des «ratés», vous pouvez voir ces informations en faisant quelque chose comme «fib.cache_info ()», mais il n'y a pas de «root» ou «full».

Qu'est-ce qui ne va pas cette fois

Il semble que le nombre de caches était insuffisant car il a été défini sur maxsize = 128 car le maxsize n'a pas été défini. Après de nombreuses recherches, j'ai spécifié maxsize = None et il n'est pas devenu TLE. De plus, la vitesse a été légèrement améliorée (plusieurs dizaines de ms) par rapport au cas où le cache était réglé sur `memo [a] [b] [c] '.

Donc, spécifions maxsize = None quand ce n'est pas nécessaire. (J'aurais dû lire un peu plus le document ...)