Dies ist der zweite Teil der Analyse der Aufgaben von unserem Stand auf der
HolyJS- Konferenz, die vom 24. bis 25. Mai in St. Petersburg stattfand. Für einen größeren Kontext wird empfohlen, zuerst den
ersten Teil dieses Materials zu lesen. Wenn der
Countdown-Ausdruck bereits abgeschlossen ist, fahren Sie mit dem nächsten Schritt fort.
Im Gegensatz zum Obskurantismus in der ersten Aufgabe haben die nächsten beiden bereits einen Hinweis auf die Anwendbarkeit normaler Anwendungen im Leben. JavaScript entwickelt sich immer noch recht schnell und Lösungen für die vorgeschlagenen Probleme heben einige der neuen Funktionen der Sprache hervor.
Aufgabe 2 ~ Von den Einen erledigt
Es wurde angenommen, dass der Code Antworten auf drei Anforderungen ausführen und an die Konsole drucken würde, und dann „fertig“. Aber etwas ist schief gelaufen ... Korrigieren Sie die Situation.
;(function() { let iter = { [Symbol.iterator]: function* iterf() { let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(req); } } }; for (const res of iter) { console.log(res); } console.log('done'); })();
Forschungsproblem
Was haben wir hier? Dies ist ein
iterierbares Iter- Objekt, bei dem ein
bekanntes Symbol.iterator- Symbol über
eine Generatorfunktion definiert ist . Im Hauptteil der Funktion wird ein Array
fs deklariert, dessen Elemente wiederum in die
Abruffunktion fallen, um eine Anforderung zu senden, und das Ergebnis jedes Funktionsaufrufs wird durch
Yield zurückgegeben . Welche Anfragen sendet die
Abruffunktion ? Alle Elemente des
fs- Arrays sind relative Pfade zu Ressourcen mit den Nummern 1, 2 bzw. 3. Die vollständige URL erhalten Sie also, indem Sie
location.origin mit der nächsten Nummer verketten, zum Beispiel:
GET https://www.example.com/1
Als nächstes wollen wir das
iter- Objekt durch
for-of iterieren, um schließlich jede Anforderung der Reihe nach mit der Ausgabe des Ergebnisses auszuführen - print "done". Das geht aber nicht! Das Problem ist, dass das
Abrufen asynchron ist und ein Versprechen zurückgibt, keine Antwort. Daher sehen wir in der Konsole ungefähr Folgendes:
Promise {pending}
Promise {pending}
Promise {pending}
done
Tatsächlich besteht die Aufgabe darin, dieselben Versprechen zu lösen.
Wir haben async / warten
Der erste Gedanke könnte sein, mit
Promise.all zu spielen: Geben Sie ihm unser
iterierbares Objekt,
dann ist die Ausgabe an die Konsole "erledigt". Er wird uns jedoch keine sequentielle Ausführung von Anforderungen (wie von der Bedingung gefordert) zur Verfügung stellen, sondern einfach alle senden und auf die letzte Antwort vor der allgemeinen Lösung warten.
Die einfachste Lösung hier wäre, im
For-of- Body auf die Lösung des nächsten Versprechens zu warten, bevor es an die Konsole ausgegeben wird:
for (const res of iter) { console.log(await res); }
Damit das
Warten auf Arbeit und "Fertig" am Ende angezeigt wird, müssen Sie die Hauptfunktion über
Async asynchron machen:
;(async function() { let iter = { }; for (const res of iter) { console.log(await res); } console.log('done'); })();
In diesem Fall wurde das Problem bereits (fast) gelöst:
GET 1st
Response 1st
GET 2nd
Response 2nd
GET 3rd
Response 3rd
done
Asynchroner Iterator und Generator
Wir werden die Hauptfunktion asynchron lassen, aber für das
Warten gibt es einen eleganteren Platz in dieser Aufgabe als im
For-of- Body: Dies ist die Verwendung der asynchronen Iteration durch
For-Wait-of , nämlich:
for await (const res of iter) { console.log(res); }
Alles wird funktionieren! Wenn Sie sich jedoch der Beschreibung
dieses Vorschlags zur asynchronen Iteration zuwenden, ist Folgendes interessant:
Wir führen eine Variation der for-of-Iterationsanweisung ein, die über asynchrone iterierbare Objekte iteriert. Asynchrone for-of-Anweisungen sind nur in asynchronen Funktionen und asynchronen Generatorfunktionen zulässig
Das heißt, unser Objekt sollte nicht nur
iterierbar , sondern durch das neue
bekannte Symbol
Symbol.asyncIterator und in unserem Fall bereits eine asynchrone Generatorfunktion „asynchronisierbar“ sein:
let iter = { [Symbol.asyncIterator]: async function* iterf() { let fs = ['/1', '/2', '/3']; for (const req in fs) { yield await fetch(req); } } };
Wie funktioniert es dann mit einem regulären Iterator und Generator? Ja, nur implizit, wie so viel mehr in dieser Sprache. Dieses
Warten ist schwierig: Wenn das Objekt nur
iterierbar ist , "konvertiert" es das Objekt bei asynchroner Iteration in asynchronisierbar, indem die Elemente (falls erforderlich) in
Promise mit der Erwartung einer Auflösung eingeschlossen werden. Er sprach ausführlicher
in einem Artikel von Axel Rauschmayer .
Wahrscheinlich wird es durch
Symbol.asyncIterator noch korrekter sein, da wir das
asyncIterable- Objekt für unsere asynchrone Iteration explizit durch
for-await-of erstellt haben , während wir die Möglichkeit haben, das Objekt bei Bedarf durch einen regulären Iterator für
for von zu ergänzen. Wenn Sie in einem Artikel über asynchrone Iterationen in JavaScript etwas Nützliches und Ausreichendes lesen möchten, dann
ist es hier !
Asynchrones
For-of befindet sich teilweise noch im Entwurf, wird jedoch bereits von modernen Browsern (außer Edge) und Node.js ab 10.x unterstützt. Wenn dies jemanden stört, können Sie immer Ihr eigenes kleines Polyphil für eine Kette von Versprechungen schreiben, zum Beispiel für ein
iterierbares Objekt:
const chain = (promises, callback) => new Promise(resolve => function next(it) { let i = it.next(); i.done ? resolve() : i.value.then(res => { callback(res); next(it); }); }(promises[Symbol.iterator]()) ); ;(async function() { let iter = { }; await chain(iter, console.log); console.log('done'); })();
Auf diese und jene Weise haben wir herausgefunden, wie Anfragen gesendet und Antworten verarbeitet werden. Aber in diesem Problem gibt es noch ein kleines, aber ärgerliches Problem ...
Achtsamkeitstest
Wir waren von all dieser Asynchronität so begeistert, dass wir, wie so oft, ein kleines Detail aus den Augen verloren haben. Werden diese Anfragen von unserem Skript gesendet? Sehen wir uns das
Netzwerk an :
GET https://www.example.com/0
GET https://www.example.com/1
GET https://www.example.com/2
Aber unsere Zahlen sind 1, 2, 3. Als ob eine Dekrementierung stattgefunden hätte. Warum so? Nur im Quellcode der Aufgabe gibt es hier ein weiteres Problem mit der Iteration:
let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(req); }
Hier wird ein
For-In verwendet , das anstelle von Array-Werten seine aufgezählten Eigenschaften umgeht: und dies sind die Indizes von Elementen von 0 bis 2. Die
Abruffunktion führt sie weiterhin zu Zeichenfolgen und wird trotz des Fehlens eines Schrägstrichs zuvor (dies ist kein
Pfad mehr) relativ aufgelöst URL der aktuellen Seite. Das Reparieren ist viel einfacher als das Bemerken. Zwei Optionen:
let fs = ['/1', '/2', '/3']; for (const req of fs) { yield fetch(req); } let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(fs[req]); }
Im ersten Fall haben wir dasselbe
for-of verwendet , um die Werte des Arrays zu durchlaufen, im zweiten Fall - Zugriff auf das Array-Element per Index.
Motivation
Wir haben 3 Lösungen in Betracht gezogen: 1) durch
Warten im
For-of- Body, 2) durch
For- Wait-Of und 3) durch unsere Polydatei (rekursive Funktion,
Pipe- Pipeline usw.). Es ist merkwürdig, dass diese Optionen die Konferenzteilnehmer ungefähr zu gleichen Teilen teilten und kein offensichtlicher Favorit bekannt wurde. In großen Projekten wird für solche realen Aufgaben normalerweise eine reaktive Bibliothek (z. B.
RxJS ) verwendet. Es lohnt sich jedoch, sich an die modernen nativen Merkmale einer asynchronen Sprache zu erinnern.
Etwa die Hälfte der Teilnehmer bemerkte keine Fehler in der Iteration der Ressourcenliste, was ebenfalls eine interessante Beobachtung ist. Wenn wir uns auf ein nicht triviales, aber offensichtliches Problem konzentrieren, können wir diese scheinbar Kleinigkeit leicht überspringen, aber mit möglichen schwerwiegenden Konsequenzen.
Problem 3 ~ Faktor 19
Wie oft in der Aufzeichnung der Nummer 2019! (Fakultät ab 2019) tritt die Zahl 19 auf? Stellen Sie zusammen mit der Antwort eine JavaScript-Lösung bereit.
Forschungsproblem
Das Problem liegt an der Oberfläche: Wir benötigen eine Aufzeichnung einer sehr großen Anzahl, um die Anzahl aller Vorkommen des Teilstrings „19“ darin zu finden. Als wir das Problem mit den
Zahlen lösten, stießen wir sehr schnell auf
Infinity (nach 170) und bekamen nichts. Darüber hinaus garantiert das Format zur Darstellung von Zahlen
float64 die Genauigkeit von nur 15-17 Zeichen, und wir müssen nicht nur eine vollständige, sondern auch eine genaue Aufzeichnung der Zahl erhalten. Daher besteht die Hauptschwierigkeit darin, die Struktur für die Akkumulation dieser großen Anzahl zu bestimmen.
Große ganze Zahlen
Wenn Sie den Neuerungen der Sprache folgen, wird die Aufgabe einfach gelöst: Anstelle der Typennummer
können Sie den neuen Typ
BigInt (Stufe 3) verwenden , mit dem Sie mit Zahlen mit beliebiger Genauigkeit arbeiten können. Mit der klassischen rekursiven Funktion zum Berechnen der Fakultät und zum Finden von Übereinstimmungen über
String.prototype.split sieht
die erste Lösung folgendermaßen aus:
const fn = n => n > 1n ? n * fn(n - 1n) : 1n; console.log(fn(2019n).toString().split('19').length - 1);
Zweitausend Funktionsaufrufe auf dem Stack können jedoch bereits
gefährlich sein . Selbst wenn Sie die Lösung für die
Tail-Rekursion verwenden , unterstützt die
Tail-Call-Optimierung nur Safari. Das faktorielle Problem ist hier angenehmer durch einen
Rechenzyklus oder
Array.prototype.reduce zu lösen:
console.log([...Array(2019)].reduce((p, _, i) => p * BigInt(i + 1), 1n).toString().match(/19/g).length);
Dies mag wie ein wahnsinnig langer Vorgang erscheinen. Aber dieser Eindruck täuscht. Wenn Sie schätzen, müssen wir nur etwas mehr als zweitausend Multiplikationen ausgeben. Bei i5-4590 3.30GHz in Chrom ist das Problem durchschnittlich in 4-5ms (!) Gelöst.
Eine weitere Option zum Suchen von Übereinstimmungen in einer Zeichenfolge mit dem Ergebnis einer Berechnung ist
String.prototype.match durch regulären Ausdruck mit dem globalen
Suchflag :
/ 19 / g .
Große Arithmetik
Aber was ist, wenn wir dieses
BigInt (und auch die
Bibliotheken ) noch nicht haben? In diesem Fall können Sie die lange Arithmetik selbst durchführen. Um das Problem zu lösen, reicht es aus, nur die Funktion des Multiplizierens von groß mit klein zu implementieren (wir multiplizieren mit Zahlen von 1 bis 2019). Wir können eine große Zahl und das Ergebnis der Multiplikation zum Beispiel in der Zeile halten:
const mult = (big, int) => { let res = '', carry = 0; for (let i = big.length - 1; i >= 0; i -= 1) { let prod = big[i] * int + carry; res = prod % 10 + res; carry = prod / 10 | 0; } return (carry || '') + res; } console.log([...Array(2019)].reduce((p, _, i) => mult(p, i + 1), '1').match(/19/g).length);
Hier multiplizieren wir einfach die Spalte in Bits vom Ende der Zeile bis zum Anfang, wie wir in der Schule unterrichtet wurden. Die Lösung benötigt aber schon ca. 170ms.
Wir können den Algorithmus etwas verbessern, indem wir mehr als eine Ziffer in einem Nummernsatz gleichzeitig verarbeiten. Dazu ändern wir die Funktion und gehen gleichzeitig zu den Arrays, um nicht jedes Mal mit den Zeilen herumzuspielen:
const mult = (big, int, digits = 1) => { let res = [], carry = 0, div = 10 ** digits; for (let i = big.length - 1; i >= 0 || carry; i -= 1) { let prod = (i < 0 ? 0 : big[i] * int) + carry; res.push(prod % div); carry = prod / div | 0; } return res.reverse(); }
Hier werden große Zahlen durch ein Array dargestellt, in dem jedes Element Informationen über
Ziffern Ziffern aus dem Nummernsatz unter Verwendung von
Zahlen speichert. Beispielsweise wird die Nummer 2016201720182019 mit
Ziffern = 3 wie folgt dargestellt:
'2|016|201|720|182|019' => [2,16,201,720,182,19]
Wenn Sie vor einem Join in eine Zeile konvertieren, müssen Sie sich die führenden Nullen merken. Die
Faktorfunktion gibt die berechnete Fakultät durch eine Zeichenfolge zurück, wobei die
Multifunktion mit der angegebenen Anzahl von verarbeiteten Ziffern gleichzeitig in der "massiven" Darstellung der Zahl bei der Berechnung verwendet wird:
const factor = (n, digits = 1) => [...Array(n)].reduce((p, _, i) => mult(p, i + 1, digits), [1]) .map(String) .map(el => '0'.repeat(digits - el.length) + el) .join('') .replace(/^0+/, ''); console.log(factor(2019, 3).match(/19/g).length);
Die "knielange" Implementierung durch Arrays erwies sich als schneller als durch Strings und berechnet mit
Ziffern = 1 die Antwort bereits im Durchschnitt in 90 ms,
Ziffern = 3 in 35 ms,
Ziffern = 6 in nur 20 ms.
Denken Sie jedoch daran, dass wir uns mit zunehmender Anzahl von Ziffern einer Situation nähern, in der das Multiplizieren von
Zahlen mit
Zahlen „unter der Haube“ außerhalb des sicheren
MAX_SAFE_INTEGER liegen kann . Hier können Sie damit spielen. Was ist der maximale Stellenwert, den wir uns für diese Aufgabe leisten können?
Die Ergebnisse sind bereits ziemlich bezeichnend,
BigInt ist wirklich ziemlich schnell:
Motivation
Es ist cool, dass 2/3 der Konferenzteilnehmer den neuen
BigInt- Typ in der Lösung verwendeten (jemand gab zu, dass dies die erste Erfahrung war). Das verbleibende Drittel der Lösungen enthielt eigene Implementierungen langer Arithmetik für Strings oder Arrays. Die meisten implementierten Funktionen multiplizierten große Zahlen mit großen, während es für eine Lösung ausreichte, mit einer "kleinen"
Zahl zu multiplizieren und etwas weniger Zeit zu verbringen. Okay Aufgabe, verwenden Sie
BigInt bereits in Ihren Projekten?
Danksagung
Diese beiden Konferenztage waren sehr voller Diskussionen und des Lernens von etwas Neuem. Ich möchte dem Programmkomitee für die nächste unvergessliche Konferenz und allen Teilnehmern für ihre einzigartige Vernetzung und gute Laune danken.