Principale différence entre map et reduce

Question

J'ai utilisé les deux méthodes, mais je suis assez confus quant à leur utilisation.

Est-ce que quelque chose qui map peut faire mais reduce et vice versa ?

Note : Je sais comment utiliser les deux méthodes, mais je m'interroge sur les principales différences entre ces méthodes et sur le moment où elles doivent être utilisées.

Answer 1

Source

Les deux map y reduce ont comme entrée le tableau et une fonction que vous définissez. Elles sont en quelque sorte complémentaires : map ne peut pas renvoyer un seul élément pour un tableau composé de plusieurs éléments, tandis que reduce renverra toujours l'accumulateur que vous avez modifié.

map

Utilisation map vous itérez les éléments, et pour chaque élément vous renvoyez l'élément que vous souhaitez.

Par exemple, si vous disposez d'un tableau de nombres et que vous souhaitez obtenir leurs carrés, vous pouvez procéder comme suit :

// A function which calculates the square
const square = x => x * x

// Use `map` to get the square of each number
console.log([1, 2, 3, 4, 5].map(square))

reduce

En utilisant un tableau comme entrée, vous pouvez obtenir un seul élément (disons un objet, un nombre ou un autre tableau) sur la base de la fonction de rappel (le premier argument) qui obtient l'élément accumulator y current_element paramètres :

const numbers = [1, 2, 3, 4, 5]

// Calculate the sum
console.log(numbers.reduce(function (acc, current) {
  return acc + current
}, 0)) // < Start with 0

// Calculate the product
console.log(numbers.reduce(function (acc, current) {
  return acc * current
}, 1)) // < Start with 1

---

Lequel choisir quand on peut faire la même chose avec les deux ? Essayez d'imaginer à quoi ressemble le code. Pour l'exemple fourni, vous pouvez calculer le tableau des carrés comme vous l'avez mentionné, en utilisant reduce :

// Using reduce
[1, 2, 3, 4, 5].reduce(function (acc, current) {
    acc.push(current*current);
    return acc;
 }, [])

 // Using map
 [1, 2, 3, 4, 5].map(x => x * x)

Si l'on examine ces documents, il est évident que la deuxième solution est plus efficace et plus courte. En général, on choisit la solution la plus propre, qui dans ce cas est map . Bien sûr, vous pouvez le faire avec reduce Mais en résumé, réfléchissez à ce qui serait le plus court et ce qui serait éventuellement le mieux.

Answer 2

Je pense que cette image vous répondra sur la différence entre ces HOC

Answer 3

En règle générale, le terme "carte" désigne la conversion d'une série d'entrées en une série de données. longueur égale série de sorties, tandis que "réduire" signifie convertir une série d'entrées en une série de sorties, tandis que "réduire" signifie convertir une série d'entrées en une série de sorties. plus petit le nombre de sorties.

Le terme "map-reduce" est généralement interprété comme signifiant "transformer, éventuellement en parallèle, combiner en série".

Lorsque vous "mappez", vous écrivez une fonction qui transforme x con f(x) en une nouvelle valeur x1 . Lorsque vous "réduisez", vous écrivez une fonction g(y) qui prend un tableau y et émet un tableau y1 . Ils travaillent sur différents types de données et produisent des résultats différents.

Answer 4

Je pense que cette question est très pertinente et je ne peux pas ne pas être d'accord avec les réponses, mais j'ai l'impression que nous passons complètement à côté de l'essentiel.

Penser à map y reduce de manière plus abstraite peut nous fournir BEAUCOUP d'informations très utiles.

Cette réponse est divisée en trois parties :

• Définir et décider entre map et reduce (7 minutes)
• Utiliser la réduction de manière intentionnelle (8 minutes)
• Faire le lien entre map et reduce avec les transducteurs (5 minutes)

cartographier ou réduire

Caractéristiques communes

map y reduce sont mis en œuvre de manière significative et cohérente sur un large éventail d'objets qui ne sont pas nécessairement des collections.

Ils renvoient une valeur utile à l'algorithme environnant et ne se préoccupent que de cette valeur.

Leur rôle principal est de transmettre l'intention concernant la transformation ou la préservation de la structure.

Structure

Par "structure", j'entends un ensemble de propriétés conceptuelles qui caractérisent des objets abstraits, tels qu'une liste non ordonnée ou une matrice 2D, et leur concrétisation dans des structures de données.

Notez qu'il peut y avoir un décalage entre les deux :

• une liste non ordonnée peut être stockée sous la forme d'un tableau, dont le concept d'ordre est porté par des clés indexées ;
• une matrice 2D peut être stockée sous la forme d'un TypedArray, qui ne possède pas le concept de dimension (ou d'imbrication).

carte

map est une transformation stricte préservant la structure.

Il est utile de l'appliquer à d'autres types d'objets pour en saisir la valeur sémantique :

class A {
    constructor (value) {
        this.value = value
    }

    map (f) { 
        return new A(f(this.value))
    }
}

new A(5).map(x => x * 2); // A { value: 10 }

Objets mettant en œuvre map peuvent avoir toutes sortes de comportements, mais elles renvoient toujours le même type d'objet que celui avec lequel vous avez commencé, tout en transformant les valeurs à l'aide de la fonction de rappel fournie.

Array.map renvoie un tableau de la même longueur et du même ordre que l'original.

Sur l'arité du callback

Parce qu'il préserve la structure, map est considérée comme une opération sûre, mais tous les rappels ne sont pas égaux.

Avec un rappel unaire : map(x => f(x)) chaque valeur du tableau est totalement indifférente à la présence d'autres valeurs.

En revanche, l'utilisation des deux autres paramètres introduit un couplage qui peut ne pas être fidèle à la structure originale.

---

Imaginez que vous supprimiez ou réordonniez le deuxième élément des tableaux ci-dessous : le faire avant ou après la carte ne donnerait pas le même résultat.

Couplage avec la taille du tableau :

[6, 3, 12].map((x, _, a) => x/a.length);
// [2, 1, 4]

Couplage avec la commande :

['foo', 'bar', 'baz'].map((x, i) => [i, x]);
// [[0, 'foo'], [1, 'bar'], [2, 'baz']]

Couplage avec une valeur spécifique :

[1, 5, 3].map((x, _, a) => x/Math.max(...a));
//[ 0.2, 1, 0.6]

Couplage avec les voisins :

const smooth = (x, i, a) => {
    const prev = a[i - 1] ?? x;
    const next = a[i + 1] ?? x;
    const average = (prev + x + next) / 3;
    return Math.round((x + average) / 2);
};

[1, 10, 50, 35, 40, 1].map(smoothh);
// [ 3, 15, 41, 38, 33, 8 ]

---

Je recommande d'indiquer explicitement sur le site d'appel si ces paramètres sont utilisés ou non.

const transfrom = (x, i) => x * i;

 array.map(transfrom);
 array.map((x, i) => transfrom(x, i));

Cela présente d'autres avantages lorsque vous utilisez des fonctions variadiques avec map .

 ["1", "2", "3"].map(parseInt);
   // [1, NaN, NaN]
 ["1", "2", "3"].map(x => parseInt(x));
   // [1, 2, 3]

réduire

reduce libère une valeur de la structure qui l'entoure.

Là encore, nous allons l'appliquer à un objet plus simple :

class A {
    constructor (value) {
        this.value = value
    }

    reduce (f, init) { 
        return init !== undefined
            ? f(init, this.value)
            : this.value
    }
}

new A(5).reduce(); // 5

const concat = (a, b) => a.concat(b);
new A(5).reduce(concat, []); // [ 5 ]

Que vous laissiez la valeur seule ou que vous la réintroduisiez dans quelque chose d'autre, la sortie de reduce peut avoir n'importe quelle forme. C'est littéralement le contraire de map .

Implications pour les tableaux

Les tableaux peuvent contenir des valeurs multiples ou nulles, ce qui donne lieu à deux exigences, parfois contradictoires.

La nécessité de combiner

Comment renvoyer des valeurs multiples sans structure autour d'elles ?

C'est impossible. Pour ne renvoyer qu'une seule valeur, nous avons deux possibilités :

• la synthèse des valeurs en une seule valeur ;
• déplacer les valeurs dans une structure différente.

N'est-ce pas plus logique maintenant ?

La nécessité d'initialiser

Et s'il n'y a pas de valeur à renvoyer ?

Si reduce renvoie une valeur erronée, il n'y aurait aucun moyen de savoir si le tableau source est vide ou s'il contient cette valeur erronée, donc à moins de fournir une valeur initiale, reduce doit lancer.

La véritable fonction du réducteur

Vous devriez être en mesure de deviner ce que le réducteur f dans l'extrait suivant :

[a].reduce(f);
[].reduce(f, a);

Rien . Il ne s'agit pas d'un nom.

C'est le cas le plus banal : a est la valeur unique que nous voulons renvoyer, donc f n'est pas nécessaire.

C'est d'ailleurs la raison pour laquelle nous n'avons pas rendu le réducteur obligatoire dans notre classe A plus tôt : parce qu'il ne contenait qu'une seule valeur. Elle est obligatoire pour les tableaux car ceux-ci peuvent contenir plusieurs valeurs.

Puisque le réducteur n'est appelé que lorsque vous avez 2 valeurs ou plus, dire que son seul but est de les combiner n'est qu'un jet de pierre.

Sur la transformation des valeurs

Pour les tableaux de longueur variable, il est dangereux d'attendre du réducteur qu'il transforme les valeurs car, comme nous l'avons découvert, il peut ne pas être appelé.

Je vous encourage à map avant de vous reduce lorsque vous devez à la fois transformer des valeurs et changer de forme.

Pour des raisons de lisibilité, il est de toute façon souhaitable de séparer ces deux aspects.

Quand ne pas utiliser la réduction

Parce que reduce est un outil polyvalent pour réaliser une transformation de structure, je vous conseille de l'éviter lorsque vous voulez récupérer un tableau s'il existe une autre méthode plus ciblée qui fait ce que vous voulez.

Plus précisément, si vous avez des difficultés avec les tableaux imbriqués dans un fichier map Pensez à flatMap o flat avant d'atteindre le reduce .

Au cœur de la réduction

une opération binaire récursive

Mise en œuvre reduce sur les tableaux introduit cette boucle de rétroaction où le premier argument du réducteur est la valeur de retour de l'itération précédente.

Inutile de dire qu'il ne ressemble en rien à map de l'entreprise.

Nous pourrions mettre en œuvre Array.reduce de manière récursive :

const reduce = (f, acc, [current, ...rest]) => 
    rest.length == 0
    ? f(acc, current)
    : reduce(f, f(acc, current), rest)

Cela met en évidence la nature binaire du réducteur f et comment sa valeur de retour devient le nouveau acc lors de l'itération suivante.

Je vous laisse vous convaincre que ce qui suit est vrai :

reduce(f, a, [b, c, d])

// is equivalent to
f(f(f(a, b), c), d)

// or if you squint a little 
((a  b)  c)  d

Cela devrait vous sembler familier : vous savez que les opérations arithmétiques obéissent à des règles telles que l'"associativité" ou la "commutativité". Ce que je veux dire ici, c'est que le même type de règles s'applique.

reduce peut supprimer la structure environnante, les valeurs sont toujours liées dans une structure algébrique pendant la durée de la transformation.

l'algèbre des réducteurs

Les structures algébriques dépassent largement le cadre de cette réponse, et je me contenterai donc d'évoquer leur pertinence.

((a  b)  c)  d

En examinant l'expression ci-dessus, il est évident qu'il existe une contrainte qui lie toutes les valeurs entre elles : doit savoir les combiner de la même manière + doit savoir combiner 1 + 2 et tout aussi important (1 + 2) + 3 .

Structure de sécurité la plus faible

Une façon de s'en assurer est d'imposer que ces valeurs appartiennent à un même ensemble sur lequel le réducteur est une opération binaire "interne" ou "fermée", c'est-à-dire que la combinaison de deux valeurs quelconques de cet ensemble avec le réducteur produit une valeur qui appartient au même ensemble.

En algèbre abstraite, on appelle cela un magma . Vous pouvez également consulter semi-groupes dont on parle davantage et qui sont la même chose que l'associativité (pas d'accolades nécessaires), bien que reduce s'en moque.

Moins sûr

Vivre dans un magma n'est pas absolument nécessaire : on peut imaginer une situation où peut combiner a y b mais pas c y b .

La composition des fonctions en est un exemple. L'une des fonctions suivantes renvoie une chaîne de caractères, ce qui limite l'ordre dans lequel vous pouvez les combiner :

const a = x => x * 2;
const b = x => x ** 2;
const c = x => x + ' !';

// (a  b)  c
const abc = x => c(b(a(x)));
abc(5); // "100 !"

// (a  c)  b
const acb = x => b(c(a(x)));
acb(5); // NaN

Comme de nombreuses opérations binaires, la composition de fonctions peut être utilisée comme réducteur.

Savoir si nous nous trouvons dans une situation où le fait de réordonner ou de supprimer des éléments d'un tableau peut avoir des conséquences négatives sur la qualité de la vie. reduce La pause est en quelque sorte précieuse.

Donc, les magmas : pas absolument nécessaires, mais très importants.

Qu'en est-il de la valeur initiale ?

Supposons que nous voulions éviter qu'une exception soit levée lorsque le tableau est vide, en introduisant une valeur initiale :

array.reduce(f, init)

// which is really the same as doing
[init, ...array].reduce(f)

// or
((init  a)  b)  c...

Nous disposons maintenant d'une valeur supplémentaire. Il n'y a pas de problème.

"Pas de problème ! Nous avons dit que le but du réducteur était de combiner les valeurs du tableau, mais init n'est pas un vrai valeur : elle a été introduite avec force par nous-mêmes, elle ne devrait pas affecter le résultat de l'enquête. reduce .

La question est la suivante :

Ce qu'il faut faire init devrions-nous choisir pour que f(init, a) o init a retours a ?

Nous voulons une valeur initiale qui agisse comme si elle n'existait pas. Nous voulons un élément neutre (ou "identité").

Vous pouvez consulter magmas unitaire o monoïdes (idem pour l'associativité) qui sont des gros mots pour les magmas dotés d'un élément neutre.

Quelques éléments neutres

Vous connaissez déjà un certain nombre d'éléments neutres

numbers.reduce((a, b) => a + b, 0)

numbers.reduce((a, b) => a * b, 1)

booleans.reduce((a, b) => a && b, true)

strings.reduce((a, b) => a.concat(b), "")

arrays.reduce((a, b) => a.concat(b), [])

vec2s.reduce(([u,v], [x,y]) => [u+x,v+y], [0,0])

mat2s.reduce(dot, [[1,0],[0,1]])

Vous pouvez répéter ce schéma pour de nombreux types d'abstractions. Notez que l'élément neutre et le calcul n'ont pas besoin d'être aussi triviaux ( exemple extrême ).

Les difficultés de l'élément neutre

Nous devons accepter le fait que certaines réductions ne sont possibles que pour des tableaux non vides et que l'ajout de mauvais initialisateurs ne résout pas le problème.

Quelques exemples de réductions qui ont mal tourné :

Partiellement neutre

numbers.reduce((a, b) => b - a, 0)

// does not work
numbers.reduce((a, b) => a - b, 0)

Soustraction 0 formulaire b retours b mais en soustrayant b de 0 retours -b . Nous disons que seule la "bonne identité" est vraie.

Toutes les opérations non-commutatives ne sont pas dépourvues d'un élément neutre symétrique, mais c'est un bon signe.

Hors plage

const min = (a, b) => a < b ? a : b;

// Do you really want to return Infinity?
numbers.reduce(min, Infinity)

Infinity est la seule valeur initiale qui ne modifie pas la sortie de reduce pour les tableaux non vides, mais il est peu probable que nous voulions qu'elle apparaisse dans notre programme.

L'élément neutre n'est pas une valeur joker que nous ajoutons par commodité. Il doit s'agir d'une valeur autorisée, sinon il ne sert à rien.

Absurde

Les réductions ci-dessous s'appuient sur la position, mais l'ajout d'un initialisateur déplace naturellement le premier élément à la deuxième place, ce qui nécessite de modifier l'index dans le réducteur pour maintenir le comportement.

const first = (a, b, i) => !i ? b : a;
things.reduce(first, null);

const camelCase = (a, b, i) =>  a + (
    !i ? b : b[0].toUpperCase() + b.slice(1)
);
words.reduce(camelCase, '');

Il aurait été beaucoup plus propre d'accepter le fait que le tableau ne peut pas être vide et de simplifier la définition des réducteurs.

De plus, les valeurs initiales sont dégénérées :

• null n'est pas le premier élément d'un tableau vide.

• une chaîne vide n'est en aucun cas un identifiant valide.

Il n'y a aucun moyen de préserver la notion de "première" avec une valeur initiale.

conclusion

Les structures algébriques peuvent nous aider à penser nos programmes de manière plus systématique. En sachant à quelle structure nous avons affaire, nous pouvons prédire exactement ce que nous pouvons attendre de reduce Je ne peux donc que vous conseiller de les rechercher.

Un pas de plus

Nous avons vu comment map y reduce étaient si différents du point de vue de la structure, mais ce n'est pas comme s'il s'agissait de deux choses isolées.

Nous pouvons exprimer map en termes de reduce Car il est toujours possible de reconstruire la même structure que celle de départ.

const map = f => (acc, x) => 
    acc.concat(f(x))
;

const double = x => x * 2;
[1, 2, 3].reduce(map(double), []) // [2, 4, 6]

En poussant les choses un peu plus loin, on est parvenu à des astuces astucieuses telles que les transducteurs.

Je n'entrerai pas dans les détails, mais je voudrais que vous remarquiez deux ou trois choses qui feront écho à ce que nous avons déjà dit.

Transducteurs

Voyons d'abord quel est le problème que nous essayons de résoudre

[1, 2, 3, 4].filter(x => x % 2 == 0)
            .map(x => x ** 2)
            .reduce((a, b) => a + b)
// 20

Nous itérons 3 fois et créons 2 structures de données intermédiaires. Ce code est déclaratif, mais n'est pas efficace. Les transducteurs tentent de concilier les deux.

Tout d'abord, un petit util pour composer des fonctions à l'aide de reduce car nous n'allons pas utiliser le chaînage de méthodes :

const composition = (f, g) => x => f(g(x));
const identity = x => x;

const compose = (...functions) => 
    functions.reduce(composition, identity)
;

// compose(a, b, c) is the same as x => a(b(c(x)))

Prêtez maintenant attention à la mise en œuvre de map y filter souffler. Nous passons dans cette reducer au lieu de concaténer directement.

const map = f => reducer => (acc, x) => 
    reducer(acc, f(x))
;

const filter = f => reducer => (acc, x) => 
    f(x) ? reducer(acc, x) : acc
;

examiner cette question de manière plus spécifique :
reducer => (acc, ) => [...]
après la fonction de rappel f est appliqué, nous nous retrouvons avec une fonction qui prend un réducteur en entrée et renvoie un réducteur.

Ce sont ces fonctions symétriques que nous transmettons à compose :

const pipeline = compose(
    filter(x => x % 2 == 0), 
    map(x => x ** 2)
);

Se souvenir compose est mis en œuvre avec reduce : notre composition définie précédemment combine nos fonctions symétriques.

Le résultat de cette opération est une fonction de la même forme : quelque chose qui attend un réducteur et renvoie un réducteur, ce qui signifie

• nous avons un magma. Nous pouvons continuer à composer des transformations tant qu'elles ont cette forme.
• nous pouvons consommer cette chaîne en appliquant la fonction résultante à un réducteur, qui renverra un réducteur que nous pourrons utiliser avec reduce

Je vous laisse développer le tout si vous avez besoin d'être convaincu. Si vous le faites, vous remarquerez que les transformations seront commodément appliquées de gauche à droite, ce qui est la direction opposée de compose .

D'accord, utilisons cet énergumène :

const add = (a, b) => a + b;

const reducer = pipeline(add);

const identity = 0;

[1, 2, 3, 4].reduce(reducer, identity); // 20

Nous avons composé des opérations aussi diverses que map , filter y reduce en un seul reduce en n'itérant qu'une seule fois sans structure de données intermédiaire.

Ce n'est pas une mince affaire ! Et il ne s'agit pas d'un projet que l'on peut mettre en place en choisissant entre map y reduce uniquement sur la base de la concision de la syntaxe.

Remarquez également que nous avons un contrôle total sur la valeur initiale et le réducteur final. Nous avons utilisé 0 y add mais nous aurions pu utiliser [] y concat (de manière plus réaliste push du point de vue des performances) ou toute autre structure de données pour laquelle nous pouvons mettre en œuvre une opération de type concat.

Answer 5

Les map() renvoie un nouveau tableau en passant une fonction sur chaque élément du tableau d'entrée.

Il s'agit d'une différence par rapport à reduce() qui prend un tableau et une fonction de la même manière, mais la fonction prend 2 entrées - un accumulateur et une valeur courante.

Donc reduce() pourrait être utilisé comme map() si vous avez toujours .concat dans l'accumulateur la sortie suivante d'une fonction. Cependant, il est plus couramment utilisé pour réduire les dimensions d'un tableau, soit en prenant un tableau à une dimension et en renvoyant une seule valeur, soit en aplatissant un tableau à deux dimensions, etc.