Лучший способ объединить две карты и суммировать значения одного и того же ключа?

Question

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

Я хочу объединить их и суммировать значения тех же ключей.Таким образом, результат будет:

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

Теперь у меня есть 2 решения:

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

и

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

Но я хочу знать, есть ли какие-нибудь лучшерешения.

Answer 1

Scalaz имеет концепцию Полугруппа , которая фиксирует то, что вы хотите здесь сделать, и приводит, возможно, к кратчайшему / чистому решению:

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)

В частности, бинарный оператор для Map[K, V] объединяет ключи карт, складывая оператор полугруппы V по любым дублирующимся значениям. Стандартная полугруппа для Int использует оператор сложения, поэтому вы получаете сумму значений для каждого дублирующего ключа.

Редактировать : немного больше деталей, согласно запросу пользователя 482745.

Математически полугруппа - это просто набор значений вместе с оператором, который принимает два значения из этого набора и создает другое значение из этого набора. Таким образом, при добавлении целые числа представляют собой полугруппу, например - оператор + объединяет два целых числа для создания другого целого числа.

Вы также можете определить полугруппу по набору «всех карт с заданным типом ключа и типом значения», при условии, что вы можете придумать некоторую операцию, которая объединяет две карты, чтобы создать новую, которая каким-то образом является комбинацией из двух входов.

Если на обеих картах нет клавиш, это тривиально. Если один и тот же ключ существует на обеих картах, то нам нужно объединить два значения, на которые отображается ключ. Хм, разве мы не описали оператор, который объединяет два объекта одного типа? Вот почему в Scalaz полугруппа для Map[K, V] существует тогда и только тогда, когда существует полугруппа для V - полугруппа V используется для объединения значений из двух карт, которые назначены одному и тому же ключу.

Так как Int является здесь типом значения, «коллизия» на ключе 1 разрешается путем целочисленного сложения двух отображенных значений (как это делает оператор полугруппы Int), следовательно, 100 + 9. Если бы значения были Strings, коллизия привела бы к объединению строк двух сопоставленных значений (опять же, потому что это то, что делает оператор полугруппы для String).

(И что интересно, поскольку конкатенация строк не является коммутативной, то есть "a" + "b" != "b" + "a", результирующая операция полугруппы также не является. Поэтому map1 |+| map2 отличается от map2 |+| map1 в случае String, но не в Int случай.)

Answer 2

Самый короткий из известных мне ответов, использующий только стандартную библиотеку, -

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

Answer 3

Быстрое решение:

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

Answer 4

Ну, теперь в библиотеке Scala (по крайней мере, в 2.10) есть то, что вы хотели - объединенная функция. НО он представлен только в HashMap, а не в Map. Это несколько сбивает с толку. Кроме того, подпись громоздка - не могу представить, зачем мне дважды нужен ключ и когда мне нужно создать пару с другим ключом. Но, тем не менее, он работает и намного чище, чем предыдущие «родные» решения.

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

Также в скаладоке упоминается, что

Метод merged в среднем более производительный, чем выполнение Обход и восстановление новой неизменной хэш-карты из царапина, или ++.

Answer 5

Это может быть реализовано как Моноид с простым Scala.Вот пример реализации.При таком подходе мы можем объединить не только 2, но и список карт.

// Monoid trait

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

Реализация черты Monoid на основе карт, которая объединяет две карты.

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
}

Теперь,если у вас есть список карт, которые необходимо объединить (в данном случае только 2), это можно сделать, как показано ниже.

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)

Answer 6

Вы также можете сделать это с Кошками .

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)

Answer 7

Я написал в блоге об этом, зацените:

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

В основном, используя полугруппу скалазов, вы можете достичь этого довольно легко

будет выглядеть примерно так:

  import scalaz.Scalaz._
  map1 |+| map2

Answer 8

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

Answer 9

Начиная с Scala 2.13, другое решение, основанное только на стандартной библиотеке, состоит в замене части groupBy вашего решения на groupMapReduce, что (как следует из названия) эквивалентно groupBy, затем mapValues и шаг сокращения:

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

Это:

• Объединяет две карты в виде последовательности кортежей (List((1,9), (2,20), (1,100), (3,300))). Для краткости map2 неявно преобразуется в Seq для адаптации к типу map1.toSeq - но вы можете сделать это явным, используя map2.toSeq,

• group s элементов на основе их первой части кортежа (групповая часть group MapReduce),

• map s сгруппированные значения для их второй части кортежа (часть карты группы Map Reduce),

• reduce s сопоставленных значений (_+_) путем их суммирования (уменьшить часть groupMap Reduce ).

Answer 10

Самый быстрый и простой способ:

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

Таким образом, каждый элемент немедленно добавляется на карту.

Второй ++ способ:

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

В отличие от первого способа, во втором способе для каждого элемента на второй карте будет создан новый список и присоединен к предыдущей карте.

Выражение case неявно создает новый список с использованием unapply метод.