webentwicklung-frage-antwort-db.com.de

Bester Weg, zwei Karten zusammenzuführen und die Werte des gleichen Schlüssels zusammenzufassen?

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

Ich möchte aber wissen, ob es bessere Lösungen gibt.

154
Freewind

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

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 kombiniert der Binäroperator für Map[K, V] die Schlüssel der Maps, wobei der Semigroup-Operator von V über doppelt vorhandene Werte gefaltet wird. Die Standard-Halbgruppe für Int verwendet den Additionsoperator. Sie erhalten also die Summe der Werte für jeden doppelten Schlüssel.

Edit: Etwas detaillierter, wie in der Anfrage von user482745.

Mathematisch ist eine Semigroup nur eine Menge von Werten zusammen mit einem Operator, der zwei Werte aus dieser Menge entnimmt und einen anderen Wert aus dieser Menge erzeugt. Ganzzahlen unter Addition sind zum Beispiel eine Halbgruppe - der +-Operator kombiniert zwei Ints zu einem anderen Int.

Sie können auch eine Halbgruppe über den Satz "Alle Maps mit einem bestimmten Schlüsseltyp und Werttyp" definieren, sofern Sie einige Operationen ausführen können, bei denen zwei Maps kombiniert werden, um eine neue zu erstellen, die irgendwie die Kombination der beiden ist Eingänge.

Wenn in beiden Karten keine Schlüssel angezeigt werden, 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 gibt es in Scalaz genau dann eine Halbgruppe für Map[K, V], wenn eine Halbgruppe für V vorhanden ist - Vs Halbgruppe wird verwendet, um die Werte von zwei Karten zu kombinieren, die demselben Schlüssel zugewiesen sind.

Da hier Int der Werttyp ist, wird die "Kollision" auf dem 1-Schlüssel durch Addition der beiden zugeordneten Werte durch Integer aufgelöst (wie es der Int-Semigroup-Operator tut), also 100 + 9. Wenn die Werte Strings gewesen wären, hätte eine Kollision zu einer String-Verkettung der zwei zugeordneten Werte geführt (wiederum, weil dies der Semergruppenoperator für String ist).

(Und interessanterweise ist, da die String-Verkettung nicht kommutativ ist, d. H. "a" + "b" != "b" + "a", auch die resultierende Halbgruppenoperation nicht der Fall. Daher unterscheidet sich map1 |+| map2 von map2 |+| map1 im String-Fall, jedoch nicht im Int-Fall.

138
Andrzej Doyle

Die kürzeste Antwort, die ich kenne, verwendet nur die Standardbibliothek

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

Schnelle Lösung:

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

Nun, jetzt in der Scala-Bibliothek (zumindest in 2.10) gibt es etwas, was Sie wollten - zusammengeführt Funktion. ABER es wird nur in HashMap dargestellt, nicht in Map. Es ist etwas verwirrend. Auch die Signatur ist mühsam - ich kann mir nicht vorstellen, warum ich einen Schlüssel zweimal brauche und wann ich ein Paar mit einem anderen Schlüssel produzieren müsste. Aber es funktioniert und viel sauberer als bisherige "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 hat das erwähnt

Die merged-Methode ist im Durchschnitt performanter als eine Durchqueren und Rekonstruieren einer neuen unveränderlichen Hash-Karte aus Scratch oder ++.

37

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

// Monoid trait

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

Die auf Karten basierende Implementierung der Eigenschaft Monoid, die zwei Karten zusammenführt.

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 eine Liste von Karten haben, die zusammengeführt werden müssen (in diesem Fall nur 2), können Sie dies wie folgt tun.

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

Ich habe einen Blog-Post darüber geschrieben, schaut mal rein:

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

im Grunde können Sie dies mit der scalaz semi-Gruppe ganz leicht erreichen

würde ungefähr so ​​aussehen:

  import scalaz.Scalaz._
  map1 |+| map2
5
Nimrod007
map1 ++ ( for ( (k,v) <- map2 ) yield ( k -> ( v + map1.getOrElse(k,0) ) ) )
5
AmigoNico

Das geht auch mit Cats .

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

Die Antwort von Andrzej Doyle enthält eine großartige Erläuterung von Halbgruppen, mit der Sie mit dem |+|-Operator zwei Karten verknüpfen und die Werte für übereinstimmende Schlüssel summieren können.

Es gibt viele Möglichkeiten, etwas als Instanz einer Typklasse zu definieren, und im Gegensatz zum OP möchten Sie Ihre Schlüssel möglicherweise nicht speziell summieren. Oder Sie möchten eher eine Vereinigung als eine Kreuzung durchführen. Scalaz fügt Map zu diesem Zweck 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-SAPSHOT-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
2
user1158559

Dies ist, was ich mit ...

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
}
1
kaur

Ab Scala 2.13 besteht eine weitere Lösung, die nur auf der Standardbibliothek basiert, darin, den groupBy-Teil Ihrer Lösung durch groupMapReduce zu ersetzen, der (wie der Name schon sagt) einem groupBy entspricht, gefolgt von mapValues und einem Reduzierungsschritt:

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

Diese:

  • verkettet die beiden Karten als Folge von Tupeln (List((1,9), (2,20), (1,100), (3,300)))

  • groups Elemente basierend auf ihrem ersten Tuple-Teil (Gruppenteil von group MapReduce)

  • maps gruppierte Werte zu ihrem zweiten Tuple-Teil (Kartenteil von Gruppe Map Reduce

  • reduces zugeordnete Werte (_+_) durch Summieren (Reduzieren eines Teils der groupMap Reduzieren)

0
Xavier Guihot

Ich habe eine kleine Funktion, die den Job erledigt, sie befindet sich in meiner kleinen Bibliothek für einige häufig verwendete Funktionen, die nicht in der Standardlib. Lib enthalten sind, und sollte für alle Kartentypen 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

0
Eugene Platonov

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 zur ersten Methode wird auf eine zweite Weise für jedes Element in einer zweiten Map eine neue Liste erstellt und mit der vorherigen Map verkettet.

Der Ausdruck case erstellt implizit eine neue Liste mit der Methode unapply.

0

Folgendes habe ich letztendlich verwendet:

(a.toSeq ++ b.toSeq).groupBy(_._1).mapValues(_.map(_._2).sum)
0
user1084563