Scala: wie eine Sammlung von Karten fusionieren

Question

Ich habe eine Liste des Map [String, Double], und ich mag ihren Inhalt in eine einzige Map [String, Double] verschmelzen. Wie soll ich tun dies in einer idiomatischen Weg? Ich stelle mir vor, dass ich im Stande sein sollte dies mit einer Falte zu tun. So etwas wie:

val newMap = Map[String, Double]() /: listOfMaps { (accumulator, m) => ... }

Darüber hinaus würde Ich mag zu den wichtigsten Kollisionen in allgemeiner Weise behandeln. Das heißt, wenn ich einen Schlüssel zu der Karte hinzuzufügen, die bereits vorhanden ist, soll ich in der Lage sein, eine Funktion angeben, die eine Doppel (in diesem Fall) zurückgibt und den vorhandenen Wert für diesen Schlüssel sowie den Wert Ich versuche hinzufügen . Wenn der Schlüssel noch nicht in der Karte vorhanden ist, dann fügen Sie einfach es und sein Wert unverändert.

In meinem speziellen Fall würde Ich mag eine einzelne Map [String, Double] so bauen, dass, wenn die Karte bereits einen Schlüssel enthält, dann wird das doppelt auf den vorhandenen Kartenwert hinzugefügt werden.

Ich arbeite mit veränderbaren Karten in meinem speziellen Code, aber ich bin daran interessiert, mehr generische Lösungen, wenn möglich.

Answer 1

Wie wäre es dieses:

def mergeMap[A, B](ms: List[Map[A, B]])(f: (B, B) => B): Map[A, B] =
  (Map[A, B]() /: (for (m <- ms; kv <- m) yield kv)) { (a, kv) =>
    a + (if (a.contains(kv._1)) kv._1 -> f(a(kv._1), kv._2) else kv)
  }

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
val mm = mergeMap(ms)((v1, v2) => v1 + v2)

println(mm) // prints Map(hello -> 5.5, world -> 2.2, goodbye -> 3.3)

Und es funktioniert sowohl in 2.7.5 und 2.8.0.

Answer 2

Nun, Sie tun können:

mapList reduce (_ ++ _)

mit Ausnahme der speziellen Anforderung für eine Kollision.

Da Sie diese spezielle Anforderung tun haben, vielleicht die besten etwas so sein würde tun (2.8):

def combine(m1: Map, m2: Map): Map = {
  val k1 = Set(m1.keysIterator.toList: _*)
  val k2 = Set(m2.keysIterator.toList: _*)
  val intersection = k1 & k2

  val r1 = for(key <- intersection) yield (key -> (m1(key) + m2(key)))
  val r2 = m1.filterKeys(!intersection.contains(_)) ++ m2.filterKeys(!intersection.contains(_)) 
  r2 ++ r1
}

Sie können dann diese Methode auf die Karte Klasse durch das Muster Pimp My Library hinzufügen, und es in dem ursprünglichen Beispiel anstelle von „++“:

class CombiningMap(m1: Map[Symbol, Double]) {
  def combine(m2: Map[Symbol, Double]) = {
    val k1 = Set(m1.keysIterator.toList: _*)
    val k2 = Set(m2.keysIterator.toList: _*)
    val intersection = k1 & k2
    val r1 = for(key <- intersection) yield (key -> (m1(key) + m2(key)))
    val r2 = m1.filterKeys(!intersection.contains(_)) ++ m2.filterKeys(!intersection.contains(_))
    r2 ++ r1
  }
}

// Then use this:
implicit def toCombining(m: Map[Symbol, Double]) = new CombiningMap(m)

// And finish with:
mapList reduce (_ combine _)

Während dies in 2.8 geschrieben wurde, so keysIterator wird keys für 2,7, filterKeys muß möglicherweise in Bezug auf filter und map geschrieben werden, & ** wird, und so weiter, es sollte nicht zu unterschiedlich sein.

Answer 3

Ich bin überrascht, die niemand mit dieser Lösung kommt noch:

myListOfMaps.flatten.toMap

Ist genau das, was Sie brauchen:

1. Führt die Liste auf eine einzige Karte
2. Weeds heraus irgendwelche Nachschlüssel

Beispiel:

scala> List(Map('a -> 1), Map('b -> 2), Map('c -> 3), Map('a -> 4, 'b -> 5)).flatten.toMap
res7: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 4, 'b -> 5, 'c -> 3)

flatten die Liste der Karten in eine flache Liste von Tupeln dreht, toMap dreht die Liste von Tupeln in eine Karte mit allen Nachschlüssel entfernt

Answer 4

ich lesen diese Frage schnell, damit ich nicht sicher bin, ob ich etwas fehlt (wie es hat für 2.7.x oder ohne scalaz arbeiten):

import scalaz._
import Scalaz._
val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms.reduceLeft(_ |+| _)
// returns Map(goodbye -> 3.3, hello -> 5.5, world -> 2.2)

Sie können die Monoid Definition für Double ändern und eine andere Art und Weise erhalten, die Werte zu akkumulieren, hier den max bekommen:

implicit val dbsg: Semigroup[Double] = semigroup((a,b) => math.max(a,b))
ms.reduceLeft(_ |+| _)
// returns Map(goodbye -> 3.3, hello -> 4.4, world -> 2.2)

Answer 5

Interessant, noodling um mit diesem ein wenig, ich habe folgendes (auf 2.7.5):

Allgemeine Karten:

   def mergeMaps[A,B](collisionFunc: (B,B) => B)(listOfMaps: Seq[scala.collection.Map[A,B]]): Map[A, B] = {
    listOfMaps.foldLeft(Map[A, B]()) { (m, s) =>
      Map(
        s.projection.map { pair =>
        if (m contains pair._1)
          (pair._1, collisionFunc(m(pair._1), pair._2))
        else
          pair
      }.force.toList:_*)
    }
  }

Aber der Mensch, der mit dem Vorsprung scheußlich ist und zwingt und ToList und so weiter. Separate Frage: Was ist eine bessere Art und Weise mit, dass innerhalb der Falte zu behandeln

Für veränderbare Karten, das ist, was ich zu tun habe mit in meinem Code, und mit einer weniger allgemeinen Lösung, ich habe dies:

def mergeMaps[A,B](collisionFunc: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A, B] = {
    listOfMaps.foldLeft(mutable.Map[A,B]()) {
      (m, s) =>
      for (k <- s.keys) {
        if (m contains k)
          m(k) = collisionFunc(m(k), s(k))
        else
          m(k) = s(k)
      }
      m
    }
  }

Das scheint ein wenig saubere, aber nur mit veränderbaren Karten arbeitet, wie es geschrieben ist. Interessanterweise habe ich versucht, zuerst die oben (bevor ich die Frage gestellt) unter Verwendung von /: statt foldLeft, aber ich war Typ Fehler zu bekommen. Ich dachte, /: und foldLeft war im Grunde gleichwertig, aber der Compiler gehalten beschweren, dass ich explizite Typen für (m, n) benötigt. Was ist mit dem oben?

Answer 6

ich eine Blog-Post über das geschrieben habe, check it out:

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

im Grunde scalaz halb Gruppe verwenden, können Sie diese ziemlich leicht

erreichen

würde in etwa so aussehen:

  import scalaz.Scalaz._
  listOfMaps reduce(_ |+| _)

Answer 7

Starten Scala 2.13, eine andere Lösung, die Nachschlüssel Griffe und ist nur auf der Basis der Standardbibliothek besteht die Maps als Sequenzen (flatten) bei der Zusammenführung vor der neuen Anwendung groupMapReduce Bediener die (wie der Name schon sagt) ist ein Äquivalent eines groupBy durch eine Abbildung und eine Verringerung Schritt der gruppierten Werte gefolgt:

List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
  .flatten
  .groupMapReduce(_._1)(_._2)(_ + _)
// Map("world" -> 2.2, "goodbye" -> 3.3, "hello" -> 5.5)

Dieses:

• flattens (verkettet) werden die Karten als Folge von Tupeln (List(("hello", 1.1), ("world", 2.2), ("goodbye", 3.3), ("hello", 4.4))), die alle Schlüssel / Wert hält (auch Schlüssel duplizieren)

• groups Elemente basierend auf ihrem ersten Teil tuple (_._1) (Gruppe Teil group MapReduce)

• maps gruppierten Werte zu ihrem zweiten Tupel Teil (_._2) (Karte zur Gruppe Karte Verkleinern)

• reduces abgebildet gruppiert Werte (_+_) durch ihre Summe nehmen (aber es kann jede reduce: (T, T) => T Funktion sein) (reduzieren Teil groupMap reduzieren )

---

Der groupMapReduce Schritt als One-Pass-Version äquivalent:

list.groupBy(_._1).mapValues(_.map(_._2).reduce(_ + _))

Answer 8

ein oneliner Helfer-funk, deren Nutzung fast so sauber liest scalaz wie mit:

def mergeMaps[K,V](m1: Map[K,V], m2: Map[K,V])(f: (V,V) => V): Map[K,V] =
    (m1 -- m2.keySet) ++ (m2 -- m1.keySet) ++ (for (k <- m1.keySet & m2.keySet) yield { k -> f(m1(k), m2(k)) })

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms.reduceLeft(mergeMaps(_,_)(_ + _))
// returns Map(goodbye -> 3.3, hello -> 5.5, world -> 2.2)

für ultimative Lesbarkeit es in einem impliziten benutzerdefinierten Typ wickeln:

class MyMap[K,V](m1: Map[K,V]) {
    def merge(m2: Map[K,V])(f: (V,V) => V) =
    (m1 -- m2.keySet) ++ (m2 -- m1.keySet) ++ (for (k <- m1.keySet & m2.keySet) yield { k -> f(m1(k), m2(k)) })
}
implicit def toMyMap[K,V](m: Map[K,V]) = new MyMap(m)

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms reduceLeft { _.merge(_)(_ + _) }