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

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

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

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

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

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

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

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

Что ж, теперь в библиотеке 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метод в среднем более производительный, чем обход и восстановление новой неизменяемой хэш-карты с нуля, или ++.

Это может быть реализовано как Monoid с простым 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)

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

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

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

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

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

  import scalaz.Scalaz._
  map1 |+| map2

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

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)

Запуск 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элементы, основанные на их первой части кортежа (групповая часть группы MapReduce),

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

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

Вот что я в итоге использовал:

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

Ответ Анджея Дойла содержит отличное объяснение полугрупп, которое позволяет использовать |+|оператор для объединения двух карт и суммирования значений для соответствующих ключей.

Существует множество способов определить, что что-то является экземпляром класса типов, и, в отличие от OP, вы, возможно, не захотите специально суммировать свои ключи. Или, возможно, вы захотите работать на объединении, а не на пересечении. Scalaz также добавляет дополнительные функции Mapдля этого:

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

Ты можешь сделать

import scalaz.Scalaz._

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

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

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метод.

Это то, что я придумал ...

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
}

Используя шаблон класса типов, мы можем объединить любой тип Numeric:

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

Использование:

import MapSyntax.MapOps

map1 plus map2

Слияние последовательности карт:

maps.reduce(_ plus _)

У меня есть небольшая функция для работы, она находится в моей маленькой библиотеке для некоторых часто используемых функций, которых нет в стандартной библиотеке. Это должно работать для всех типов карт, изменяемых и неизменяемых, не только HashMaps

Вот использование

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

А вот и тело

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