Der beste Weg, um zwei Karten zusammenzuführen und die Werte desselben Schlüssels zu summieren?

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

Ich möchte sie zusammenführen und die Werte derselben Schlüssel summieren. Das Ergebnis wird also sein:

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

Jetzt habe ich 2 Lösungen:

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

und

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

Aber ich möchte wissen, ob es bessere Lösungen gibt.

Freilauf
quelle
Am einfachsten istmap1 ++ map2
Seraf
3
@Seraf Das "verschmilzt" die Karten einfach und ignoriert Duplikate, anstatt ihre Werte zu summieren.
Zeynep Akkalyoncu Yilmaz
@ZeynepAkkalyoncuYilmaz rechts hätte die Frage besser lesen sollen, geht in Schande
Seraf

Antworten:

142

Scalaz hat das Konzept einer Halbgruppe, die erfasst, was Sie hier tun möchten, und zu der wohl kürzesten / saubersten Lösung führt:

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)

Insbesondere Map[K, V]kombiniert der Binäroperator für die Schlüssel der Karten und faltet Vden Halbgruppenoperator über alle doppelten Werte. Die Standard-Halbgruppe für Intverwendet den Additionsoperator, sodass Sie die Summe der Werte für jeden doppelten Schlüssel erhalten.

Bearbeiten : Etwas detaillierter gemäß der Anfrage von user482745.

Mathematisch a Halbgruppe nur eine Menge von Werten, zusammen mit einem Operator, der zwei Werte aus dieser Menge nimmt und einen anderen Wert aus dieser Menge erzeugt. So sind +hinzugefügte Ganzzahlen beispielsweise eine Halbgruppe - der Operator kombiniert zwei Ints, um ein weiteres Int zu erstellen.

Sie können auch eine Halbgruppe über der Menge "Alle Karten mit einem bestimmten Schlüsseltyp und Werttyp" definieren, sofern Sie eine Operation entwickeln können, bei der zwei Karten kombiniert werden, um eine neue zu erstellen, die irgendwie die Kombination der beiden ist Eingänge.

Wenn in beiden Karten keine Schlüssel vorhanden sind, ist dies trivial. Wenn in beiden Karten derselbe Schlüssel vorhanden ist, müssen wir die beiden Werte kombinieren, denen der Schlüssel zugeordnet ist. Hmm, haben wir nicht gerade einen Operator beschrieben, der zwei Entitäten desselben Typs kombiniert? Deshalb in Scalaz eine Halbgruppe fürMap[K, V] genau dann, wenn eine Halbgruppe für Vexistiert - Vdie Halbgruppe wird verwendet, um die Werte aus zwei Karten zu kombinieren, die demselben Schlüssel zugeordnet sind.

Also, weil Inthier der Werttyp ist, die "Kollision" auf dem1 Schlüssel durch ganzzahlige Addition der beiden zugeordneten Werte aufgelöst (wie dies der Halbgruppenoperator von Int tut) 100 + 9. Wenn die Werte Strings gewesen wären, hätte eine Kollision zu einer Verkettung der beiden zugeordneten Werte geführt (wiederum, weil dies der Halbgruppenoperator für String tut).

(Und interessanterweise, weil die Verkettung von Zeichenfolgen nicht kommutativ ist - das heißt, "a" + "b" != "b" + "a"- die resultierende Halbgruppenoperation auch nicht. Sie map1 |+| map2unterscheidet sich also von map2 |+| map1der Zeichenfolge , aber nicht von Int.)

Andrzej Doyle
quelle
37
Brillant! Erstes praktisches Beispiel, wo scalazes Sinn machte.
Soc
5
Im Ernst! Wenn Sie anfangen, danach zu suchen ... ist es überall. Um erric torrebone zu zitieren, Autor von Spezifikationen und Spezifikationen2: "Zuerst lernst du Option und siehst sie überall. Dann lernst du Anwendbar und es ist dasselbe. Weiter?" Als nächstes kommen noch mehr funktionale Konzepte. Und diese helfen Ihnen sehr dabei, Ihren Code zu strukturieren und Probleme gut zu lösen.
AndreasScheinert
4
Eigentlich hatte ich fünf Jahre lang nach Option gesucht, als ich endlich Scala fand. Der Unterschied zwischen einer Java-Objektreferenz, die möglicherweise null ist, und einer, die nicht sein kann (dh zwischen Aund Option[A]), ist so groß, dass ich nicht glauben konnte, dass sie wirklich vom selben Typ sind. Ich habe gerade angefangen, Scalaz anzusehen. Ich bin nicht sicher, ob ich klug genug bin ...
Malvolio
1
Es gibt auch eine Option für Java, siehe Funktionales Java. Hab keine Angst, Lernen macht Spaß. Und funktionale Programmierung bringt Ihnen nicht (nur) neue Dinge bei, sondern bietet Ihnen dem Programmierer Hilfe bei der Bereitstellung von Begriffen und Vokabeln, um Probleme anzugehen. Die OP-Frage ist ein perfektes Beispiel. Das Konzept einer Halbgruppe ist so einfach, dass Sie es jeden Tag verwenden, z. B. für Strings. Die wahre Kraft erscheint, wenn Sie diese Abstraktion identifizieren, benennen und schließlich auf andere Typen als nur String anwenden.
AndreasScheinert
1
Wie ist es möglich, dass es zu 1 -> (100 + 9) führt? Können Sie mir bitte "Stack Trace" zeigen? Vielen Dank. PS: Ich bitte hier, die Antwort klarer zu machen.
Benutzer482745
151

Die kürzeste mir bekannte Antwort, die nur die Standardbibliothek verwendet, ist

map1 ++ map2.map{ case (k,v) => k -> (v + map1.getOrElse(k,0)) }
Rex Kerr
quelle
34
Schöne Lösung. Ich möchte den Hinweis hinzufügen, ++der jedes (k, v) von der Karte auf der linken Seite von ++(hier map1) durch (k, v) von der rechten Seite der Karte ersetzt, wenn (k, _) bereits auf der linken Seite existiert Seitenkarte (hier map1), zBMap(1->1) ++ Map(1->2) results in Map(1->2)
Lutz
Eine Art sauberere Version: für ((k, v) <- (aa ++ bb)) ergibt k -> (wenn ((aa enthält k) && (bb enthält k)) aa (k) + v sonst v)
Dividebyzero
Ich habe vorher etwas anderes gemacht, aber hier ist eine Version von dem, was Sie getan haben: Ersetzen der Karte durch eine forKarte1 ++ (für ((k, v) <- map2) ergibt k -> (v + map1.getOrElse (k, 0) )))
Dividebyzero
1
@ Jus12 - Nein .hat eine höhere Priorität als ++; du liest map1 ++ map2.map{...}als map1 ++ (map2 map {...}). Auf die eine Weise ordnen Sie die map1Elemente zu und auf die andere Weise nicht.
Rex Kerr
1
@matt - Scalaz wird es bereits tun, also würde ich sagen "eine vorhandene Bibliothek macht es bereits".
Rex Kerr
48

Schnelle Lösung:

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

Nun, jetzt in der Scala-Bibliothek (zumindest in 2.10) gibt es etwas, das Sie wollten - die zusammengeführte Funktion. ABER es wird nur in HashMap dargestellt, nicht in Map. Es ist etwas verwirrend. Auch die Signatur ist umständlich - ich kann mir nicht vorstellen, warum ich zweimal einen Schlüssel benötige und wann ich ein Paar mit einem anderen Schlüssel erstellen muss. Trotzdem funktioniert es und ist viel sauberer als frühere "native" Lösungen.

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

Auch in Scaladoc erwähnt das

Die mergedMethode ist im Durchschnitt leistungsfähiger als das Durchlaufen und Rekonstruieren einer neuen unveränderlichen Hash-Map von Grund auf oder ++.

Mikhail Golubtsov
quelle
1
Ab sofort ist es nur in unveränderlicher Hashmap, nicht in veränderlicher Hashmap.
Kevin Wheeler
2
Das ist ziemlich ärgerlich, dass sie nur das haben, damit HashMaps ehrlich ist.
Johan S
Ich kann dies nicht zum Kompilieren bringen. Es scheint, dass der Typ, den es akzeptiert, privat ist, daher kann ich keine typisierte Funktion übergeben, die übereinstimmt.
Ryan The Leach
2
In Version 2.11 scheint sich etwas geändert zu haben. Check out 2.10 scaladoc - scala-lang.org/api/2.10.1/… Es gibt eine übliche Funktion. Aber in 2.11 ist es MergeFunction.
Mikhail Golubtsov
Alles, was sich in 2.11 geändert hat, ist die Einführung eines private type MergeFunction[A1, B1] = ((A1, B1), (A1, B1)) => (A1, B1)
Typalias
14

Dies kann als implementiert werden Monoid mit einfachem Scala . Hier ist eine Beispielimplementierung. Mit diesem Ansatz können wir nicht nur 2, sondern eine Liste von Karten zusammenführen.

// Monoid trait

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

Die kartenbasierte Implementierung des Monoid-Merkmals, bei dem zwei Karten zusammengeführt werden.

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
}

Wenn Sie nun eine Liste von Karten haben, die zusammengeführt werden müssen (in diesem Fall nur 2), können Sie wie folgt vorgehen.

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
quelle
5
map1 ++ ( for ( (k,v) <- map2 ) yield ( k -> ( v + map1.getOrElse(k,0) ) ) )
AmigoNico
quelle
5

Ich habe einen Blog-Beitrag darüber geschrieben.

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

Grundsätzlich können Sie dies mit Scalaz Semi Group ziemlich einfach erreichen

würde ungefähr so ​​aussehen:

  import scalaz.Scalaz._
  map1 |+| map2
Nimrod007
quelle
11
Sie müssen Ihre Antwort etwas detaillierter beschreiben, vorzugsweise Implementierungscode. Tun Sie dies auch für die anderen ähnlichen Antworten, die Sie gepostet haben, und passen Sie jede Antwort auf die spezifische Frage an, die gestellt wurde. Faustregel : Der Fragesteller sollte von Ihrer Antwort profitieren können, ohne auf den Blog-Link zu klicken.
Robert Harvey
5

Sie können das auch mit Katzen tun .

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
quelle
Eek , import cats.implicits._. Importieren Sie import cats.instances.map._ import cats.instances.int._ import cats.syntax.semigroup._nicht viel ausführlicher ...
St.Antario
@ St.Antario es ist eigentlich empfohlen, nur zu habenimport cats.implicits._
Artsiom Miklushou
Von wem empfohlen? Das Einfügen aller (von denen die meisten nicht verwendeten) impliziten Instanzen in den Bereich erschweren das Leben des Compilers. Und außerdem, wenn man beispielsweise keine anwendbare Instanz benötigt, warum sollten sie sie dorthin bringen?
St.Antario
4

Zu Beginn Scala 2.13besteht eine andere Lösung, die nur auf der Standardbibliothek basiert, darin, den groupByTeil Ihrer Lösung zu ersetzen, durch den groupMapReduce(wie der Name schon sagt) ein groupBynachfolgender mapValuesund ein reduzierter Schritt entspricht:

// 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)

Dies:

  • Verkettet die beiden Karten als Folge von Tupeln ( List((1,9), (2,20), (1,100), (3,300))). Aus Gründen der Übersichtlichkeit map2wird implizit in konvertiert, Sequm sich an den Typ von anzupassen. map1.toSeqSie können ihn jedoch auch explizit festlegen map2.toSeq, indem Sie Folgendes verwenden :

  • groups Elemente basierend auf ihrem ersten Tupelteil (Gruppenteil der Gruppe MapReduce),

  • maps gruppierte Werte zu ihrem zweiten Tupelteil (Kartenteil der Gruppe Map Reduce),

  • reduces _+_Zuordnen von Werten ( ) durch Summieren (Reduzieren eines Teils von groupMap Reduce ).

Xavier Guihot
quelle
3

Folgendes habe ich letztendlich verwendet:

(a.toSeq ++ b.toSeq).groupBy(_._1).mapValues(_.map(_._2).sum)
user1084563
quelle
1
Das unterscheidet sich wirklich nicht wesentlich von der ersten vom OP vorgeschlagenen Lösung.
JWVH
2

Die Antwort von Andrzej Doyle enthält eine großartige Erklärung der Halbgruppen, mit der Sie die verwenden können |+| Operator verwenden können, um zwei Karten zu verbinden und die Werte für übereinstimmende Schlüssel zu summieren.

Es gibt viele Möglichkeiten, wie etwas als Instanz einer Typklasse definiert werden kann, und im Gegensatz zum OP möchten Sie Ihre Schlüssel möglicherweise nicht spezifisch summieren. Oder Sie möchten möglicherweise eher an einer Gewerkschaft als an einer Kreuzung arbeiten. Scalaz fügt zu Mapdiesem Zweck auch zusätzliche Funktionen hinzu :

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

Du kannst tun

import scalaz.Scalaz._

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

Der schnellste und einfachste Weg:

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

Auf diese Weise wird jedes Element sofort zur Karte hinzugefügt.

Der zweite ++Weg ist:

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

Im Gegensatz zum ersten Weg wird auf zweite Weise für jedes Element in einer zweiten Karte eine neue Liste erstellt und mit der vorherigen Karte verknüpft.

Der caseAusdruck erstellt implizit eine neue Liste mit der unapplyMethode.

Alexey Kudryashov
quelle
1

Das habe ich mir ausgedacht ...

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
quelle
1

Mit dem Typklassenmuster können wir jeden numerischen Typ zusammenführen:

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

Verwendung:

import MapSyntax.MapOps

map1 plus map2

Zusammenführen einer Folge von Karten:

maps.reduce(_ plus _)
Tomer Sela
quelle
0

Ich habe eine kleine Funktion, um die Arbeit zu erledigen. Sie befindet sich in meiner kleinen Bibliothek für einige häufig verwendete Funktionen, die nicht in der Standardbibliothek enthalten sind. Es sollte für alle Arten von Karten funktionieren, veränderlich und unveränderlich, nicht nur für HashMaps

Hier ist die Verwendung

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

Und hier ist der Körper

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

Eugene Platonov
quelle