L'histoire d'un problème: le plus court mémo JavaScript

C'était le soir, à la veille de la conférence annuelle HolyJS à Saint-Pétersbourg. Notre entreprise est sponsor depuis plusieurs années: elle a donc son propre stand avec des intérêts intéressants pour l'esprit curieux des développeurs attentionnés. Quand le plat principal était prêt et que toutes les tâches étaient revues et complétées par des avocats, j'ai décidé de jeter un peu plus de nourriture intellectuelle à mes collègues la nuit:

Écrivez un mémo - une fonction de décoration qui enregistre les résultats de l'exécution d'une fonction encapsulée pour éviter des calculs répétés. Vous n'avez que 50 caractères.

Le langage est, bien sûr, JavaScript . La tâche elle-même est un classique, mais la limite de 50 caractères s'est transformée en un véritable défi.

Dans les pauses du premier jour de la conférence, nous avons discuté des options pour atteindre l'objectif, en réduisant progressivement la réponse. Tout le battage médiatique a été couronné par l'idée de partager la tâche avec tous les participants de la conférence, et le deuxième jour, nous avons visualisé la tâche (voir l'annexe) et commencé à distribuer des formulaires à ceux qui le voulaient. En conséquence, nous avons obtenu environ 40 solutions et sommes une fois de plus convaincus de l'extraordinaire communauté de développeurs js, mais le record de Dmitry Kataev (SEMrush) de 53 caractères est resté. Voyons ça!

Mise en œuvre habituelle

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]; } } 

Résultat: ~ 190 caractères

• memoize - notre memoizer
• f - fonction décorée et enveloppée
• ret - fonction résultante

Pour obtenir la réponse - la taille de la fonction - nous utilisons:

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

Lors de l'évaluation de la taille d'une fonction, nous prêtons attention à son corps et à une liste de paramètres. Si la fonction est anonyme, la déclaration n'est pas prise en compte.

Des tests simples pour tester la santé après un abus:

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

Ensuite, le résultat de chaque implémentation sera marqué par le résultat du test.

Mise en œuvre nette

Tout d'abord, je veux me débarrasser de la déclaration de fonction en faveur de la fonction flèche, car nous ne sommes pas intéressés par ce contexte, nous ne faisons pas appel aux arguments, et en tant que constructeur, nous n'avons pas l'intention d'appeler via new . Dans le même temps, nous réduirons les noms des variables locales utilisées:

 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]; } } 

Résultat: 154 , tests réussis

Ensuite, nous pouvons effectuer une opération similaire avec la fonction résultante, mais nous avons besoin d' arguments . Ici, l' opérateur d'étalement vient à la rescousse, nous permettant de remplacer l'objet itérable passé des arguments par la variable tableau a . De plus, nous ne passerons plus ce contexte à la fonction en cours de décoration: si nécessaire, Function.prototype.bind ou notre polyfil vous aidera.

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

Résultat: 127 , tests réussis

Passons maintenant au corps de la fonction résultante. Évidemment, trouver la clé dans le cache et renvoyer la valeur est fastidieux. Essayons de réduire comment:

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

Résultat: 101 , les tests 3 et 4 sont tombés

Ici, nous abandonnons la méthode hasOwnProperty . Nous pouvons nous le permettre, car le résultat de la sérialisation du tableau d'arguments via JSON.stringify sera toujours "[...]" et il est peu probable qu'une telle propriété apparaisse dans le cache du prototype ( Object ).

Ensuite, nous utilisons la fonction de l'opérateur OR «logique» pour renvoyer la première expression si elle peut être convertie en vrai , ou sinon, la seconde avec le calcul de fonction précédent.

Et ici, nous sommes tombés aux tests 3 et 4. Cela s'est produit parce que la fonction décorée console.log ne renvoie pas de valeur: le résultat ne sera pas défini . Nous mettons cela dans le cache, et lorsque nous essayons de vérifier la fonctionnalité disjoncteur lorsque nous l'appelons à nouveau, nous obtenons implicitement un affichage faux dans le premier opérande et, en conséquence, nous entrons dans le second, ce qui conduit à l'appel de fonction. Cet effet se produira pour tous les résultats réduits à faux : 0, "", null, NaN , etc.

Au lieu de l' instruction OR et if, nous pouvons utiliser un opérateur ternaire conditionnel:

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

Résultat: 118 , tests réussis

Réduit très légèrement. Mais que se passe-t-il si vous utilisez Map comme stockage au lieu d'un simple objet? Il existe également une méthode courte:

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

Résultat: 121 , tests réussis

La réduction a complètement échoué. Mais jeter immédiatement Map n'en vaut pas la peine. Cette implémentation du stockage de valeurs-clés vous permet d'utiliser des objets comme clé. Et cela signifie, devrions-nous abandonner JSON.stringify ?

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

Résultat: 83 , les tests 3 et 4 sont tombés

Cela semble très prometteur! Cependant, les tests 3 et 4 ont recommencé à tomber, car la comparaison des clés dans l'objet Map est implémentée à l'aide de l'algorithme SameValueZero . Si vous omettez les détails avec NaN, -0 et 0 , cela fonctionne de manière similaire à l'opérateur de comparaison strict ( === ). Et nous avons un nouveau tableau d'arguments (et donc un objet) pour chaque appel de la fonction encapsulée, même avec les mêmes valeurs. La comparaison a lieu en fonction de la référence de l'objet et donc la méthode Map.prototype.has ne trouvera jamais rien.

Ainsi, l'utilisation de Map ne nous a pas réduit hasOwnProperty ou JSON.stringify .

En opérateur vient à la rescousse, qui vérifie la présence d'une propriété dans un objet ou dans la chaîne de ses prototypes. Pourquoi nous ne pouvons pas avoir peur de la recherche dans les prototypes a été expliqué ci-dessus.

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

Résultat: 105 , tests réussis

Le corps du memoizer et de la fonction résultante se compose de deux expressions avec la nécessité de déclarer et d'initialiser une variable locale avant la logique dans l' instruction de retour . Est-il possible de réduire le corps de la fonction flèche à une seule expression ici? Bien sûr, en utilisant le modèle IIFE ( Immediateely Invoked Function Expression ):

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

Résultat: 82 , tests réussis

Il est temps de se débarrasser des espaces supplémentaires:

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

Résultat: 68 , tests réussis

De toute évidence, le goulot d'étranglement est maintenant la longue méthode JSON.stringify , qui sérialise récursivement l'objet en une chaîne JSON, que nous utilisons comme clé. En fait, nous n'avons pas besoin d'une fonction de sérialisation, mais d'une fonction de hachage avec laquelle nous pourrions vérifier l'égalité des objets, car cela fonctionne dans d'autres langages. Mais, malheureusement, il n'y a pas de solution native en JavaScript, et le polyphile auto-écrit hashCode dans le prototype Object est clairement hors de portée.

Hmm, pourquoi devons-nous même nous sérialiser? Lors de l'ajout d'un élément à un objet par clé, sa toString sera appelée implicitement. Comme nous avons refusé d'utiliser l'objet arguments itérables en faveur du tableau via l' opérateur de propagation , l'appel à String ne proviendra pas de Object.prototype , mais de Array.prototype , dans lequel il est redéfini et séparé par des virgules de ses éléments. Ainsi, pour un ensemble d'arguments différent, nous obtenons une clé différente.

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

Résultat: 44 , le test 6 est tombé

Le test 6 commence tout juste à tomber. Il semble que la valeur de retour soit le résultat d'un appel de fonction précédent dans le test 5. Pourquoi cela se produit-il? Oui, nous avons ignoré l'appel à String pour l'objet arguments , mais nous n'avons pas pris en compte le fait qu'un argument peut également être un objet complexe, appelant toString à partir duquel nous obtenons [l'objet objet] préféré de tous. Cela signifie que les arguments {x: 1} et {x: 2} utiliseront la même clé dans le hachage.

Le btoa utilisé pour convertir en base64 semblait être un bon concurrent pour la fonction de sérialisation. Mais il mène d'abord à la chaîne, donc aucune chance. Nous avons pensé dans le sens de générer un URI et de former un ArrayBuffer , toutes les fonctions pour obtenir un hachage ou une valeur sérialisée. Mais ils sont restés en place.

Soit dit en passant, JSON.stringify a ses propres particularités: Infinity, NaN, undefined, Symbol sera converti en null . Il en va de même pour les fonctions. Si possible, un appel implicite à JSON à partir de l'objet se produit, et Map et Set seront représentés par des éléments simplement énumérés. C'est compréhensible, étant donné le format final: JSON.

Et ensuite?

Modification toxique

Nous aimons certainement tous les fonctions pures, mais face au problème, une telle exigence n'en vaut pas la peine. Et cela signifie qu'il est temps d'ajouter une pincée d'effets secondaires.

Tout d'abord, pourquoi ne pas lancer le cache comme suit:

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

Résultat: 66 , tests réussis

Ici, nous utilisons le paramètre par défaut dans la fonction flèche. Bien sûr, nous donnons au client la possibilité de définir son cache, alors quoi? Mais nous avons réduit 2 caractères.

Sinon, comment puis-je lancer un cache pour une fonction à décorer? La bonne réponse: pourquoi devons-nous l'initier? Pourquoi ne pas utiliser quelque chose de prêt dans le contexte d'une fonction à encapsuler. Mais que faire si la fonction elle-même? Nous savons tous que les fonctions en JavaScript sont également des objets:

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

Résultat: 59 , tests réussis

Ici, JSON.stringify nous protégera contre l'intersection avec d'autres propriétés et méthodes de l'objet (fonction), en enveloppant les arguments dans "[...]".

En ce moment même, le schéma IIFE précédemment appliqué ne se justifie plus. Mais il est urgent de conserver une seule expression pour la fonction flèche pour éviter une déclaration de retour :

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

Résultat: 57 , tests réussis

Puisque nous n'utilisons pas l' instruction de bloc dans la fonction flèche, nous ne pouvons pas déclarer une variable ( var ou let ), mais nous pouvons utiliser le contexte global - effet secondaire! Ici, le conflit a déjà quelques chances d’être.

En utilisant l' opérateur virgule, nous concaténons deux expressions en une seule: les opérandes sont évalués de gauche à droite, et le résultat est la valeur de cette dernière.

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

Résultat: 54 , tests réussis

Ainsi, en réorganisant un seul support, nous nous sommes débarrassés de trois caractères à la fois. L'opérateur de regroupement lors du calcul de la clé nous a permis de combiner les deux opérandes de l'expression en une seule expression, et le crochet de fermeture a supprimé l'espace avant l' opérateur in .

Et enfin:

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

Résultat: 53 , tests réussis

Pourquoi ne pas calculer la clé lors de l'accès à la valeur. Et puis - le même opérateur ternaire et affectation. Total: 53 caractères!

Est-il possible de supprimer les 3 caractères restants?

Compréhension

Pourquoi tout ça? Cette tâche simple et la chaîne de conversions subséquente de l'habituel à l'indécent démontrent un nombre considérable de fonctionnalités du langage JavaScript. Dans nos discussions, nous avons abordé des sujets tels que:

• Expression de la fonction flèche
• Portée lexicale et IIFE
• Objet arguments de type tableau
• Spread, virgule ou opérateurs
• Opérateur de comparaison strict
• JSON.stringify & toString
• Dans operator & hasOwnProperty
• Opérateur de regroupement et instruction de bloc
• Objet de carte
• et autre chose

De telles histoires sont une bonne raison de s'immerger dans l'étude des spécificités d'une langue, de mieux la comprendre (ou vice versa). Et bien sûr, juste pour le plaisir!

App

Dans ses aventures, Rick doit souvent calibrer son arme portique. La procédure prend du temps, mais l'entrée est souvent répétée. Le scientifique tente de mémoriser les résultats déjà obtenus une fois afin de ne pas faire de calculs à plusieurs reprises, mais l'alcoolisme et la sénilité sénile affectent fortement sa mémoire. Il a demandé à Morty d'améliorer le module des paramètres du pistolet, en ajoutant une fonction de mémorisation. Cette fonction doit enregistrer les résultats de la fonction en cours de décoration pour éviter des calculs répétés. Seul Morty a peur des fonctions longues. Aidez-le à résoudre le problème de la manière la plus compacte possible . La fonction en cours de décoration peut prendre des entiers, des chaînes, des booléens et des objets comme arguments.