Javascript Girl
  1. Javascript Girl
  3. Comment éviter les résultats intermédiaires lors de l'exécution d'itérations de tableau?
Intereting Posts
Méthode différée jQuery et ajax beforeSend () Comment combiner les éléments de triage jquery ui draggable avec un code à échelle personnalisé? Existe-t-il une limite de délai maximum pour window.setInterval Comment fournir des avertissements lors de la validation dans ASP.NET MVC? Javascript: simulez des événements clés sur Chrome 53 Ouvrez plusieurs onglets dans le même navigateur par JavaScript Existe-t-il une raison pour utiliser un XMLHttpRequest synchrone? Angulaire, limite et suivi par indice de $ Vérifiez le support du navigateur pour le type Mime spécifique? Trouvez l'objet JSON en utilisant plusieurs paires de clés / valeurs, puis mettez à jour l'autre attribut de l'objet Comment intégrer la fonctionnalité dans un courrier électronique HTML? Par programme, allumez ou obscurci une couleur hexagonale (ou rgb, et mélangez des couleurs) ToLocaleString () n'est-il pas pris en charge dans tous les navigateurs? Toile HTML5 – drawImage ne dessine pas toujours l'image Comment déclencher le rappel après l'état de mise à jour dans Redux?

Comment éviter les résultats intermédiaires lors de l'exécution d'itérations de tableau?

Lorsque vous travaillez avec des tableaux, des représentations intermédiaires sont nécessaires régulièrement, en particulier dans le cadre de la programmation fonctionnelle, dans laquelle les données sont souvent traitées comme immuables: 

const square = x => x * x; const odd = x => (x & 1) === 1; let xs = [1,2,3,4,5,6,7,8,9]; // unnecessary intermediate array: xs.map(square).filter(odd); // [1,4,9,16,25,36,49,64,81] => [1,9,25,49,81] // even worse: xs.map(square).filter(odd).slice(0, 2); // [1,9]

Comment puis-je éviter ce comportement dans JavaScript / Ecmascript 2015 pour obtenir des algorithmes itératifs plus efficaces?

Les transducteurs sont un moyen possible d'éviter les résultats intermédiaires dans les algorithmes itératifs. Afin de mieux les comprendre, vous devez vous rendre compte que les transducteurs eux-mêmes sont plutôt inutiles: 

 // map transducer let map = tf => rf => acc => x => rf(acc)(tf(x));

Pourquoi devrions-nous passer une fonction de réduction à la map pour chaque invocation lorsque la fonction requise est toujours la même, concat ?

La réponse à cette question est située dans la définition officielle du transducteur:

Les transducteurs sont des transformations algorithmiques composables .

Le transducteur développe son pouvoir expressif uniquement en conjonction avec la composition de la fonction: 

 const comp = f => g => x => f(g(x)); let xf = comp(filter(gt3))(map(inc)); foldL(xf(append))([])(xs);

comp est passé un nombre arbitraire de transducteurs ( filter et map ) et une seule fonction de réduction ( append ) comme argument final. À partir de ce comp construit une séquence de transformation qui ne nécessite pas de tableaux intermédiaires. Chaque élément de tableau passe à travers la séquence entière avant que l'élément suivant ne soit en ligne.

À ce stade, la définition du transducteur de map est compréhensible: la composabilité nécessite la signature de fonctions correspondantes.

Notez que l'ordre d'évaluation de la pile de transducteurs va de gauche à droite et est donc opposé à l'ordre normal de la composition de la fonction.

Une propriété importante des transducteurs est leur capacité à sortir tôt des processus itératifs. Dans la mise en œuvre choisie, ce comportement est réalisé en implémentant à la fois les transducteurs et le foldL dans le style de passage continu. Une alternative serait une évaluation paresseuse. Voici la mise en œuvre de la CPS: 

 const foldL = rf => acc => xs => { return xs.length ? rf(acc)(xs[0])(acc_ => foldL(rf)(acc_)(xs.slice(1))) : acc; }; // transducers const map = tf => rf => acc => x => cont => rf(acc)(tf(x))(cont); const filter = pred => rf => acc => x => cont => pred(x) ? rf(acc)(x)(cont) : cont(acc); const takeN = n => rf => acc => x => cont => acc.length < n - 1 ? rf(acc)(x)(cont) : rf(acc)(x)(id); // reducer const append = xs => ys => xs.concat(ys); // transformers const inc = x => ++x; const gt3 = x => x > 3; const comp = f => g => x => f(g(x)); const liftC2 = f => x => y => cont => cont(f(x)(y)); const id = x => x; let xs = [1,3,5,7,9,11]; let xf = comp(filter(gt3))(map(inc)); foldL(xf(liftC2(append)))([])(xs); // [6,8,10,12] xf = comp(comp(filter(gt3))(map(inc)))(takeN(2)); foldL(xf(liftC2(append)))([])(xs); // [6,8]

Veuillez noter que cette implémentation est plus une preuve de concept et aucune solution intégrale. Les avantages évidents des transducteurs sont les suivants:

  • Pas de représentation intermédiaire
  • Solution purement fonctionnelle et concise
  • Générique (travaillez avec un agrégat / collection, pas seulement des tableaux)
  • Réutilisabilité de code extraordinaire (les réducteurs / transformateurs sont des fonctions communes avec leurs signatures habituelles)

Théoriquement, CPS est aussi rapide que les boucles impératives, au moins dans Ecmascript 2015, puisque tous les appels de queue ont le même point de retour et peuvent donc partager le même cadre de pile (TCO).

Il est considéré comme controversé si cette approche est assez idiomatique pour une solution Javascript. Je préfère ce style fonctionnel. Cependant, les bibliothèques transductrices les plus courantes sont mises en œuvre dans le style objet et devraient être plus familières aux développeurs OO.