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.
map1 ++ map2
Antworten:
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:
Insbesondere
Map[K, V]
kombiniert der Binäroperator für die Schlüssel der Karten und faltetV
den Halbgruppenoperator über alle doppelten Werte. Die Standard-Halbgruppe fürInt
verwendet 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ür
Map[K, V]
genau dann, wenn eine Halbgruppe fürV
existiert -V
die Halbgruppe wird verwendet, um die Werte aus zwei Karten zu kombinieren, die demselben Schlüssel zugeordnet sind.Also, weil
Int
hier 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. Siemap1 |+| map2
unterscheidet sich also vonmap2 |+| map1
der Zeichenfolge , aber nicht von Int.)quelle
scalaz
es Sinn machte.A
undOption[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 ...Die kürzeste mir bekannte Antwort, die nur die Standardbibliothek verwendet, ist
quelle
++
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)
for
Karte1 ++ (für ((k, v) <- map2) ergibt k -> (v + map1.getOrElse (k, 0) ))).
hat eine höhere Priorität als++
; du liestmap1 ++ map2.map{...}
alsmap1 ++ (map2 map {...})
. Auf die eine Weise ordnen Sie diemap1
Elemente zu und auf die andere Weise nicht.Schnelle Lösung:
quelle
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.
Auch in Scaladoc erwähnt das
quelle
MergeFunction
.private type MergeFunction[A1, B1] = ((A1, B1), (A1, B1)) => (A1, B1)
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.
Die kartenbasierte Implementierung des Monoid-Merkmals, bei dem zwei Karten zusammengeführt werden.
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.
quelle
quelle
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:
quelle
Sie können das auch mit Katzen tun .
quelle
import cats.implicits._
. Importieren Sieimport cats.instances.map._ import cats.instances.int._ import cats.syntax.semigroup._
nicht viel ausführlicher ...import cats.implicits._
Zu Beginn
Scala 2.13
besteht eine andere Lösung, die nur auf der Standardbibliothek basiert, darin, dengroupBy
Teil Ihrer Lösung zu ersetzen, durch dengroupMapReduce
(wie der Name schon sagt) eingroupBy
nachfolgendermapValues
und ein reduzierter Schritt entspricht:Dies:
Verkettet die beiden Karten als Folge von Tupeln (
List((1,9), (2,20), (1,100), (3,300))
). Aus Gründen der Übersichtlichkeitmap2
wird implizit in konvertiert,Seq
um sich an den Typ von anzupassen.map1.toSeq
Sie können ihn jedoch auch explizit festlegenmap2.toSeq
, indem Sie Folgendes verwenden :group
s Elemente basierend auf ihrem ersten Tupelteil (Gruppenteil der Gruppe MapReduce),map
s gruppierte Werte zu ihrem zweiten Tupelteil (Kartenteil der Gruppe Map Reduce),reduce
s_+_
Zuordnen von Werten ( ) durch Summieren (Reduzieren eines Teils von groupMap Reduce ).quelle
Folgendes habe ich letztendlich verwendet:
quelle
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
Map
diesem 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
quelle
Der schnellste und einfachste Weg:
Auf diese Weise wird jedes Element sofort zur Karte hinzugefügt.
Der zweite
++
Weg ist: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
case
Ausdruck erstellt implizit eine neue Liste mit derunapply
Methode.quelle
Das habe ich mir ausgedacht ...
quelle
Mit dem Typklassenmuster können wir jeden numerischen Typ zusammenführen:
Verwendung:
Zusammenführen einer Folge von Karten:
quelle
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
https://github.com/jozic/scalax-collection/blob/master/README.md#mergedwith
Und hier ist der Körper
https://github.com/jozic/scalax-collection/blob/master/src%2Fmain%2Fscala%2Fcom%2Fdaodecode%2Fscalax%2Fcollection%2Fextensions%2Fpackage.scala#L190
quelle