Scala: كيفية دمج مجموعة من الخرائط

Question

لدي قائمة خريطة [سلسلة، مزدوجة]، وأرغب في دمج محتوياتها في خريطة واحدة [سلسلة، مزدوجة]. كيف يجب أن أفعل هذا بطريقة oriomatic؟ أتصور أنني يجب أن أكون قادرا على القيام بذلك مع أضعاف. شيء مثل:

val newMap = Map[String, Double]() /: listOfMaps { (accumulator, m) => ... }

علاوة على ذلك، أود التعامل مع الاصطدامات الرئيسية بطريقة عامة. وهذا هو، إذا أضفت مفتاحا إلى الخريطة الموجودة بالفعل، يجب أن أكون قادرا على تحديد وظيفة إرجاع مضاعفة (في هذه الحالة) وتأخذ القيمة الموجودة لهذا المفتاح، بالإضافة إلى القيمة التي أحاول إضافتها وبعد إذا كان المفتاح غير موجود بعد في الخريطة، فما عليك سوى إضافته وقدرتها دون تغيير.

في حالتي المحددة، أود إنشاء خريطة واحدة [سلسلة، مضاعفة] بحيث إذا كانت الخريطة تحتوي بالفعل على مفتاح، فسيتم إضافة المزدوج إلى قيمة الخريطة الموجودة.

أنا أعمل مع خرائط متغيرة في التعليمات البرمجية الخاصة بي، لكنني مهتم بأكثر حلولا عامة، إن أمكن.

Answer 1

ماذا عن هذه:

def mergeMap[A, B](ms: List[Map[A, B]])(f: (B, B) => B): Map[A, B] =
  (Map[A, B]() /: (for (m <- ms; kv <- m) yield kv)) { (a, kv) =>
    a + (if (a.contains(kv._1)) kv._1 -> f(a(kv._1), kv._2) else kv)
  }

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
val mm = mergeMap(ms)((v1, v2) => v1 + v2)

println(mm) // prints Map(hello -> 5.5, world -> 2.2, goodbye -> 3.3)

ويعمل في كل من 2.7.5 و 2.8.0.

Answer 2

حسنا، يمكنك القيام به:

mapList reduce (_ ++ _)

باستثناء الاحتياجات الخاصة للتصادم.

نظرا لأن لديك هذا الاحتياجات الخاصة، فربما أفضل أن يفعل شيئا مثل هذا (2.8):

def combine(m1: Map, m2: Map): Map = {
  val k1 = Set(m1.keysIterator.toList: _*)
  val k2 = Set(m2.keysIterator.toList: _*)
  val intersection = k1 & k2

  val r1 = for(key <- intersection) yield (key -> (m1(key) + m2(key)))
  val r2 = m1.filterKeys(!intersection.contains(_)) ++ m2.filterKeys(!intersection.contains(_)) 
  r2 ++ r1
}

يمكنك بعد ذلك إضافة هذه الطريقة إلى فئة الخريطة من خلال نقش Pimp My Library، واستخدامها في المثال الأصلي بدلا من "++":

class CombiningMap(m1: Map[Symbol, Double]) {
  def combine(m2: Map[Symbol, Double]) = {
    val k1 = Set(m1.keysIterator.toList: _*)
    val k2 = Set(m2.keysIterator.toList: _*)
    val intersection = k1 & k2
    val r1 = for(key <- intersection) yield (key -> (m1(key) + m2(key)))
    val r2 = m1.filterKeys(!intersection.contains(_)) ++ m2.filterKeys(!intersection.contains(_))
    r2 ++ r1
  }
}

// Then use this:
implicit def toCombining(m: Map[Symbol, Double]) = new CombiningMap(m)

// And finish with:
mapList reduce (_ combine _)

بينما كتب هذا في 2.8، لذلك keysIterator يصبح keys لمدة 2.7، filterKeys قد تحتاج إلى أن تكون مكتوبة من حيث filter و map, & يصبح **, وهلم جرا، لا ينبغي أن يكون مختلفا جدا.

Answer 3

أنا مندهش لا أحد يأتي مع هذا الحل بعد:

myListOfMaps.flatten.toMap

هل بالضبط ما تحتاجه:

1. يدمج القائمة إلى خريطة واحدة
2. أعشى أي مفاتيح مكررة

مثال:

scala> List(Map('a -> 1), Map('b -> 2), Map('c -> 3), Map('a -> 4, 'b -> 5)).flatten.toMap
res7: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 4, 'b -> 5, 'c -> 3)

flatten يحول قائمة الخرائط إلى قائمة مسطحة من tuples، toMap يحول قائمة tuples إلى خريطة مع إزالتها جميع المفاتيح المكررة

Answer 4

أقرأ هذا السؤال بسرعة لذلك لست متأكدا مما إذا كنت أفتقد شيئا ما (مثله يجب أن يعمل مع 2.7.x أو بدون Scalaz):

import scalaz._
import Scalaz._
val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms.reduceLeft(_ |+| _)
// returns Map(goodbye -> 3.3, hello -> 5.5, world -> 2.2)

يمكنك تغيير تعريف Monit ل Double واحصل على طريقة أخرى لتجميع القيم، وهنا الحصول على Max:

implicit val dbsg: Semigroup[Double] = semigroup((a,b) => math.max(a,b))
ms.reduceLeft(_ |+| _)
// returns Map(goodbye -> 3.3, hello -> 4.4, world -> 2.2)

Answer 5

مثيرة للاهتمام، وهمية حول هذا قليلا، حصلت على ما يلي (في 2.7.5):

خرائط عامة:

   def mergeMaps[A,B](collisionFunc: (B,B) => B)(listOfMaps: Seq[scala.collection.Map[A,B]]): Map[A, B] = {
    listOfMaps.foldLeft(Map[A, B]()) { (m, s) =>
      Map(
        s.projection.map { pair =>
        if (m contains pair._1)
          (pair._1, collisionFunc(m(pair._1), pair._2))
        else
          pair
      }.force.toList:_*)
    }
  }

لكن الرجل، هذا هو البشعة مع الإسقاط وإجباره و tolist و whatnot. سؤال منفصل: ما هي طريقة أفضل للتعامل مع ذلك داخل الطية؟

للحصول على خرائط متغيرة، وهذا ما كنت أتعامل معه في التعليمات البرمجية، ومع حل عام أقل، حصلت على هذا:

def mergeMaps[A,B](collisionFunc: (B,B) => B)(listOfMaps: List[mutable.Map[A,B]]): mutable.Map[A, B] = {
    listOfMaps.foldLeft(mutable.Map[A,B]()) {
      (m, s) =>
      for (k <- s.keys) {
        if (m contains k)
          m(k) = collisionFunc(m(k), s(k))
        else
          m(k) = s(k)
      }
      m
    }
  }

يبدو أن الأنظف قليلا، لكنه لن يعمل فقط مع خرائط متغيرة كما هو مكتوب. ومن المثير للاهتمام، لقد حاولت لأول مرة أعلاه (قبل أن سألت السؤال) باستخدام /: بدلا من formleft، لكنني كنت أحصل على أخطاء. اعتقدت /: وكانت foldleft مكافئة أساسا، لكن المترجم أبقى يشكو من أنني بحاجة إلى أنواع واضحة ل (م، ق). ما الأمر مع ذلك؟

Answer 6

كتبت بلوق وظيفة حول هذا الأمر، والتحقق من ذلك:

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

أساسا باستخدام Scalaz Semi Group يمكنك تحقيق هذا بسهولة

سوف تبدو مثل شيء:

  import scalaz.Scalaz._
  listOfMaps reduce(_ |+| _)

Answer 7

بدءا Scala 2.13, ، حل آخر الذي مقابض المفاتيح المكررة وهذا فقط بناء على المكتبة القياسية يتكون في دمج Mapكمتسلسلة (flatten) قبل تطبيق الجديد groupmapreduce. المشغل الذي (كما يوحي اسمه) هو ما يعادل groupBy تليها رسم الخرائط وتقليل خطوة القيم المجمعة:

List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
  .flatten
  .groupMapReduce(_._1)(_._2)(_ + _)
// Map("world" -> 2.2, "goodbye" -> 3.3, "hello" -> 5.5)

هذه:

• flattenS (تسلسل) الخرائط كسلسلة من tuples (List(("hello", 1.1), ("world", 2.2), ("goodbye", 3.3), ("hello", 4.4)))، مما يحافظ على كل مفتاح / القيم (حتى مفاتيح مكررة)

• groupالعناصر S القائمة على أول جزء tuple (_._1) (جزء المجموعة من مجموعةmapreduce)

• mapقيم مجمعة إلى الجزء ثاني tuple (_._2) (خريطة جزء من المجموعةخريطةخفض)

• reduceالقيم المجمعة المعينة (_+_) عن طريق أخذ مجموعهم (ولكن يمكن أن يكون أي أي reduce: (T, T) => T وظيفة) (تقليل جزء من groupmapخفض)

---

ال groupMapReduce خطوة يمكن أن ينظر إليها على أنها نسخة واحدة أي ما يعادل:

list.groupBy(_._1).mapValues(_.map(_._2).reduce(_ + _))

Answer 8

المساعد Oneliner-Func، الذي يقرأ استخدامه نظيفا تقريبا مثل استخدام Scalaz:

def mergeMaps[K,V](m1: Map[K,V], m2: Map[K,V])(f: (V,V) => V): Map[K,V] =
    (m1 -- m2.keySet) ++ (m2 -- m1.keySet) ++ (for (k <- m1.keySet & m2.keySet) yield { k -> f(m1(k), m2(k)) })

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms.reduceLeft(mergeMaps(_,_)(_ + _))
// returns Map(goodbye -> 3.3, hello -> 5.5, world -> 2.2)

لقراءة القراءة النهائية لفه في نوع مخصص ضمني:

class MyMap[K,V](m1: Map[K,V]) {
    def merge(m2: Map[K,V])(f: (V,V) => V) =
    (m1 -- m2.keySet) ++ (m2 -- m1.keySet) ++ (for (k <- m1.keySet & m2.keySet) yield { k -> f(m1(k), m2(k)) })
}
implicit def toMyMap[K,V](m: Map[K,V]) = new MyMap(m)

val ms = List(Map("hello" -> 1.1, "world" -> 2.2), Map("goodbye" -> 3.3, "hello" -> 4.4))
ms reduceLeft { _.merge(_)(_ + _) }