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

179
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.

Freewind
źródło
Najłatwiej jestmap1 ++ map2
Seraf
3
@Seraf To właściwie po prostu „łączy” mapy, ignorując duplikaty zamiast sumować ich wartości.
Zeynep Akkalyoncu Yilmaz
@ZeynepAkkalyoncuYilmaz po prawej powinienem był przeczytać pytanie lepiej, odchodzi ze wstydu
Seraf

Odpowiedzi:

143

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

Andrzej Doyle
źródło
37
Znakomity! Pierwszy praktyczny przykład, który scalazmiał sens.
soc
5
Bez żartów! Jeśli zaczniesz go szukać ... to jest wszędzie. Cytując Errica Torrebone, autora specyfikacji i specyfikacji2: "Najpierw uczysz się Option i zaczynasz ją widzieć wszędzie. Potem uczysz się Applicative i to to samo. Dalej?" Dalej są jeszcze bardziej funkcjonalne koncepcje. A to bardzo pomaga w uporządkowaniu kodu i ładnym rozwiązywaniu problemów.
AndreasScheinert
4
Właściwie szukałem Option przez pięć lat, kiedy w końcu znalazłem Scalę. Różnica między odwołaniem do obiektu Java, które może być zerowe, a takim, którego nie może być (tj. Między Ai Option[A]) jest tak ogromna, że ​​nie mogłem uwierzyć, że są naprawdę tego samego typu. I tak rozpoczęła się patrząc na Scalaz. Nie jestem pewien, czy jestem wystarczająco sprytny ...
Malvolio,
1
Istnieje również opcja dla języka Java, patrz Funkcjonalna Java. Nie bój się, nauka jest fajna. A programowanie funkcjonalne nie uczy (tylko) nowych rzeczy, ale zamiast tego oferuje programiście pomoc w dostarczaniu terminów i słownictwa potrzebnego do rozwiązywania problemów. Pytanie OP jest doskonałym przykładem. Koncepcja półgrupy jest tak prosta, że ​​używasz jej na co dzień, np. Do Strings. Prawdziwa moc pojawia się, jeśli zidentyfikujesz tę abstrakcję, nazwij ją i ostatecznie zastosujesz do innych typów, a następnie po prostu String.
AndreasScheinert
1
Jak to możliwe, że spowoduje to 1 -> (100 + 9)? Czy możesz mi pokazać „ślad stosu”? Dzięki. PS: Proszę tutaj o wyjaśnienie odpowiedzi.
user482745
152

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

map1 ++ map2.map{ case (k,v) => k -> (v + map1.getOrElse(k,0)) }
Rex Kerr
źródło
34
Niezłe rozwiązanie. Lubię dodać wskazówkę, która ++zamienia dowolne (k, v) z mapy po lewej stronie ++(tutaj mapa1) na (k, v) z prawej strony, jeśli (k, _) już istnieje po lewej stronie mapa boczna (tutaj mapa1), np.Map(1->1) ++ Map(1->2) results in Map(1->2)
Lutz
Rodzaj ładniejszej wersji: for ((k, v) <- (aa ++ bb)) yield k -> (if ((aa zawiera k) && (bb zawiera k)) aa (k) + v else v)
dividebyzero
Wcześniej zrobiłem coś innego, ale tutaj jest wersja tego, co zrobiłeś, zastępując mapę formapą1 ++ (for ((k, v) <- map2) yield k -> (v + map1.getOrElse (k, 0 )))
dividebyzero
1
@ Jus12 - No. .ma wyższy priorytet niż ++; czytasz map1 ++ map2.map{...}jako map1 ++ (map2 map {...}). Tak więc w jeden sposób map1mapujesz elementy, a w drugi nie.
Rex Kerr
1
@matt - Scalaz już to zrobi, więc powiedziałbym "istniejąca biblioteka już to robi".
Rex Kerr
48

Szybkie rozwiązanie:

(map1.keySet ++ map2.keySet).map {i=> (i,map1.getOrElse(i,0) + map2.getOrElse(i,0))}.toMap
Matthew Farwell
źródło
41

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 ++.

Michaił Golubtsov
źródło
1
W tej chwili jest tylko w niezmiennej Hashmapie, a nie w zmiennej Hashmapie.
Kevin Wheeler
2
To dość denerwujące, że mają to tylko dla HashMaps, aby być uczciwym.
Johan S
Nie mogę tego skompilować, wygląda na to, że typ, który akceptuje, jest prywatny, więc nie mogę przekazać wpisanej funkcji, która pasuje.
Ryan The Leach,
2
Wygląda na to, że coś się zmieniło w wersji 2.11. Sprawdź 2.10 scaladoc - scala-lang.org/api/2.10.1/… Jest to zwykła funkcja. Ale w 2.11 to jest MergeFunction.
Michaił Golubtsov
Wszystko, co zmieniło się w 2.11, to wprowadzenie aliasu typu dla tego konkretnego typu funkcjiprivate type MergeFunction[A1, B1] = ((A1, B1), (A1, B1)) => (A1, B1)
EthanP
14

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)
Jegan
źródło
5
map1 ++ ( for ( (k,v) <- map2 ) yield ( k -> ( v + map1.getOrElse(k,0) ) ) )
AmigoNico
źródło
5

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
Nimrod007
źródło
11
Musisz podać więcej szczegółów w swojej odpowiedzi, najlepiej kod implementacji. Zrób to również dla innych podobnych odpowiedzi, które opublikowałeś, i dostosuj każdą odpowiedź do konkretnego pytania, które zostało zadane. Praktyczna zasada: osoba pytająca powinna mieć możliwość skorzystania z Twojej odpowiedzi bez klikania linku do bloga.
Robert Harvey
5

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)
Artsiom Miklushou
źródło
EEK, import cats.implicits._. Importuj import cats.instances.map._ import cats.instances.int._ import cats.syntax.semigroup._niewiele więcej informacji ...
Święty Antario,
@ St.Antario to właściwie zalecany sposób, aby mieć tylkoimport cats.implicits._
Artsiom Miklushou
Polecony przez kogo? Wprowadzenie wszystkich (z których większość jest nieużywanych) niejawnych wystąpień do zakresu komplikuje życie kompilatora. A poza tym, jeśli nie potrzeba, powiedzmy, instancji aplikacyjnej, dlaczego mieliby ją tam przynosić?
Święty Antario
4

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

Xavier Guihot
źródło
3

Oto, czego ostatecznie użyłem:

(a.toSeq ++ b.toSeq).groupBy(_._1).mapValues(_.map(_._2).sum)
user1084563
źródło
1
To naprawdę niewiele różni się od pierwszego rozwiązania zaproponowanego przez PO.
jwvh
2

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
user1158559
źródło
2

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.

Alexey Kudryashov
źródło
1

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
}
kaur
źródło
1

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 _)
Tomer Sela
źródło
0

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

Eugene Platonov
źródło