La meilleure façon de fusionner deux cartes et d'additionner les valeurs de la même clé ?

Question

val map1 = Map(1 -> 9 , 2 -> 20)
val map2 = Map(1 -> 100, 3 -> 300)

Je veux les fusionner, et additionner les valeurs des mêmes clés. Donc le résultat sera :

Map(2->20, 1->109, 3->300)

Maintenant, j'ai deux solutions :

val list = map1.toList ++ map2.toList
val merged = list.groupBy ( _._1) .map { case (k,v) => k -> v.map(_._2).sum }

et

val merged = (map1 /: map2) { case (map, (k,v)) =>
    map + ( k -> (v + map.getOrElse(k, 0)) )
}

Mais je veux savoir s'il existe de meilleures solutions.

Answer 1

La réponse la plus courte que je connaisse, qui utilise uniquement la bibliothèque standard, est la suivante

map1 ++ map2.map{ case (k,v) => k -> (v + map1.getOrElse(k,0)) }

Answer 2

Scalaz a le concept d'un Semigroupe qui capture ce que vous voulez faire ici, et mène à la solution la plus courte et la plus propre :

scala> import scalaz._
import scalaz._

scala> import Scalaz._
import Scalaz._

scala> val map1 = Map(1 -> 9 , 2 -> 20)
map1: scala.collection.immutable.Map[Int,Int] = Map(1 -> 9, 2 -> 20)

scala> val map2 = Map(1 -> 100, 3 -> 300)
map2: scala.collection.immutable.Map[Int,Int] = Map(1 -> 100, 3 -> 300)

scala> map1 |+| map2
res2: scala.collection.immutable.Map[Int,Int] = Map(1 -> 109, 3 -> 300, 2 -> 20)

Plus précisément, l'opérateur binaire pour Map[K, V] combine les clés des cartes, le pliage V L'opérateur de semigroupe de l'auteur sur toutes les valeurs en double. Le semigroupe standard pour Int utilise l'opérateur d'addition, de sorte que vous obtenez la somme des valeurs pour chaque clé dupliquée.

Editar : Un peu plus de détails, à la demande de l'utilisateur 482745.

Mathématiquement, un semigroupe est juste un ensemble de valeurs, ainsi qu'un opérateur qui prend deux valeurs de cet ensemble, et produit une autre valeur de cet ensemble. Ainsi, les entiers sous addition sont un semigroupe, par exemple - le + L'opérateur combine deux entiers pour en faire un autre entier.

Vous pouvez également définir un semigroupe sur l'ensemble de "toutes les cartes avec un type de clé et un type de valeur donnés", tant que vous pouvez trouver une opération qui combine deux cartes pour en produire une nouvelle qui est en quelque sorte la combinaison des deux entrées.

S'il n'y a pas de clés qui apparaissent dans les deux cartes, c'est trivial. Si la même clé existe dans les deux cartes, nous devons combiner les deux valeurs auxquelles la clé correspond. Hmm, ne venons-nous pas de décrire un opérateur qui combine deux entités du même type ? C'est pourquoi, dans Scalaz, un semigroupe de Map[K, V] existe si et seulement si un Semigroup pour V existe - V Le semigroupe de l'auteur est utilisé pour combiner les valeurs de deux cartes qui sont affectées à la même clé.

Donc, parce que Int est le type de valeur ici, la "collision" sur le 1 est résolu par l'addition entière des deux valeurs mappées (car c'est ce que fait l'opérateur semigroupe de Int), d'où 100 + 9 . Si les valeurs avaient été des chaînes de caractères, une collision aurait entraîné la concaténation des deux valeurs mappées (encore une fois, parce que c'est ce que fait l'opérateur de semigroupe pour les chaînes de caractères).

(Et de façon intéressante, parce que la concaténation des chaînes de caractères n'est pas commutative - c'est-à-dire, "a" + "b" != "b" + "a" - l'opération de semigroupe qui en résulte ne l'est pas non plus. Donc map1 |+| map2 est différent de map2 |+| map1 dans le cas de String, mais pas dans le cas de Int).

Answer 3

Solution rapide :

(map1.keySet ++ map2.keySet).map {i=> (i,map1.getOrElse(i,0) + map2.getOrElse(i,0))}.toMap

Answer 4

Eh bien, maintenant, dans la bibliothèque scala (au moins dans la version 2.10), il y a quelque chose que vous souhaitiez fusionné fonction. MAIS elle est présentée uniquement dans HashMap et non dans Map. C'est un peu déroutant. De plus, la signature est encombrante - je ne peux pas imaginer pourquoi j'aurais besoin d'une clé deux fois et quand j'aurais besoin de produire une paire avec une autre clé. Mais néanmoins, cela fonctionne et c'est beaucoup plus propre que les solutions "natives" précédentes.

val map1 = collection.immutable.HashMap(1 -> 11 , 2 -> 12)
val map2 = collection.immutable.HashMap(1 -> 11 , 2 -> 12)
map1.merged(map2)({ case ((k,v1),(_,v2)) => (k,v1+v2) })

Dans scaladoc, il est également mentionné que

En merged est en moyenne plus performante que l'utilisation de la méthode et de reconstruire une nouvelle carte de hachage immuable à partir de zéro, ou ++ .

Answer 5

map1 ++ ( for ( (k,v) <- map2 ) yield ( k -> ( v + map1.getOrElse(k,0) ) ) )