Scala: comment fusionner une collection de cartes

StackOverflow https://stackoverflow.com/questions/1262741

Question

J'ai une liste de carte [String, Double], et je voudrais fusionner leur contenu en une seule carte [String, Double]. Comment dois-je faire cela d'une manière idiomatiques? Je suppose que je devrais être capable de le faire avec un pli. Quelque chose comme: 

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

De plus, je voudrais gérer les collisions clés d'une manière générique. Autrement dit, si j'ajoute une clé à la carte qui existe déjà, je devrais être en mesure de spécifier une fonction qui renvoie un double (dans ce cas) et prend la valeur existante pour cette clé, plus la valeur que je suis en train d'ajouter . Si la clé n'existe pas encore sur la carte, puis ajoutez juste et sa valeur inchangée.

Dans mon cas particulier, je voudrais construire une seule carte [String, Double] telle que si la carte contient déjà une clé, le double sera ajouté à la valeur de la carte actuelle.

Je travaille avec des cartes mutables dans mon code spécifique, mais je suis intéressé par des solutions plus génériques, si possible.

Était-ce utile?

La solution

Que diriez-vous celui-ci: 

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)

Et cela fonctionne dans les deux 2.7.5 et 2.8.0.

Autres conseils

Eh bien, vous pouvez le faire: 

mapList reduce (_ ++ _)

à l'exception de l'exigence spéciale de collision.

Puisque vous avez cette exigence particulière, peut-être le mieux serait de faire quelque chose comme ça (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
}

Vous pouvez ensuite ajouter cette méthode à la classe de carte à travers le motif Pimp Ma bibliothèque, et l'utiliser dans l'exemple d'origine au lieu de « ++ »: 

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

Bien que cela a été écrit en 2.8, donc keysIterator devient keys 2,7, filterKeys faudra peut-être écrit en termes de filter et map, & devient **, et ainsi de suite, il ne devrait pas être trop différent.

Je suis surpris venu de ne encore avec cette solution: 

myListOfMaps.flatten.toMap

Est-ce exactement ce dont vous avez besoin:

  1. Fusionne la liste à une seule carte
  2. les mauvaises herbes en double des clés

Exemple: 

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 transforme la liste des cartes dans une liste plate de tuples, toMap transforme la liste de tuples en une carte avec toutes les clés en double supprimés

Je lu cette question rapidement, donc je ne sais pas si je manque quelque chose (comme il doit travailler pour 2.7.x ou non 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)

Vous pouvez modifier la définition de monoid pour Double et obtenir une autre façon d'accumuler les valeurs, ici obtenir le maximum: 

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)

Intéressant, noodling autour de cela un peu, je suis la suivante (sur 2.7.5):

Cartes générales: 

   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:_*)
    }
  }

Mais l'homme, qui est hideux avec la projection et en forçant et toList et ainsi de suite. autre question: quelle est une meilleure façon de traiter que dans le pli

Pour carte mutables, ce qui est ce que je traitais dans mon code, et avec une solution moins générale, je suis arrivé à ceci: 

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

Cela semble un peu plus propre, mais ne fonctionne qu'avec mutables Maps comme il est écrit. Fait intéressant, j'ai essayé ci-dessus (avant que je pose la question) en utilisant /: au lieu de foldLeft, mais je recevais des erreurs de type. Je pensais /: et foldLeft étaient essentiellement équivalents, mais le compilateur se plaignait que je avais besoin types explicites pour (m, s). Quoi de neuf avec ça?

J'ai écrit un billet de blog à ce sujet, vérifier:

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

essentiellement en utilisant le groupe semi-scalaz vous pouvez y parvenir assez facilement

ressemblerait à quelque chose comme: 

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

une oneliner aide-Func, dont l'utilisation se lit presque aussi propre que l'utilisation 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)

pour une meilleure lisibilité ultime envelopper dans un type personnalisé implicite: 

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(_)(_ + _) }
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top