Die Geschichte eines Problems: Der kürzeste JavaScript-Memoizer

Es war am Abend, am Vorabend der jährlichen HolyJS- Konferenz in St. Petersburg. Unser Unternehmen ist seit mehreren Jahren Sponsor: Dementsprechend hat es auch einen eigenen Stand mit interessanten Interessen für den neugierigen Geist fürsorglicher Entwickler. Als das Hauptgericht fertig war und alle Aufgaben von Anwälten überprüft und erledigt wurden, beschloss ich, meinen Kollegen nachts mehr intellektuelles Essen zu geben:

Schreiben Sie einen Memoizer - eine Dekorationsfunktion, die die Ergebnisse der Ausführung einer umschlossenen Funktion speichert, um wiederholte Berechnungen zu verhindern. Sie haben nur 50 Zeichen.

Die Sprache ist natürlich JavaScript . Die Aufgabe selbst ist ein Klassiker, aber die Beschränkung auf 50 Zeichen wurde zu einer echten Herausforderung.

In den Pausen des ersten Konferenztages diskutierten wir Optionen zur Erreichung des Ziels und reduzierten schrittweise die Reaktion. Der ganze Hype war gekrönt von der Idee, die Aufgabe mit allen Teilnehmern der Konferenz zu teilen, und am zweiten Tag visualisierten wir die Aufgabe (siehe Anhang) und begannen, Formulare an diejenigen zu verteilen, die wollten. Als Ergebnis erhielten wir ungefähr 40 Lösungen und waren erneut von der außergewöhnlichen Community der js-Entwickler überzeugt, aber Dmitry Kataevs Rekord (SEMrush) von 53 Zeichen blieb bestehen. Lass es uns herausfinden!

Gewohnheitsmäßige Umsetzung

function memoize(f) { let cache = {}; return function ret() { let key = JSON.stringify(arguments); if (!cache.hasOwnProperty(key)) { cache[key] = f.apply(this, arguments); } return cache[key]; } } 

Ergebnis: ~ 190 Zeichen

• memoize - unser memoizer
• f - dekorierte, verpackte Funktion
• ret - resultierende Funktion

Um die Antwort zu erhalten - die Größe der Funktion - verwenden wir:

 memoize.toString().replace(/\s+/g, ' ').length 

Bei der Bewertung der Größe einer Funktion achten wir auf ihren Körper und eine Liste von Parametern. Wenn die Funktion anonym ist, wird die Deklaration nicht berücksichtigt.

Einfache Tests zum Testen der Gesundheit nach Missbrauch:

 const log = memoize(console.log); const inc = memoize(o => ox + 1); 

Als nächstes wird das Ergebnis jeder Implementierung durch das Testergebnis markiert.

Nettoimplementierung

Zunächst möchte ich die Funktionsdeklaration zugunsten der Pfeilfunktion loswerden, da wir an diesem Kontext nicht interessiert sind, keine Argumente ansprechen und als Konstruktor nicht beabsichtigen, neue durchzurufen. Gleichzeitig werden wir die Namen der verwendeten lokalen Variablen reduzieren:

 const memoize = f => { let c = {}; return function() { let k = JSON.stringify(arguments); if (!c.hasOwnProperty(k)) { c[k] = f.apply(this, arguments); } return c[k]; } } 

Ergebnis: 154 , Tests bestanden

Dann können wir eine ähnliche Operation mit der resultierenden Funktion ausführen, aber dort brauchen wir Argumente . Hier kommt der Spread-Operator zur Rettung, sodass wir das übergebene iterierbare Objekt der Argumente durch die Array-Variable a ersetzen können. Außerdem werden wir diesen Kontext nicht mehr an die zu dekorierende Funktion übergeben: Falls erforderlich, helfen Function.prototype.bind oder unser Polyfil.

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); if (!c.hasOwnProperty(k)) { c[k] = f(...a); } return c[k]; } } 

Ergebnis: 127 , Tests bestanden

Nun wenden wir uns dem Körper der resultierenden Funktion zu. Das Auffinden des Schlüssels im Cache und das Zurückgeben des Werts ist natürlich umständlich. Versuchen wir zu reduzieren, wie:

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return c[k] || (c[k] = f(...a)); } } 

Ergebnis: 101 , Test 3 und 4 fielen

Hier geben wir die hasOwnProperty- Methode auf. Wir können es uns leisten, da das Ergebnis der Serialisierung des Argumentarrays über JSON.stringify immer "[...]" ist und es unwahrscheinlich ist, dass eine solche Eigenschaft im Prototyp-Cache ( Objekt ) angezeigt wird.

Als nächstes verwenden wir die Funktion des "logischen" ODER-Operators, um den ersten Ausdruck zurückzugeben, wenn er mit der vorherigen Funktionsberechnung in " true" oder auf andere Weise in den zweiten Ausdruck konvertiert werden kann.

Und hier sind die Tests 3 und 4 gefallen. Dies geschah, weil die dekorierte Funktion console.log keinen Wert zurückgibt : Das Ergebnis ist undefiniert . Wir legen dies in den Cache, und wenn wir versuchen, die Disjunctor-Funktion zu überprüfen, wenn wir sie erneut aufrufen, werden wir im ersten Operanden implizit false angezeigt und gelangen dementsprechend in den zweiten, was zum Funktionsaufruf führt. Dieser Effekt tritt für alle auf false reduzierten Ergebnisse auf: 0, "", null, NaN usw.

Anstelle der Anweisung OR und if können wir einen bedingten ternären Operator verwenden:

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return c.hasOwnProperty(k) ?c[k] :c[k] = f(...a); } } 

Ergebnis: 118 , Tests bestanden

Sehr leicht reduziert. Aber was ist, wenn Sie Map als Speicher anstelle eines einfachen Objekts verwenden? Es gibt auch eine kurze Methode:

 const memoize = f => { let c = new Map; return (...a) => { let k = JSON.stringify(a); return (c.has(k) ?c :c.set(k, f(...a))).get(k); } } 

Ergebnis: 121 , Tests bestanden

Reduzieren komplett fehlgeschlagen. Aber Karte sofort zu verwerfen ist es nicht wert. Diese Implementierung der Schlüsselwertspeicherung ermöglicht es Ihnen, Objekte als Schlüssel zu verwenden. Und das heißt, sollten wir JSON.stringify überhaupt aufgeben?

 const memoize = f => { let c = new Map; return (...a) => (c.has(a) ?c :c.set(a, f(...a))).get(a); } 

Ergebnis: 83 , Test 3 und 4 fielen

Es sieht sehr vielversprechend aus! Die Tests 3 und 4 fielen jedoch wieder ab. Dies liegt daran, dass der Vergleich der Schlüssel im Map- Objekt mithilfe des SameValueZero- Algorithmus implementiert wird. Wenn Sie die Details mit NaN, -0 und 0 weglassen, funktioniert dies ähnlich wie bei einem strengen Vergleichsoperator ( === ). Und wir haben ein neues Array von Argumenten (und damit ein Objekt) für jeden Aufruf der umschlossenen Funktion, selbst mit denselben Werten. Der Vergleich erfolgt gemäß der Referenz des Objekts, und daher findet die Map.prototype.has- Methode niemals etwas.

Daher hat die Verwendung von Map uns hasOwnProperty oder JSON.stringify nicht reduziert.

Der Bediener kommt zur Rettung, der prüft, ob ein Objekt in einem Objekt oder in der Kette seiner Prototypen vorhanden ist. Warum wir keine Angst vor der Suche in Prototypen haben können, wurde oben erklärt.

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return k in c ?c[k] :c[k] = f(...a); } } 

Ergebnis: 105 , Tests bestanden

Der Hauptteil des Memoizers und der resultierenden Funktion besteht aus zwei Ausdrücken, bei denen eine lokale Variable vor der Logik in der return-Anweisung deklariert und initialisiert werden muss. Ist es hier möglich, den Körper der Pfeilfunktion auf einen Ausdruck zu reduzieren? Natürlich unter Verwendung des IIFE-Musters ( Sofort aufgerufener Funktionsausdruck ):

 const memoize = f => (c => (...a) => (k => k in c ?c[k] : c[k] = f(...a))(JSON.stringify(a)) )({}); 

Ergebnis: 82 , Tests bestanden

Es ist Zeit, zusätzliche Räume loszuwerden:

 f=>(c=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)))({}); 

Ergebnis: 68 , Tests bestanden

Offensichtlich ist der Engpass jetzt die lange JSON.stringify- Methode, die das Objekt rekursiv in eine JSON-Zeichenfolge serialisiert, die wir als Schlüssel verwenden. Tatsächlich benötigen wir keine Serialisierungsfunktion, sondern eine Hash-Funktion, mit der wir die Gleichheit von Objekten überprüfen können, da sie in anderen Sprachen funktioniert. Leider gibt es in JavaScript keine native Lösung, und das selbst geschriebene hashCode-Polyphil im Object- Prototyp liegt eindeutig außerhalb des Bereichs.

Hmm, warum müssen wir uns überhaupt serialisieren? Wenn Sie einem Objekt ein Element per Schlüssel hinzufügen, wird dessen toString implizit aufgerufen. Da wir uns geweigert haben, das iterierbare Argumentobjekt zugunsten des Arrays durch den Spread-Operator zu verwenden , erfolgt der Aufruf von String nicht von Object.prototype , sondern von Array.prototype , in dem die Elemente neu definiert und durch Kommas getrennt werden. Für einen anderen Satz von Argumenten erhalten wir also einen anderen Schlüssel.

 f=>(c=>(...a)=>a in c?c[a]:c[a]=f(...a))({}); 

Ergebnis: 44 , Test 6 fiel

Test 6 beginnt gerade zu fallen. Es scheint, dass der Rückgabewert das Ergebnis eines vorherigen Funktionsaufrufs in Test 5 ist. Warum geschieht dies? Ja, wir haben den Aufruf von String für das Argumentobjekt umgangen, aber wir haben nicht berücksichtigt, dass jedes Argument auch ein komplexes Objekt sein kann. Wir rufen toString auf, von dem wir das Lieblingsobjekt [Objektobjekt] aller erhalten. Dies bedeutet, dass die Argumente {x: 1} und {x: 2} denselben Schlüssel im Hash verwenden.

Die zur Konvertierung in base64 verwendete Btoa schien ein guter Anwärter für die Serialisierungsfunktion zu sein. Aber er führt zuerst zur Saite, also keine Chance. Wir dachten in Richtung der Erzeugung eines URI und der Bildung eines ArrayBuffers an alle Funktionen, um einen Hash oder einen serialisierten Wert zu erhalten. Aber sie blieben an Ort und Stelle.

Übrigens hat JSON.stringify seine eigenen Besonderheiten: Unendlichkeit, NaN, undefiniert, Symbol wird auf null gesetzt . Gleiches gilt für Funktionen. Wenn möglich, erfolgt ein impliziter Aufruf von JSON vom Objekt aus, und Map und Set werden durch einfach aufgezählte Elemente dargestellt. Angesichts des endgültigen Formats ist dies verständlich: JSON.

Was kommt als nächstes?

Toxische Modifikation

Wir alle lieben sicherlich reine Funktionen, aber angesichts des Problems lohnt sich eine solche Anforderung nicht. Und das bedeutet, dass es Zeit ist, eine Prise Nebenwirkungen hinzuzufügen.

Initiieren Sie zunächst den Cache wie folgt:

 (f,c={})=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)); 

Ergebnis: 66 , Tests bestanden

Hier verwenden wir den Standardparameter in der Pfeilfunktion. Natürlich geben wir dem Kunden die Möglichkeit, seinen Cache festzulegen, na und? Wir haben aber 2 Zeichen reduziert.

Wie kann ich sonst einen Cache für eine zu dekorierende Funktion initiieren? Die richtige Antwort: Warum müssen wir sie initiieren? Warum nicht etwas Fertiges im Kontext einer zu verpackenden Funktion verwenden? Aber was ist, wenn die Funktion selbst? Wir alle wissen, dass Funktionen in JavaScript auch Objekte sind:

 f=>(...a)=>(k=>k in f?f[k]:f[k]=f(...a))(JSON.stringify(a)); 

Ergebnis: 59 , Tests bestanden

Hier schützt uns JSON.stringify vor Überschneidungen mit anderen Eigenschaften und Methoden des Objekts (Funktion) und umschließt die Argumente mit "[...]".

In diesem Moment rechtfertigt sich das zuvor angewendete IIFE- Muster nicht mehr. Es ist jedoch dringend erforderlich, einen einzelnen Ausdruck für die Pfeilfunktion beizubehalten, um eine return-Anweisung zu vermeiden:

 f=>(...a)=>(k=JSON.stringify(a),k in f?f[k]:f[k]=f(...a)); 

Ergebnis: 57 , Tests bestanden

Da wir die block-Anweisung in der Pfeilfunktion nicht verwenden, können wir keine Variable ( var oder let ) deklarieren, aber wir können den globalen Kontext verwenden - Nebeneffekt! Hier hat der Konflikt schon einige Chancen.

Mit dem Komma-Operator verketten wir zwei Ausdrücke zu einem: Die Operanden werden von links nach rechts ausgewertet, und das Ergebnis ist der Wert des letzteren.

 f=>(...a)=>(k=JSON.stringify(a))in f?f[k]:f[k]=f(...a); 

Ergebnis: 54 , Tests bestanden

Indem wir nur eine Klammer neu anordneten, wurden drei Zeichen gleichzeitig entfernt. Der Gruppierungsoperator bei der Berechnung des Schlüssels ermöglichte es uns, beide Operanden des Ausdrucks zu nur einem Ausdruck zu kombinieren, und die schließende Klammer entfernte das Leerzeichen vor dem Operator in .

Und endlich:

 f=>(...a)=>f[k=JSON.stringify(a)]=k in f?f[k]:f(...a); 

Ergebnis: 53 , Tests bestanden

Warum nicht den Schlüssel berechnen, wenn Sie auf den Wert zugreifen? Und dann - der gleiche ternäre Operator und die gleiche Zuordnung. Insgesamt: 53 Zeichen!

Ist es möglich, die restlichen 3 Zeichen zu entfernen?

Verständnis

Warum das alles? Diese einfache Aufgabe und die anschließende Konvertierungskette von Gewohnheit zu Unanständigkeit demonstrieren eine beträchtliche Anzahl von Merkmalen der JavaScript-Sprache. In unseren Diskussionen haben wir folgende Dinge angesprochen:

• Pfeilfunktionsausdruck
• Lexikalisches Scoping & IIFE
• Array-ähnliches Argumentobjekt
• Spread, Komma oder Operatoren
• Strenger Vergleichsoperator
• JSON.stringify & toString
• In Operator & hasOwnProperty
• Gruppierungsoperator & Blockanweisung
• Kartenobjekt
• und noch etwas

Solche Geschichten sind ein guter Grund, sich mit dem Studium der Besonderheiten einer Sprache zu beschäftigen und sie besser zu verstehen (oder umgekehrt). Und natürlich nur zum Spaß!

App

In seinen Abenteuern muss Rick oft seine Portalwaffe kalibrieren. Der Vorgang braucht Zeit, aber die Eingabe wird oft wiederholt. Der Wissenschaftler versucht, sich die bereits einmal erzielten Ergebnisse zu merken, um nicht wiederholt Berechnungen durchzuführen, aber Alkoholismus und senile Senilität wirken sich stark auf sein Gedächtnis aus. Er bat Morty, das Waffeneinstellungsmodul zu verbessern und eine Memoizer-Funktion hinzuzufügen. Diese Funktion sollte die Ergebnisse der zu dekorierenden Funktion speichern, um wiederholte Berechnungen zu verhindern. Nur Morty hat panische Angst vor langen Funktionen. Helfen Sie ihm, das Problem so kompakt wie möglich zu lösen. Die zu dekorierende Funktion kann Ganzzahlen, Zeichenfolgen, Boolesche Werte und Objekte als Argumente verwenden.