Implementierung von Memoisierung in JavaScript

Kernpunkte

• Memorisierung ist eine Programmierungstechnik, die die Leistung einer Funktion verbessert, indem die Ergebnisse früherer Berechnungen einer Funktion zwischengespeichert werden. Dies ist besonders nützlich für rekursive und mathematische Funktionen, die häufig die gleichen Parameter verwenden.
• Implementierung des Speichers beinhaltet die Verwendung von Caches, die durch die Eingabeparameter durch die Funktion indiziert sind. Wenn der Parameter im Cache vorhanden ist, wird der Cache -Wert zurückgegeben. Andernfalls wird die Funktion ausgeführt und das Ergebnis dem Cache hinzugefügt.
• Wenn sich das Auswendiglernen für Funktionen mit mehreren Parametern verwendet, kann ein mehrdimensionaler Cache verwendet werden oder alle Parameter können kombiniert werden, um einen einzelnen Index zu bilden. Objektparameter sollten vor der Verwendung als Indizes angestrebt werden.
• Auswendiglernen hat bestimmte Einschränkungen. Es erhöht den Speicherverbrauch und ist möglicherweise nicht für Funktionen geeignet, die schnell ausgeführt werden oder eine niedrige Frequenz aufrufen. Es kann nur mit Verweisen auf transparente Funktionen automatisiert werden, d. H. Der Ausgang hängt nur von seiner Eingabe ab und erzeugt keine Nebenwirkungen.

Programme verschwenden häufig Zeit damit, Funktionen aufzurufen, die das gleiche Ergebnis wiederholt neu berechnen. Dies gilt insbesondere für rekursive und mathematische Funktionen. Der Fibonacci -Zahlengenerator ist ein perfektes Beispiel. Eine Fibonacci -Sequenz ist eine Reihe von Ganzzahlen, die mit Nullsummen beginnen, wobei jeder Wert die Summe der ersten beiden Zahlen in der Sequenz ist. Nach dieser Definition sind die ersten zehn Fibonacci -Zahlen: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Aus programmierender Sicht werden die Fibonacci -Zahlen normalerweise unter Verwendung der folgenden Funktionen rekursiv berechnet. Diese Funktion funktioniert gut für kleinere "n" -Werte. Mit zunehmender "N" sinkt jedoch die Leistung rasch. Dies liegt daran, dass die beiden rekursiven Anrufe dieselbe Arbeit wiederholen. Um die 50. Fibonacci -Zahl beispielsweise zu berechnen, muss die rekursive Funktion mehr als 40 Milliarden Mal bezeichnet werden (40.730.022.147 um genau zu sein)! Um die Sache noch schlimmer zu machen, muss die 51. Figur berechnet werden, erfordert die Wiederholung der Arbeit fast vollständig zweimal. Wenn sich die Funktion erinnert, was sie zuvor berechnet hat, kann sie das Problem der wiederholten Arbeit lindern.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Grundlagen des Auswendiglernens

Memorisierung ist eine Programmierungstechnik, die versucht, die Leistung einer Funktion zu verbessern, indem die Ergebnisse der früheren Berechnungen einer Funktion zwischengespeichert werden. Da sich JavaScript -Objekte wie assoziative Arrays verhalten, sind sie ideal, um als Caches zu fungieren. Jedes Mal, wenn die Speicherfunktion aufgerufen wird, werden ihre Parameter für den Indexcache verwendet. Wenn die Daten vorhanden sind, kann sie zurückgegeben werden, ohne die gesamte Funktion auszuführen. Wenn die Daten jedoch nicht zwischengespeichert werden, wird die Funktion ausgeführt und das Ergebnis dem Cache hinzugefügt.

Im folgenden Beispiel wird die ursprüngliche Fibonacci -Funktion um den Speicher einbezogen. In diesem Beispiel gibt die anonyme Funktion selbst executierende eine interne Funktion f () zurück, die als Fibonacci-Funktion verwendet wird. Wenn f () zurückgegeben wird, ermöglicht es sein Verschluss, weiterhin auf das "Memo" -Objekt zuzugreifen, das alle vorherigen Ergebnisse speichert. Jedes Mal, wenn f () ausgeführt wird, wird zunächst überprüft, ob das Ergebnis des aktuellen "N" -Wertwerts existiert. Wenn vorhanden, wird der Cache -Wert zurückgegeben. Führen Sie ansonsten den ursprünglichen Fibonacci -Code aus. Beachten Sie, dass "Memo" außerhalb von F () definiert ist, damit es seinen Wert in mehreren Funktionsaufrufen beibehalten kann. Erinnern Sie sich daran, dass die ursprüngliche rekursive Funktion mehr als 40 Milliarden Mal bezeichnet wurde, bevor sie die 50. Fibonacci -Nummer berechnen konnte. Durch die Implementierung des Speichers fällt diese Zahl auf 99.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Verarbeitung mehrerer Parameter

im vorherigen Beispiel akzeptiert die Funktion einen einzelnen Parameter. Dies macht die Implementierung von Caching recht einfach. Leider erfordern die meisten Funktionen mehrere Parameter, die zwischengespeicherte Indizes komplizieren. Um eine Funktion mit mehreren Parametern zu merken, muss der Cache zu mehrdimensional werden oder alle Parameter müssen kombiniert werden, um einen einzelnen Index zu bilden.

Bei mehrdimensionalen Methoden wird Cache zur Hierarchie des Objekts, nicht zu einem einzelnen Objekt. Jede Dimension wird dann durch einen einzelnen Parameter indiziert. Das folgende Beispiel implementiert einen mehrdimensionalen Cache für die Fibonacci -Funktion. In diesem Beispiel akzeptiert die Funktion einen zusätzlichen Parameter "x" und er tut nichts. Jedes Mal, wenn eine Funktion aufgerufen wird, überprüft der Code, ob die Dimension "x" vorhanden ist, und initialisiert sie, wenn es nicht vorhanden ist. Seitdem wird die Dimension "X" verwendet, um den "n" -Wert zu zwischenstrahlen. Das Ergebnis ist, dass Funktionen Fibonacci ("Foo", 3) und Fibonacci ("Bar", 3) nicht als das gleiche Ergebnis angesehen werden.

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

Die Alternative zu mehrdimensionalem Cache ist ein einzelnes Cache -Objekt, das durch eine Kombination aller Parameter der Funktion indiziert wird. Bei dieser Methode werden die Parameter in ein Array konvertiert und dann für den Indexcache verwendet. Jede Funktion verfügt über ein integriertes Objekt mit dem Namen "Argumente", das die in Parametern bestehenden übergebenen. "Argumente" ist ein Objekt vom Typ, der als Array -Objekt der Klasse bezeichnet wird. Es ähnelt einem Array, kann aber nicht für Index -Cache verwendet werden. Daher muss es zuerst in das tatsächliche Array umgewandelt werden. Dies kann mit der Array Slice () -Methode erfolgen. Der Cache kann dann unter Verwendung von Array -Darstellungen indexiert werden, wie zuvor gezeigt. Das folgende Beispiel zeigt, wie dies erreicht werden kann. Beachten Sie, dass die zusätzliche Variable "Slice" als Referenz auf die Array Slice () -Methode definiert ist. Durch das Speichern dieser Referenz können Sie wiederholte Berechnungen von Array.Prototype.slice () Overhead vermeiden. Verwenden Sie dann die Methode call (), um Slice () auf "Argumente" anzuwenden.

var fibonacci = (function() {
  var memo = {};

  function f(x, n) {
    var value;

    memo[x] = memo[x] || {};

    if (x in memo && n in memo[x]) {
      value = memo[x][n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(x, n - 1) + f(x, n - 2);

      memo[x][n] = value;
    }

    return value;
  }

  return f;
})();

Cache -Objektparameter

Das hier eingeführte Speicherschema verarbeitet Objektparameter nicht gut. Wenn Objekte als Indizes verwendet werden, werden sie zunächst in String -Darstellungen wie "[Objektobjekt]" konvertiert. Dies führt dazu, dass mehrere Objekte falsch an denselben Cache -Speicherort zugeordnet werden. Dieses Verhalten kann korrigiert werden, indem Objektparameter vor der Indexierung abgestuft werden. Leider verlangsamt dies auch den Speicherprozess. Das folgende Beispiel erstellt eine allgemeine Speicherfunktion, die ein Objekt als Argument nennt. Beachten Sie, dass Objektparameter mit json.stringify () angestrahlt werden, um zwischengespeicherte Indizes zu erstellen.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Automatischer Speicher

In allen früheren Beispielen wird die Funktion explizit geändert, um Speicher hinzuzufügen. Eine auswendig ausgeführte Infrastruktur kann auch implementiert werden, ohne die Funktionen überhaupt zu ändern. Dies ist nützlich, da die Funktionslogik separat von der auswendigem Logik implementiert werden kann. Dies geschieht durch das Erstellen einer Versorgungsfunktion, die die Funktion als Eingabe annimmt und sie anwendet, um sie auswendig zu lernen. Die folgende Memoize () -Funktion nimmt die Funktion "func" als Eingabe. Memoize () gibt eine neue Funktion zurück, die den Cache -Mechanismus um "Func" umschließt. Beachten Sie, dass diese Funktion keine Objektparameter behandelt. Um das Objekt zu verarbeiten, wird eine Schleife benötigt, mit der jeder Parameter einzeln und nach Bedarf Stringify überprüft wird.

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

Einschränkungen

Bei der Verwirklichung des Speichers müssen die folgenden Punkte in Erinnerung bleiben. Durch die Speicherung alter Ergebnisse verbraucht die Memorisierungsfunktion zusätzlichen Speicher. Im Fibonacci -Beispiel ist der zusätzliche Speicherverbrauch unbegrenzt. Wenn Speicherverwendung ein Problem ist, sollte ein Cache mit fester Größe verwendet werden. Der mit dem Speicher verknüpfte Overhead kann es auch für Funktionen, die sehr schnell ausgeführt werden oder eine niedrige Frequenz aufweisen, ungeeignet machen.

Die größte Einschränkung des Speichers besteht darin, dass sie nur automatisch auf die transparenten

-Referenzfunktionen angewendet werden kann. Wenn die Ausgabe einer Funktion nur von ihrer Eingabe abhängt und keine Nebenwirkungen erzeugt, wird die Funktion als Referenztransparent angesehen. Anrufe, die transparente Funktionen referenzieren, können durch ihren Rückgabewert ersetzt werden, ohne die Semantik des Programms zu ändern. Die Fibonacci -Funktion wird transparent verwiesen, da sie vollständig vom Wert von "n" abhängt. Im folgenden Beispiel wird die Funktion foo () nicht transparent verwiesen, da sie die globale Variable "Balken" verwendet. Da "Bar" außerhalb von Foo () geändert werden kann, gibt es keine Garantie dafür, dass der Rückgabewert für jeden Eingangswert unverändert bleibt. In diesem Beispiel sind die beiden Aufrufe bei Foo () die Werte 2 und 3, selbst wenn die an die beiden Anrufe übergebenen Parameter gleich sind.

var fibonacci = (function() {
  var memo = {};

  function f(x, n) {
    var value;

    memo[x] = memo[x] || {};

    if (x in memo && n in memo[x]) {
      value = memo[x][n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(x, n - 1) + f(x, n - 2);

      memo[x][n] = value;
    }

    return value;
  }

  return f;
})();

Dinge, die Sie an

erinnern sollten

• Memorisierung kann die Leistung möglicherweise verbessern, indem die Ergebnisse früherer Funktionsaufrufe zwischengespeichert werden.
• Die Speicherfunktion speichert einen Cache, der durch ihre Eingabeparameter indiziert ist. Wenn der Parameter im Cache vorhanden ist, wird der Cache -Wert zurückgegeben. Führen Sie ansonsten die Funktion aus und fügen Sie den neu berechneten Wert zum Cache hinzu.
• Objektparameter sollten vor der Verwendung als Indizes angestrahlt werden.
• Memorisierung kann automatisch auf transparente Funktionen angewendet werden.
• Auswendiglernen ist möglicherweise nicht ideal für Funktionen, die nicht häufig bezeichnet oder schnell ausgeführt werden.

FAQ beim Memorisieren in JavaScript (FAQ)

Was ist der Hauptzweck für die Verwendung von Speicher in JavaScript?

Memorisierung ist eine Programmierungstechnik, mit der Computerprogramme in JavaScript und anderen Sprachen optimiert werden können. Diese Technik umfasst das Speichern der Ergebnisse teurer Funktionsaufrufe und die Wiederverwendung, wenn dieselbe Eingabe erneut angezeigt wird. Dies kann die Leistung des Programms erheblich verbessern, indem unnötige Berechnungen vermieden werden. Es ist besonders nützlich in Situationen, in denen rekursive Funktionen oder Funktionen, die wiederholt mit denselben Parametern aufgerufen werden.

Wie funktioniert das Speicher in JavaScript?

In JavaScript funktioniert der Speicher, indem ein Cache erstellt wird, um die Ergebnisse der Funktionsaufrufe zu speichern. Beim Aufrufen einer Funktion prüft die Funktion zuerst, ob das Ergebnis der angegebenen Eingabe bereits im Cache liegt. In diesem Fall gibt die Funktion das zwischengespeicherte Ergebnis zurück, anstatt die Berechnung erneut durchzuführen. Wenn sich das Ergebnis nicht im Cache befindet, führt die Funktion die Berechnung durch, speichert das Ergebnis im Cache und gibt das Ergebnis zurück.

Können Sie in JavaScript ein Beispiel für eine auswendig ausgeerlpfte Funktion angeben?

Betrachten wir natürlich ein Beispiel für eine einfache Funktion, die das Faktor der numerischen Berechnung berechnet. Ohne Speicher sieht die Funktion so aus:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Mit dem Speicher können wir diese Funktion optimieren, indem wir die Ergebnisse früherer Funktionsaufrufe speichern:

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

Gibt es Einschränkungen oder Nachteile der Verwendung von Speicher in JavaScript?

Während das Auswendiglernen die Leistung von JavaScript -Programmen erheblich verbessern kann, ist dies nicht ohne Einschränkungen. Ein großer Nachteil des Speichers ist, dass es viel Speicher verbrauchen kann, insbesondere wenn viele Daten im Cache gespeichert werden. Wenn dies nicht ordnungsgemäß verwaltet wird, kann dies zu Leistungsproblemen führen. Darüber hinaus ist der Speicher nur dann gültig, wenn die Funktion mehrmals mit demselben Parameter aufgerufen wird. Das Auswendiglernen bietet keine Leistungsvorteile, wenn die Funktionseingabe immer unterschiedlich ist.

Kann ich ein Auswendiglernen für alle Arten von Funktionen in JavaScript verwenden?

Memorisierung ist am effektivsten, wenn sie mit reinen Funktionen verwendet werden. Eine reine Funktion ist eine Funktion, die immer das gleiche Ergebnis derselben Eingabe zurückgibt und keine Nebenwirkungen erzeugt. Das Auswendiglernen der Funktion kann zu unerwarteten Ergebnissen führen, wenn sie von einem externen Zustand abhängt oder Nebenwirkungen hat. Während Sie sich also technisch für jede Art von Funktion in JavaScript auswendig machen können, eignet sich dies für reine Funktionen am besten.

Wie kann man Funktionen mit mehreren Parametern in JavaScript auswendig lernen?

Speicher für eine Funktion mit mehreren Parametern kann etwas kompliziert sein, aber dies ist definitiv möglich. Eine Möglichkeit besteht darin, die Argumente in Zeichenfolgen umzuwandeln, die als Schlüssel im Cache verwendet werden können. Hier ist ein Beispiel:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Gibt es eine Bibliothek oder ein Tool, das sich in JavaScript auswendig lernen kann?

Ja, es gibt Bibliotheken und Tools, die sich in JavaScript auswendig lernen können. Beispielsweise bietet die beliebte JavaScript -Dienstprogrammbibliothek Lodash eine _.memoize -Funktion, die Funktionen leicht auswendig lernen kann. In ähnlicher Weise bietet die RAMDA -Bibliothek eine R.memoizeWith -Funktion, mit der Sie benutzerdefinierte Cache -Schlüsselfunktionen angeben können.

Wie lösche ich den Cache in der Speicherfunktion?

Der Cache in der Speicherfunktion kann gelöscht werden, indem einfach das Cache -Objekt zurückgesetzt wird. Hier ist ein Beispiel:

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

Kann Speicher in JavaScript -Frameworks wie React verwendet werden?

Ja, der Speicher ist in JavaScript -Frameworks wie React sehr nützlich. Beispielsweise bietet React eine React.memo -Funktion, mit der Komponenten auswendig sein können. Dies kann dazu beitragen, die Leistung zu verbessern, indem sie unnötig erneuert werden.

Wie ist das Speicher in JavaScript im Vergleich zu anderen Optimierungstechniken?

Memorisierung ist eine leistungsstarke Optimierungstechnik, aber nicht immer die beste Lösung. In einigen Fällen können andere Optimierungstechniken wie Dejitter und Drosselung besser geeignet sein. Der Schlüssel besteht darin, die spezifischen Bedürfnisse und Einschränkungen des Programms zu verstehen und die richtige Optimierungstechnologie auszuwählen.

Das obige ist der detaillierte Inhalt vonImplementierung von Memoisierung in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!