Najlepszy sposób na połączenie dwóch map i zsumowanie wartości tego samego klucza?

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

Chcę je scalić i zsumować wartości tych samych kluczy. Wynik będzie więc:

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

Teraz mam 2 rozwiązania:

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

i

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

Ale chcę wiedzieć, czy istnieją lepsze rozwiązania.

Scalaz ma koncepcję półgrupy, która przechwytuje to, co chcesz tutaj zrobić, i prowadzi do prawdopodobnie najkrótszego / najczystszego rozwiązania:

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)

W szczególności, operator binarny for Map[K, V]łączy klucze map, Vzawijając operator półgrupy nad zduplikowanymi wartościami. Standardowa półgrupa dla Intużywa operatora dodawania, więc otrzymujesz sumę wartości dla każdego zduplikowanego klucza.

Edycja : trochę więcej szczegółów, zgodnie z prośbą użytkownika482745.

Matematycznie półgrupa to po prostu zbiór wartości wraz z operatorem, który pobiera dwie wartości z tego zbioru i tworzy inną wartość z tego zbioru. Na przykład liczby całkowite są półgrupą - +operator łączy dwie liczby całkowite, aby utworzyć kolejną liczbę int.

Możesz także zdefiniowaćpółgrupę na zbiorze "wszystkich map z podanym typem klucza i typem wartości", o ile możesz wymyślić jakąś operację, która łączy dwie mapy w celu utworzenia nowej, która jest w jakiś sposób połączeniem tych dwóch wejścia.

Jeśli nie ma kluczy, które pojawiają się na obu mapach, jest to trywialne. Jeśli ten sam klucz istnieje w obu mapach, musimy połączyć dwie wartości, na które mapuje klucz. Hmm, czy nie opisaliśmy właśnie operatora, który łączy dwie jednostki tego samego typu? Dlatego w Scalaz półgrupa for Map[K, V]istnieje wtedy i tylko wtedy, gdy półgrupa dla Vistnieje - Vjest używana do łączenia wartości z dwóch map, które są przypisane do tego samego klucza.

Tak więc, ponieważ Intjest to typ wartości, "kolizja" 1klucza jest rozwiązywana przez dodanie liczb całkowitych dwóch odwzorowanych wartości (tak jak robi to operator półgrupy Int) 100 + 9. Gdyby wartości były ciągami, kolizja spowodowałaby konkatenację ciągów dwóch odwzorowanych wartości (ponownie, ponieważ tak robi operator półgrupy dla ciągu).

(Co ciekawe, ponieważ konkatenacja ciągów nie jest przemienna - to znaczy "a" + "b" != "b" + "a"- wynikowa operacja półgrupowa też nie jest. Więc map1 |+| map2różni się od map2 |+| map1przypadku String, ale nie w przypadku Int).

Najkrótszą odpowiedzią, jaką znam, wykorzystującą tylko bibliotekę standardową, jest

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

Szybkie rozwiązanie:

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

Cóż, teraz w bibliotece scala (przynajmniej w 2.10) jest coś, czego chciałeś - funkcja scalona . ALE jest prezentowany tylko w HashMap, a nie w Mapie. To trochę zagmatwane. Również podpis jest nieporęczny - nie wyobrażam sobie, dlaczego potrzebowałbym klucza dwa razy i kiedy musiałbym stworzyć parę z innym kluczem. Niemniej jednak działa i jest znacznie czystszy niż poprzednie rozwiązania „natywne”.

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

Wspomniał o tym również w scaladoc

Ta mergedmetoda jest średnio wydajniejsza niż wykonywanie przemierzania i rekonstruowanie nowej niezmiennej mapy skrótów od zera lub ++.

Można to zaimplementować jako Monoid za pomocą zwykłej Scali. Oto przykładowa implementacja. Dzięki takiemu podejściu możemy połączyć nie tylko 2, ale także listę map.

// Monoid trait

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

Oparta na mapie implementacja cechy Monoid, która łączy dwie mapy.

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
}

Teraz, jeśli masz listę map do scalenia (w tym przypadku tylko 2), możesz to zrobić jak poniżej.

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)

map1 ++ ( for ( (k,v) <- map2 ) yield ( k -> ( v + map1.getOrElse(k,0) ) ) )

Napisałem o tym post na blogu, sprawdź to:

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

w zasadzie używając półgrupy scalaz możesz to osiągnąć całkiem łatwo

wyglądałoby mniej więcej tak:

  import scalaz.Scalaz._
  map1 |+| map2

Możesz to również zrobić z kotami .

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)

Zaczynając od Scala 2.13innego rozwiązania opartego wyłącznie na standardowej bibliotece, polega na zamianie groupByczęści rozwiązania, groupMapReducektórą (jak sama nazwa wskazuje) jest odpowiednikiem kroku groupBypo którym następuje mapValuesi redukuje:

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

To:

• Łączy dwie mapy jako sekwencję krotek ( List((1,9), (2,20), (1,100), (3,300))). Dla zwięzłości, map2jest niejawnie konwertowany na, Seqaby dostosować się do typu map1.toSeq- ale możesz zdecydować się na jawne użycie map2.toSeq,

• groups elementy na podstawie ich pierwszej części krotki (część grupowa grupy MapReduce),

• maps zgrupowane wartości do drugiej części krotki (część mapy grupy Map Reduce),

• reduces zmapowane wartości ( _+_), sumując je (zmniejsz część groupMap Reduce ).

Oto, czego ostatecznie użyłem:

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

Odpowiedź Andrzeja Doyle'a zawiera świetne wyjaśnienie półgrup, które pozwala na użycie |+|operatora do połączenia dwóch map i zsumowania wartości pasujących kluczy.

Istnieje wiele sposobów zdefiniowania czegoś jako instancji typeklasy iw przeciwieństwie do OP, możesz nie chcieć konkretnie sumować kluczy. Lub możesz chcieć działać na związku, a nie na skrzyżowaniu. Scalaz dodaje również dodatkowe funkcje Mapw tym celu:

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

Możesz to zrobić

import scalaz.Scalaz._

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

Najszybszy i najprostszy sposób:

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

W ten sposób każdy element jest natychmiast dodawany do mapy.

Drugi ++sposób to:

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

W przeciwieństwie do pierwszego sposobu, w drugim przypadku dla każdego elementu na drugiej mapie zostanie utworzona nowa lista i połączona z poprzednią mapą.

caseWyrażenie niejawnie tworzy nową listę używając unapplymetody.

Oto, co wymyśliłem ...

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
}

Używając wzorca typeklas, możemy scalić dowolny typ numeryczny:

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

Stosowanie:

import MapSyntax.MapOps

map1 plus map2

Scalanie sekwencji map:

maps.reduce(_ plus _)

Mam małą funkcję do wykonania tego zadania, która znajduje się w mojej małej bibliotece dla niektórych często używanych funkcji, których nie ma w standardowej bibliotece. Powinien działać dla wszystkich typów map, zmiennych i niezmiennych, nie tylko HashMaps

Oto użycie

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

A oto ciało

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