Il s'agit de la deuxième partie de l'analyse des tâches de notre stand lors de la conférence
HolyJS , tenue à Saint-Pétersbourg du 24 au 25 mai. Pour plus de contexte, il est recommandé de lire d'
abord la
première partie de ce document. Et si l'
expression du compte à
rebours est déjà terminée, bienvenue à l'étape suivante.
Contrairement à l'obscurantisme dans la première tâche, les deux suivantes ont déjà une idée de l'applicabilité des applications normales dans la vie. JavaScript se développe encore assez rapidement et les solutions aux problèmes suggérés mettent en évidence certaines des nouvelles fonctionnalités du langage.
Tâche 2 ~ effectuée par les uns
Il a été supposé que le code s'exécuterait et imprimerait les réponses à la console en réponse à trois demandes, puis «terminé». Mais quelque chose s'est mal passé ... Corrigez la 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'); })();
Problème de recherche
Qu'avons-nous ici? Il s'agit d'un objet
iter itérable qui a un symbole
Symbol.iterator bien connu défini par
une fonction de générateur . Un tableau
fs est déclaré dans le corps de la fonction, dont les éléments tombent dans la fonction
fetch à leur tour pour envoyer une requête et le résultat de chaque appel de fonction est retourné via
yield . Quelles demandes la fonction d'
extraction envoie-t-elle? Tous les éléments du tableau
fs sont des chemins relatifs vers les ressources avec les nombres 1, 2 et 3, respectivement. Ainsi, l'URL complète sera obtenue en concaténant
location.origin avec le numéro suivant, par exemple:
GET https://www.example.com/1
Ensuite, nous voulons itérer l'objet
iter à travers
for-of , afin d'exécuter chaque demande tour à tour avec la sortie du résultat, après tout - imprimer «done». Mais ça ne marche pas! Le problème est que l'
extraction est une chose asynchrone et renvoie une promesse, pas une réponse. Par conséquent, dans la console, nous verrons quelque chose comme ceci:
Promise {pending}
Promise {pending}
Promise {pending}
done
En fait, la tâche se résume à la réalisation de ces mêmes promesses.
Nous avons asynchrone / attend
La première pensée peut être de jouer avec
Promise.all : donnez-lui notre objet
itérable ,
puis la sortie vers la console est «terminée». Mais il ne nous fournira pas l'exécution séquentielle des demandes (comme l'exige la condition), mais les enverra simplement toutes et attendra la dernière réponse avant la résolution générale.
La solution la plus simple ici serait d'
attendre dans le
for-of body d'attendre la résolution de la prochaine promesse avant de sortir sur la console:
for (const res of iter) { console.log(await res); }
Pour
attendre que cela fonctionne et que "done" soit affiché à la fin, vous devez rendre la fonction principale asynchrone via
async :
;(async function() { let iter = { }; for (const res of iter) { console.log(await res); } console.log('done'); })();
Dans ce cas, le problème a déjà été résolu (presque):
GET 1st
Response 1st
GET 2nd
Response 2nd
GET 3rd
Response 3rd
done
Itérateur et générateur asynchrones
Nous laisserons la fonction principale asynchrone, mais pour
wait il y a une place plus élégante dans cette tâche que dans le corps
for-of : c'est l'utilisation de l'itération asynchrone via
for-wait-of , à savoir:
for await (const res of iter) { console.log(res); }
Tout fonctionnera! Mais si vous passez à la description de
cette proposition sur l'itération asynchrone, voici ce qui est intéressant:
Nous introduisons une variation de l'instruction d'itération for-of qui itère sur les objets itérables asynchrones. Les instructions for-of asynchrones ne sont autorisées que dans les fonctions asynchrones et les fonctions du générateur asynchrone
Autrement dit, notre objet doit être non seulement
itérable , mais
«asyncIterable» via le nouveau symbole
bien connu Symbol.asyncIterator et, dans notre cas, déjà une fonction de générateur asynchrone:
let iter = { [Symbol.asyncIterator]: async function* iterf() { let fs = ['/1', '/2', '/3']; for (const req in fs) { yield await fetch(req); } } };
Comment cela fonctionne-t-il alors sur un itérateur et un générateur réguliers? Oui, juste implicitement, comme beaucoup plus dans cette langue. Cette
attente est délicate: si l'objet est seulement
itérable , alors pendant l'itération asynchrone, il "convertit" l'objet en
asyncIterable en
encapsulant les éléments (si nécessaire) dans
Promise avec l'attente de résolution.
Décrit plus en détail
dans l'article Axel Rauschmayer .
Probablement, grâce à
Symbol.asyncIterator, ce sera toujours plus correct, car nous avons explicitement créé l'objet
asyncIterable pour notre itération asynchrone via
for-wait-of , tout en laissant la possibilité de compléter l'objet avec un itérateur régulier pour
for of , si nécessaire. Si vous voulez lire quelque chose d'utile et suffisant dans un article sur les itérations asynchrones en JavaScript, alors le
voici !
Le
for-of asynchrone est encore partiellement en projet, mais il est déjà pris en charge par les navigateurs modernes (sauf Edge) et Node.js à partir de 10.x. Si cela dérange quelqu'un, vous pouvez toujours écrire votre propre petit polyphile pour une chaîne de promesses, par exemple, pour un objet
itérable :
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'); })();
De cette manière et de ces façons, nous avons compris l'envoi des demandes et le traitement des réponses à leur tour. Mais dans ce problème, il y a un autre problème petit mais ennuyeux ...
Test de pleine conscience
Nous étions tellement emportés par tout cet asynchronisme que, comme cela arrive souvent, nous avons perdu de vue un petit détail. Ces demandes sont-elles envoyées par notre script? Voyons le
réseau :
GET https://www.example.com/0
GET https://www.example.com/1
GET https://www.example.com/2
Mais nos nombres sont 1, 2, 3. Comme si une décrémentation s'était produite. Pourquoi Juste dans le code source de la tâche, il y a un autre problème avec l'itération, ici:
let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(req); }
Ici, un
for-in est utilisé , qui au lieu des valeurs de tableau contourne ses propriétés énumérées: et ce sont les indices des éléments de 0 à 2. La fonction
fetch les mène toujours à des chaînes et, malgré l'absence de barre oblique avant (ce n'est plus un
chemin ), elle résout relativement URL de la page actuelle. Il est beaucoup plus facile de réparer que de remarquer. Deux options:
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]); }
Dans le premier, nous avons utilisé le même
for-of pour parcourir les valeurs du tableau, dans le second - accès à l'élément du tableau par index.
La motivation
Nous avons envisagé 3 solutions: 1) par
attente dans le corps
de for , 2) par
attente de, et 3) par le biais de notre polyfichier (fonction récursive,
pipeline de canalisation, etc.). Il est curieux que ces options aient divisé les participants à la conférence à peu près également et aucun favori évident n'a été révélé. Dans les grands projets, pour de telles tâches réelles, une bibliothèque réactive (par exemple,
RxJS ) est généralement utilisée, mais il convient de se rappeler des fonctionnalités natives modernes d'un langage à caractère asynchrone.
Environ la moitié des participants n'ont pas remarqué d'erreurs dans l'itération de la liste des ressources, ce qui est également une observation intéressante. En nous concentrant sur un problème non trivial mais évident, nous pouvons facilement ignorer cette apparence insignifiante, mais avec de graves conséquences potentielles.
Problème 3 ~ Facteur 19
Combien de fois dans le record du nombre 2019! (factorielle à partir de 2019) le nombre 19 se produit-il? Avec la réponse, fournissez une solution JavaScript.
Problème de recherche
Le problème est en surface: nous avons besoin d'un enregistrement d'un très grand nombre pour y trouver le nombre de toutes les occurrences de la sous-chaîne «19». Résolvant le problème sur les
nombres , nous avons très rapidement rencontré
Infinity (après 170) et n'avons rien obtenu. De plus, le format de représentation des nombres
float64 garantit l'exactitude de seulement 15-17 caractères, et nous devons obtenir non seulement un enregistrement complet, mais aussi précis du nombre. La principale difficulté est donc de déterminer la structure d'accumulation de ce grand nombre.
Grands entiers
Si vous suivez les innovations du langage, la tâche est résolue simplement: au lieu du
numéro de type
, vous pouvez utiliser le nouveau type
BigInt (étape 3) , qui vous permet de travailler avec des nombres de précision arbitraires. Avec la fonction récursive classique pour le calcul factoriel et la recherche de correspondances via
String.prototype.split, la première solution ressemble à ceci:
const fn = n => n > 1n ? n * fn(n - 1n) : 1n; console.log(fn(2019n).toString().split('19').length - 1);
Cependant, deux mille appels de fonction sur la pile peuvent déjà
être dangereux . Même si vous apportez la solution à la
récursivité de la queue , l'
optimisation des appels de queue ne prend toujours en charge que Safari. Le problème factoriel est ici plus agréable à résoudre à travers un cycle arithmétique ou
Array.prototype.reduce :
console.log([...Array(2019)].reduce((p, _, i) => p * BigInt(i + 1), 1n).toString().match(/19/g).length);
Cela peut sembler une procédure incroyablement longue. Mais cette impression est trompeuse. Si vous estimez, nous avons juste besoin de dépenser un peu plus de deux mille multiplications. À i5-4590 3,30 GHz en chrome, le problème est résolu en moyenne en 4-5 ms (!).
Une autre option pour rechercher des correspondances dans une chaîne avec le résultat d'un calcul est
String.prototype.match par expression régulière avec l'indicateur de recherche globale:
/ 19 / g .
Grande arithmétique
Mais que se passe-t-il si nous n'avons pas encore ce
BigInt (et les
bibliothèques aussi)? Dans ce cas, vous pouvez faire vous-même la longue arithmétique. Pour résoudre le problème, il nous suffit d'implémenter uniquement la fonction de multiplier grand par petit (nous multiplions par des nombres de 1 à 2019). Nous pouvons contenir un grand nombre et le résultat de la multiplication, par exemple, dans la ligne:
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);
Ici, nous multiplions simplement la colonne en bits de la fin de la ligne au début, comme on nous l'a enseigné à l'école. Mais la solution nécessite déjà environ 170 ms.
Nous pouvons quelque peu améliorer l'algorithme en traitant plus d'un chiffre dans un enregistrement numérique à la fois. Pour ce faire, nous modifions la fonction et en même temps allons dans les tableaux, afin de ne pas déranger les lignes à chaque fois:
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(); }
Ici, les grands nombres sont représentés par un tableau, dont chaque élément stocke des informations sur les
chiffres chiffres de l'enregistrement numérique, à l'aide de
nombre . Par exemple, le nombre 2016201720182019 avec
chiffres = 3 sera représenté comme:
'2|016|201|720|182|019' => [2,16,201,720,182,19]
Lors de la conversion en ligne avant une jointure, vous devez vous souvenir des zéros non significatifs. La fonction
facteur renvoie la factorielle calculée par une chaîne, en utilisant la fonction
mult avec le nombre spécifié de chiffres traités à la fois dans la représentation "massive" du nombre lors du calcul:
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);
L'implémentation «à longueur de genou» via des tableaux s'est avérée plus rapide que via des chaînes, et avec des
chiffres = 1, il calcule la réponse déjà en moyenne en 90 ms,
chiffres = 3 en 35 ms,
chiffres = 6 en seulement 20 ms. Cependant, rappelez-vous qu'en augmentant le nombre de chiffres, nous approchons d'une situation où la multiplication de
nombre par
nombre "sous le capot" peut être en dehors du coffre-fort
MAX_SAFE_INTEGER . Vous pouvez jouer avec
ici . Quelle est la valeur maximale de
chiffres que nous pouvons nous permettre pour cette tâche?
Les résultats sont déjà assez indicatifs,
BigInt est vraiment assez rapide:
La motivation
C'est cool que 2/3 des participants à la conférence
aient utilisé le nouveau type
BigInt dans la solution (quelqu'un a admis que c'était la première expérience). Le tiers restant des solutions contenait leurs propres implémentations d'arithmétique longue sur des chaînes ou des tableaux. La plupart des fonctions implémentées multipliaient de grands nombres par de grandes, alors que pour une solution, il suffisait de se multiplier par un "petit"
nombre et de passer un peu moins de temps. D'accord, utilisez-vous déjà
BigInt dans vos projets?
Remerciements
Ces deux jours de conférence ont été très chargés de discussions et d'apprentissage de quelque chose de nouveau. Je remercie le comité de programme pour la prochaine conférence inoubliable et tous les participants pour leur réseautage unique et leur bonne humeur.