Cara terbaik untuk menggabungkan dua peta dan menjumlahkan nilai-nilai kunci yang sama?

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

Saya ingin menggabungkan mereka, dan menjumlahkan nilai-nilai kunci yang sama. Jadi hasilnya adalah:

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

Sekarang saya punya 2 solusi:

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

dan

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

Tapi saya ingin tahu apakah ada solusi yang lebih baik.

Scalaz memiliki konsep Semigroup yang menangkap apa yang ingin Anda lakukan di sini, dan mengarah pada solusi terpendek / terbersih:

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)

Secara khusus, operator biner untuk Map[K, V]menggabungkan kunci peta, melipat Voperator semigroup atas nilai duplikat apa pun. Semigroup standar untuk Intmenggunakan operator tambahan, sehingga Anda mendapatkan jumlah nilai untuk setiap kunci duplikat.

Sunting : Sedikit lebih detail, sesuai permintaan pengguna482745.

Secara matematis sebuah semi -grup hanyalah satu set nilai, bersama dengan operator yang mengambil dua nilai dari set itu, dan menghasilkan nilai lain dari set itu. Jadi bilangan bulat yang ditambahkan adalah semigroup, misalnya - +operator menggabungkan dua int untuk membuat int lainnya.

Anda juga dapat mendefinisikan sebuah semi grup dari set "semua peta dengan tipe kunci dan tipe nilai yang diberikan", asalkan Anda dapat membuat beberapa operasi yang menggabungkan dua peta untuk menghasilkan yang baru yang entah bagaimana merupakan kombinasi dari keduanya. input.

Jika tidak ada kunci yang muncul di kedua peta, ini sepele. Jika kunci yang sama ada di kedua peta, maka kita perlu menggabungkan dua nilai yang dipetakan oleh kunci tersebut. Hmm, bukankah kita baru saja menggambarkan operator yang menggabungkan dua entitas dari jenis yang sama? Inilah sebabnya mengapa dalam Scalaz, sebuah semi-grup untuk Map[K, V]ada jika dan hanya jika semi-grup untuk Vada - semi-grup Vdigunakan untuk menggabungkan nilai-nilai dari dua peta yang ditugaskan untuk kunci yang sama.

Jadi karena Intjenis nilai di sini, "tabrakan" pada 1kunci diselesaikan dengan penambahan integer dari dua nilai yang dipetakan (seperti yang dilakukan oleh operator semi-grup Int), karenanya 100 + 9. Jika nilainya adalah String, tabrakan akan menghasilkan rangkaian string dari dua nilai yang dipetakan (sekali lagi, karena itulah yang dilakukan oleh operator semi-grup untuk String).

(Dan yang menarik, karena rangkaian string tidak komutatif - yaitu, "a" + "b" != "b" + "a"- operasi semigroup yang dihasilkan juga tidak. Jadi map1 |+| map2berbeda dari map2 |+| map1dalam kasus String, tetapi tidak dalam kasus Int.)

Jawaban terpendek yang saya tahu hanya menggunakan perpustakaan standar

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

Solusi cepat:

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

Nah, sekarang di perpustakaan scala (setidaknya di 2,10) ada sesuatu yang Anda inginkan - fungsi gabungan . TAPI itu disajikan hanya di HashMap bukan di Peta. Agak membingungkan. Tanda tangannya juga rumit - tidak bisa membayangkan mengapa saya perlu kunci dua kali dan ketika saya harus menghasilkan pasangan dengan kunci lain. Namun demikian, ini bekerja dan jauh lebih bersih daripada solusi "asli" sebelumnya.

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

Juga di scaladoc disebutkan itu

The mergedmetode adalah rata-rata lebih performant daripada melakukan traversal dan merekonstruksi peta hash berubah baru dari awal, atau ++.

Ini dapat diimplementasikan sebagai Monoid dengan Scala biasa. Berikut ini adalah contoh implementasi. Dengan pendekatan ini, kita dapat menggabungkan bukan hanya 2, tetapi juga daftar peta.

// Monoid trait

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

Implementasi berbasis peta dari sifat Monoid yang menggabungkan dua peta.

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
}

Sekarang, jika Anda memiliki daftar peta yang perlu digabung (dalam hal ini, hanya 2), itu bisa dilakukan seperti di bawah ini.

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

Saya menulis posting blog tentang ini, lihat:

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

pada dasarnya menggunakan scalaz semi grup Anda dapat mencapainya dengan cukup mudah

akan terlihat seperti:

  import scalaz.Scalaz._
  map1 |+| map2

Anda juga bisa melakukannya dengan Kucing .

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)

Mulai Scala 2.13, solusi lain hanya berdasarkan pustaka standar terdiri dalam mengganti groupBybagian dari solusi Anda dengan groupMapReduceyang (seperti namanya) adalah setara dengan groupBydiikuti oleh mapValuesdan langkah pengurangan:

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

Ini:

• Menggabungkan dua peta sebagai urutan tupel ( List((1,9), (2,20), (1,100), (3,300))). Untuk keringkasan, map2yang secara implisit dikonversi ke Seqberadaptasi dengan jenis map1.toSeq- tapi Anda bisa memilih untuk membuatnya eksplisit dengan menggunakan map2.toSeq,

• groupElemen berdasarkan pada bagian tupel pertama mereka (bagian grup dari grup MapReduce),

• maps nilai yang dikelompokkan ke bagian tupel kedua mereka (bagian peta dari grup Mengurangi Peta ),

• reduces memetakan nilai ( _+_) dengan menjumlahkannya (kurangi bagian dari groupMap Reduce ).

Inilah yang akhirnya saya gunakan:

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

Jawaban Andrzej Doyle berisi penjelasan yang bagus tentang semi-grup yang memungkinkan Anda menggunakan |+|operator untuk bergabung dengan dua peta dan menjumlahkan nilai-nilai untuk kunci yang cocok.

Ada banyak cara sesuatu dapat didefinisikan sebagai turunan dari typeclass, dan tidak seperti OP Anda mungkin tidak ingin menjumlahkan kunci Anda secara khusus. Atau, Anda mungkin ingin melakukan operasi pada serikat daripada persimpangan. Scalaz juga menambahkan fungsi ekstra Mapuntuk tujuan ini:

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

Anda dapat melakukan

import scalaz.Scalaz._

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

Cara tercepat dan paling sederhana:

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

Dengan cara ini, masing-masing elemen segera ditambahkan ke peta.

Cara kedua ++adalah:

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

Berbeda dengan cara pertama, Dalam cara kedua untuk setiap elemen dalam peta kedua, Daftar baru akan dibuat dan digabungkan ke peta sebelumnya.

The caseekspresi implisit menciptakan Daftar baru menggunakan unapplymetode.

Inilah yang saya temukan ...

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
}

Menggunakan pola typeclass, kita bisa menggabungkan semua tipe 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)) }
    }
  }
}

Pemakaian:

import MapSyntax.MapOps

map1 plus map2

Menggabungkan urutan peta:

maps.reduce(_ plus _)

Saya punya fungsi kecil untuk melakukan pekerjaan itu, ada di perpustakaan kecil saya untuk beberapa fungsi yang sering digunakan yang tidak ada dalam lib standar. Ini harus bekerja untuk semua jenis peta, bisa berubah dan tidak berubah, tidak hanya HashMaps

Ini adalah penggunaannya

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

Dan inilah tubuhnya

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