Meilleur moyen de fusionner deux cartes et de additionner les valeurs de la même clé?

181
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. Le résultat sera donc:

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

Maintenant, j'ai 2 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.

Freewind
la source
Le plus facile estmap1 ++ map2
Seraf
3
@Seraf Cela "fusionne" simplement les cartes, ignorant les doublons au lieu de additionner leurs valeurs.
Zeynep Akkalyoncu Yilmaz
@ZeynepAkkalyoncuYilmaz à droite aurait dû mieux lire la question, laisse dans la honte
Seraf

Réponses:

143

Scalaz a le concept d'un Semigroup qui capture ce que vous voulez faire ici, et conduit sans doute à la solution la plus courte / 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 mappes, repliant l V' opérateur semigroup de sur toutes les valeurs en double. Le semi-groupe standard pour Intutilise l'opérateur d'addition, vous obtenez donc la somme des valeurs pour chaque clé dupliquée.

Edit : Un peu plus de détails, à la demande de user482745.

Mathématiquement, un semigroupe est juste un ensemble de valeurs, avec un opérateur qui prend deux valeurs de cet ensemble et produit une autre valeur à partir de cet ensemble. Ainsi, les entiers sous addition sont un semi-groupe, par exemple - l' +opérateur combine deux entiers pour en faire un autre int.

Vous pouvez également définir un semi-groupe sur l'ensemble de "toutes les cartes avec un type de clé et un type de valeur donnés", à condition que vous puissiez proposer une opération qui combine deux cartes pour en produire une nouvelle qui est en quelque sorte la combinaison des deux contributions.

Si aucune clé n'apparaît dans les deux cartes, c'est trivial. Si la même clé existe dans les deux mappages, nous devons combiner les deux valeurs auxquelles la clé mappe. Hmm, n'avons-nous pas juste décrit un opérateur qui combine deux entités du même type? C'est pourquoi dans Scalaz un semigroup pour Map[K, V]existe si et seulement si un Semigroup pour Vexiste - Vle semigroup de est utilisé pour combiner les valeurs de deux mappes affectées à la même clé.

Donc, parce que Intc'est le type de valeur ici, la "collision" sur la 1clé est résolue par l'addition entière des deux valeurs mappées (comme c'est ce que fait l'opérateur semigroup d'Int), par conséquent 100 + 9. Si les valeurs avaient été des chaînes, une collision aurait entraîné une concaténation de chaînes des deux valeurs mappées (encore une fois, parce que c'est ce que fait l'opérateur semigroup pour String).

(Et fait intéressant, parce que la concaténation de chaînes n'est pas commutative - c'est-à-dire que "a" + "b" != "b" + "a"l'opération de semi-groupe qui en résulte ne l'est pas non plus. Elle map1 |+| map2est donc différente du map2 |+| map1cas String, mais pas du cas Int.)

Andrzej Doyle
la source
37
Brillant! Premier exemple pratique où cela scalaza du sens.
soc
5
Sans blague! Si vous commencez à le chercher ... il est partout. Pour citer Erric Torrebone auteur de specs et de specs2: "D'abord, vous apprenez Option et vous commencez à la voir partout. Ensuite, vous apprenez Applicative et c'est la même chose. Ensuite?" Viennent ensuite des concepts encore plus fonctionnels. Et ceux-ci vous aident grandement à structurer votre code et à résoudre correctement les problèmes.
AndreasScheinert
4
En fait, je cherchais Option depuis cinq ans quand j'ai finalement trouvé Scala. La différence entre une référence d'objet Java qui pourrait être nulle et une qui ne peut pas l'être (c'est-à-dire entre Aet Option[A]) est si énorme que je ne pouvais pas croire qu'ils étaient vraiment du même type. J'ai juste commencé à regarder Scalaz. Je ne suis pas sûr d'être assez intelligent ...
Malvolio
1
Il existe également une option pour Java, voir Java fonctionnel. N'ayez pas peur, apprendre est amusant. Et la programmation fonctionnelle ne vous apprend pas (seulement) de nouvelles choses, mais vous offre plutôt l'aide du programmeur pour fournir des termes, du vocabulaire pour résoudre les problèmes. La question OP en est un parfait exemple. Le concept d'un Semigroup est si simple que vous l'utilisez tous les jours par exemple pour les chaînes. La vraie puissance apparaît si vous identifiez cette abstraction, la nommez et enfin l'appliquez à d'autres types alors juste String.
AndreasScheinert
1
Comment est-il possible que cela aboutisse à 1 -> (100 + 9)? Pouvez-vous me montrer "trace de pile"? Merci. PS: Je demande ici de rendre la réponse plus claire.
user482745
154

La réponse la plus courte que je connaisse qui n'utilise que la bibliothèque standard est

map1 ++ map2.map{ case (k,v) => k -> (v + map1.getOrElse(k,0)) }
Rex Kerr
la source
34
Belle solution. J'aime ajouter l'indice, qui ++remplace tout (k, v) de la carte sur le côté gauche de ++(ici map1) par (k, v) de la carte de droite, si (k, _) existe déjà dans la gauche carte latérale (ici map1), par exempleMap(1->1) ++ Map(1->2) results in Map(1->2)
Lutz
Une sorte de version plus soignée: for ((k, v) <- (aa ++ bb)) yield k -> (if ((aa contient k) && (bb contains k)) aa (k) + v else v)
dividebyzero
J'ai fait quelque chose de différent précédemment, mais voici une version de ce que vous avez fait, en remplaçant la carte par une formap1 ++ (pour ((k, v) <- map2) yield k -> (v + map1.getOrElse (k, 0 )))
dividebyzero
1
@ Jus12 - No. .a une priorité plus élevée que ++; vous lisez map1 ++ map2.map{...}comme map1 ++ (map2 map {...}). Donc, dans un sens, vous mappez map1les éléments, et dans l’autre non.
Rex Kerr
1
@matt - Scalaz le fera déjà, donc je dirais "une bibliothèque existante le fait déjà".
Rex Kerr
49

Solution rapide:

(map1.keySet ++ map2.keySet).map {i=> (i,map1.getOrElse(i,0) + map2.getOrElse(i,0))}.toMap
Matthew Farwell
la source
42

Eh bien, maintenant dans la bibliothèque scala (au moins dans la version 2.10), il y a quelque chose que vous vouliez - une fonction fusionnée . MAIS il est présenté 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 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) })

Également dans scaladoc mentionné que

La mergedméthode est en moyenne plus performante que d'effectuer un parcours et de reconstruire une nouvelle carte de hachage immuable à partir de zéro, ou ++.

Mikhail Golubtsov
la source
1
Pour le moment, ce n'est que dans Hashmap immuable, pas dans Hashmap mutable.
Kevin Wheeler
2
C'est assez ennuyeux qu'ils n'aient que cela pour HashMaps pour être honnête.
Johan S
Je ne peux pas faire compiler cela, il semble que le type qu'il accepte est privé, donc je ne peux pas passer une fonction tapée qui correspond.
Ryan The Leach
2
Il semble que quelque chose ait changé dans la version 2.11. Consultez 2.10 scaladoc - scala-lang.org/api/2.10.1/ ... Il existe une fonction habituelle. Mais en 2.11, c'est MergeFunction.
Mikhail Golubtsov
Tout ce qui a changé dans la version 2.11 est l'introduction d'un alias de type pour ce type de fonction particulierprivate type MergeFunction[A1, B1] = ((A1, B1), (A1, B1)) => (A1, B1)
EthanP
14

Cela peut être implémenté en tant que Monoid avec juste Scala. Voici un exemple d'implémentation. Avec cette approche, nous pouvons fusionner non seulement 2, mais une liste de cartes.

// Monoid trait

trait Monoid[M] {
  def zero: M
  def op(a: M, b: M): M
}

Implémentation basée sur la carte du trait Monoid qui fusionne deux cartes.

val mapMonoid = new Monoid[Map[Int, Int]] {
  override def zero: Map[Int, Int] = Map()

  override def op(a: Map[Int, Int], b: Map[Int, Int]): Map[Int, Int] =
    (a.keySet ++ b.keySet) map { k => 
      (k, a.getOrElse(k, 0) + b.getOrElse(k, 0))
    } toMap
}

Maintenant, si vous avez une liste de cartes qui doivent être fusionnées (dans ce cas, seulement 2), cela peut être fait comme ci-dessous.

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

val maps = List(map1, map2) // The list can have more maps.

val merged = maps.foldLeft(mapMonoid.zero)(mapMonoid.op)
Jegan
la source
5
map1 ++ ( for ( (k,v) <- map2 ) yield ( k -> ( v + map1.getOrElse(k,0) ) ) )
AmigoNico
la source
5

J'ai écrit un article de blog à ce sujet, vérifiez-le:

http://www.nimrodstech.com/scala-map-merge/

essentiellement en utilisant le semi-groupe scalaz, vous pouvez y parvenir assez facilement

ressemblerait à quelque chose comme:

  import scalaz.Scalaz._
  map1 |+| map2
Nimrod007
la source
11
Vous devez mettre un peu plus de détails dans votre réponse, de préférence un code d'implémentation. Faites-le également pour les autres réponses similaires que vous avez publiées et adaptez chaque réponse à la question spécifique qui a été posée. Règle du pouce: le demandeur doit pouvoir bénéficier de votre réponse sans cliquer sur le lien du blog.
Robert Harvey
5

Vous pouvez également faire cela avec les chats .

import cats.implicits._

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

map1 combine map2 // Map(2 -> 20, 1 -> 109, 3 -> 300)
Artsiom Miklushou
la source
Eek, import cats.implicits._. Import import cats.instances.map._ import cats.instances.int._ import cats.syntax.semigroup._pas beaucoup plus verbeux ...
St.Antario
@ St.Antario, c'est en fait un moyen recommandé d'avoir seulementimport cats.implicits._
Artsiom Miklushou
Recommandé par qui? Faire entrer toutes les instances implicites (dont la plupart sont inutilisées) dans la portée complique la vie du compilateur. Et d'ailleurs si on n'a pas besoin, disons, d'instance applicative pourquoi l'apporteraient-ils là-bas?
Saint
4

Pour commencer Scala 2.13, une autre solution basée uniquement sur la librairie standard consiste à remplacer la groupBypartie de votre solution par groupMapReducelaquelle (comme son nom l'indique) est l'équivalent d'un groupBysuivi de mapValueset d'une étape de réduction:

// val map1 = Map(1 -> 9, 2 -> 20)
// val map2 = Map(1 -> 100, 3 -> 300)
(map1.toSeq ++ map2).groupMapReduce(_._1)(_._2)(_+_)
// Map[Int,Int] = Map(2 -> 20, 1 -> 109, 3 -> 300)

Ce:

  • Concatène les deux cartes sous la forme d'une séquence de tuples ( List((1,9), (2,20), (1,100), (3,300))). Par souci de concision, map2est implicitement converti en Seqpour s'adapter au type de map1.toSeq- mais vous pouvez choisir de le rendre explicite en utilisant map2.toSeq,

  • groups éléments basés sur leur première partie de tuple (partie de groupe du groupe MapReduce),

  • maps les valeurs groupées dans leur deuxième partie de tuple (partie de mappage du groupe Map Reduce),

  • reduces mappé les valeurs ( _+_) en les additionnant (réduire une partie de groupMap Réduire ).

Xavier Guihot
la source
3

Voici ce que j'ai fini par utiliser:

(a.toSeq ++ b.toSeq).groupBy(_._1).mapValues(_.map(_._2).sum)
user1084563
la source
1
Ce n'est vraiment pas très différent de la 1ère solution proposée par l'OP.
jwvh
2

La réponse d'Andrzej Doyle contient une excellente explication des semi-groupes qui vous permet d'utiliser l' |+|opérateur pour joindre deux cartes et additionner les valeurs des clés correspondantes.

Il existe de nombreuses façons de définir quelque chose comme une instance d'une classe de types, et contrairement à l'OP, vous ne voudrez peut-être pas additionner vos clés spécifiquement. Ou, vous voudrez peut-être opérer sur une union plutôt qu'une intersection. Scalaz ajoute également des fonctions supplémentaires à Mapcet effet:

https://oss.sonatype.org/service/local/repositories/snapshots/archive/org/scalaz/scalaz_2.11/7.3.0-SNAPSHOT/scalaz_2.11-7.3.0-SNAPSHOT-javadoc.jar/!/ index.html # scalaz.std.MapFunctions

Tu peux faire

import scalaz.Scalaz._

map1 |+| map2 // As per other answers
map1.intersectWith(map2)(_ + _) // Do things other than sum the values
user1158559
la source
2

Le moyen le plus rapide et le plus simple:

val m1 = Map(1 -> 1.0, 3 -> 3.0, 5 -> 5.2)
val m2 = Map(0 -> 10.0, 3 -> 3.0)
val merged = (m2 foldLeft m1) (
  (acc, v) => acc + (v._1 -> (v._2 + acc.getOrElse(v._1, 0.0)))
)

De cette façon, chacun des éléments est immédiatement ajouté à la carte.

La deuxième ++façon est:

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

Contrairement à la première manière, d'une seconde manière pour chaque élément d'une seconde carte, une nouvelle liste sera créée et concaténée à la carte précédente.

L' caseexpression crée implicitement une nouvelle liste à l'aide de la unapplyméthode.

Alexey Kudryashov
la source
1

C'est ce que j'ai imaginé ...

def mergeMap(m1: Map[Char, Int],  m2: Map[Char, Int]): Map[Char, Int] = {
   var map : Map[Char, Int] = Map[Char, Int]() ++ m1
   for(p <- m2) {
      map = map + (p._1 -> (p._2 + map.getOrElse(p._1,0)))
   }
   map
}
kaur
la source
1

En utilisant le modèle de classe de types, nous pouvons fusionner n'importe quel type numérique:

object MapSyntax {
  implicit class MapOps[A, B](a: Map[A, B]) {
    def plus(b: Map[A, B])(implicit num: Numeric[B]): Map[A, B] = {
      b ++ a.map { case (key, value) => key -> num.plus(value, b.getOrElse(key, num.zero)) }
    }
  }
}

Usage:

import MapSyntax.MapOps

map1 plus map2

Fusion d'une séquence de cartes:

maps.reduce(_ plus _)
Tomer Sela
la source
0

J'ai une petite fonction pour faire le travail, c'est dans ma petite bibliothèque pour certaines fonctionnalités fréquemment utilisées qui ne sont pas dans la bibliothèque standard. Cela devrait fonctionner pour tous les types de cartes, mutables et immuables, pas seulement les HashMaps

Voici l'utilisation

scala> import com.daodecode.scalax.collection.extensions._
scala> val merged = Map("1" -> 1, "2" -> 2).mergedWith(Map("1" -> 1, "2" -> 2))(_ + _)
merged: scala.collection.immutable.Map[String,Int] = Map(1 -> 2, 2 -> 4)

https://github.com/jozic/scalax-collection/blob/master/README.md#mergedwith

Et voici le corps

def mergedWith(another: Map[K, V])(f: (V, V) => V): Repr =
  if (another.isEmpty) mapLike.asInstanceOf[Repr]
  else {
    val mapBuilder = new mutable.MapBuilder[K, V, Repr](mapLike.asInstanceOf[Repr])
    another.foreach { case (k, v) =>
      mapLike.get(k) match {
        case Some(ev) => mapBuilder += k -> f(ev, v)
        case _ => mapBuilder += k -> v
      }
    }
    mapBuilder.result()
  }

https://github.com/jozic/scalax-collection/blob/master/src%2Fmain%2Fscala%2Fcom%2Fdaodecode%2Fscalax%2Fcollection%2Fextensions%2Fpackage.scala#L190

Eugène Platonov
la source