Pythons lru_cache war langsam (ich habe es untersucht, weil ich es falsch verstanden habe)

TL;DR Es ist nicht spät Beachten Sie, dass, wenn Sie nicht "maxsize" für "lru_cache" festlegen, diese standardmäßig auf "128" gesetzt wird. Referenz

Als ich in der dynamischen Planungsmethode functools.lru_cache verwendete, war es TLE

Implementierung

In D des AtCoder Beginner Contest184 wurde das Problem der DP gestellt.

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

Wenn Sie es in einer solchen Atmosphäre implementieren, 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))

Ich habe es damit verstanden. Warum?

Schauen Sie sich functools.lru_cache an

Die Implementierung finden Sie hier [https://github.com/python/cpython/blob/master/Lib/functools.py#L479].

Wir haben es möglich gemacht, Multithread-Verarbeitung zu handhaben, aber die spezifische Verarbeitung ist wie folgt.

Informationen gehalten

Der Wrapper für "lru_cache" speichert die folgenden Zustände:

• cache Zwischenspeicher Ein Wörterbuchobjekt, das ein Argument als Schlüssel und ein verwirrendes (root) verwendet, das einen Rückgabewert als Wert enthält.

• hits / misses Es kann mit cache_info () aufgerufen werden. "Treffer" gibt an, wie oft der Cache verwendet wurde. "Fehlschläge" gibt an, wie oft die eingestellte Funktion aufgerufen wurde. Es wird durch cache_clear () zurückgesetzt.

• full Wenn "len (cache)" "maxsize" überschreitet, wird es "True". Jedes Mal, wenn die gesetzte Funktion danach aufgerufen wird, wird die älteste aufgerufene Funktion aus "root" gelöscht.

• root Dies ist sehr verwirrend, aber in einem Array von "NEXT", "PREV", "KEY", "RESULT" sind die Zeiger rekursiv in der Reihenfolge, in der sie in "NEXT" aufgerufen wurden, und in der umgekehrten Reihenfolge, in der sie in "PREV" aufgerufen wurden. Es wird gespeichert. Das heißt, "root [PREV] [NEXT]" wird zu "root". Außerdem sind die oberen "KEY" und "PREV" immer "None".

root Beispiel

Angenommen, die Fibonacci-Sequenz wird wie folgt aufgerufen.

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

Zu diesem Zeitpunkt lautet die Reihenfolge der Rückgabe der Ergebnisse "fib (2)" -> "fib (1)" -> "fib (3)". Zu diesem Zeitpunkt ist "root"

{
  "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
}

Ich habe es wie JSON geschrieben, aber es ist eigentlich ein Listentyp. Hier bedeutet das Schreiben von "self", dass der Zeiger von "root" selbst gespeichert wird. Ich wusste nicht, wie ich es schreiben sollte, also schrieb ich es so. Wenn man "PREV" betrachtet, ist es von außen 3-> 1-> 2, und wenn man "NEXT" betrachtet, ist es von außen 2-> 1-> 3. Diese Reihenfolge ändert sich, wenn eine Funktion mit einem zwischengespeicherten Argument aufgerufen wird. Eine detaillierte Implementierung finden Sie im Quellcode. Wir speichern hier die Reihenfolge, in der sie aufgerufen wurden.

Verhalten von "maxsize"

Erstens ist "maxsize" die Anzahl der Datensätze, die in "lru_cache" zwischengespeichert werden sollen. Wenn dies eingestellt ist, überprüft es jedes Mal, wenn "Fehlschläge" gezählt werden, "len (Cache)", um festzustellen, ob es "maxsize" überschreitet. Jedes Mal, wenn es "voll" wird, werden die ältesten Informationen aus "root" und dem Cache gelöscht.

Einstellung von "maxsize"

Bisher ist es tatsächlich das Verhalten, wenn "maxsize" eingestellt ist. Der Standardwert ist "maxsize = 128" ohne spezielle Einstellungen. Wenn Sie zuerst "maxsize = None" setzen, ist das Verhalten völlig anders. Die Implementierung ist einfach, da die Reihenfolge nicht mehr berücksichtigt werden muss. Da es "Treffer" und "Fehler" gibt, können Sie diese Informationen anzeigen, indem Sie etwas wie "fib.cache_info ()" ausführen, aber es gibt keine "root" oder "full".

Was diesmal schief gelaufen ist

Es scheint, dass die Anzahl der Caches unzureichend war, weil sie auf "maxsize = 128" gesetzt wurde, weil die "maxsize" nicht gesetzt wurde. Nach vielen Recherchen habe ich "maxsize = None" angegeben und es wurde nicht "TLE". Außerdem wurde die Geschwindigkeit geringfügig verbessert (einige zehn ms), verglichen mit dem Zeitpunkt, als der Cache auf "memo [a] [b] [c]" eingestellt war.

Geben wir also "maxsize = None" an, wenn es nicht benötigt wird. (Ich hätte das Dokument etwas mehr lesen sollen ...)