Manera elegante de invertir un mapa en Scala

Question

Aprendizaje de Scala actualmente y necesario para invertir un mapa para hacer algunas búsquedas de valor invertido-> clave. Estaba buscando una forma sencilla de hacerlo, pero se me ocurrió solo:

(Map() ++ origMap.map(kvp=>(kvp._2->kvp._1))) 

¿Alguien tiene un enfoque más elegante?

Answer 1

valores Suponiendo que son únicos, esto funciona:

(Map() ++ origMap.map(_.swap)) 

En Scala 2.8, sin embargo, es más fácil:

origMap.map(_.swap) 

Ser capaz de hacer eso es parte de la razón por la Scala 2.8 tiene una nueva biblioteca de colecciones.

Answer 2

Puede evitar las cosas ._1 mientras itera de varias maneras.

Aquí hay una manera. Este sistema utiliza una función parcial que cubre el único caso que importa para el mapa:

Map() ++ (origMap map {case (k,v) => (v,k)}) 

Ésta es otra manera:

import Function.tupled   
Map() ++ (origMap map tupled {(k,v) => (v,k)}) 

El mapa iteración llama a una función con una tupla de dos elementos, y la la función anónima quiere dos parámetros. Function.tupled hace la traducción.

Answer 3

1. Inversa es un mejor nombre para esta operación de marcha atrás (como en "inversa de una función matemática")

2. hago a menudo esta transformación inversa no sólo en los mapas pero por otra (incluyendo Sec) colecciones. Me parece mejor no limitar la definición de mi operación inversa a los mapas de uno a uno. Esta es la definición con la que opero para mapas (sugiera mejoras a mi implementación).

   def invertMap[A,B](m: Map[A,B]) : Map[B,List[A]] = { 
       val k = ((m values) toList) distinct 
       val v = k map { e => ((m keys) toList) filter { x => m(x) == e } } 
       (k zip v) toMap 
   } 
   

Si se trata de un mapa uno a uno, se termina con las listas simples que pueden ser trivialmente probaron y se transforma en un mapa [B, A] en lugar de mapa [B, Lista [A ]].

Answer 4

en Scala REPL:

scala> val m = Map(1 -> "one", 2 -> "two") 
m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> one, 2 -> two) 

scala> val reversedM = m map { case (k, v) => (v, k) } 
reversedM: scala.collection.immutable.Map[java.lang.String,Int] = Map(one -> 1, two -> 2) 

Tenga en cuenta que los valores duplicados se sobrescribirán con la última adición al mapa:

scala> val m = Map(1 -> "one", 2 -> "two", 3 -> "one") 
m: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> one, 2 -> two, 3 -> one) 

scala> val reversedM = m map { case (k, v) => (v, k) } 
reversedM: scala.collection.immutable.Map[java.lang.String,Int] = Map(one -> 3, two -> 2) 

Answer 5

Vine aquí buscando una manera de invertir un mapa de tipo Asigne [A, Seq [B]] al Mapa [B, Seq [A]], donde cada B en el nuevo mapa está asociado con cada A en el mapa antiguo para el que B estaba en la secuencia asociada de A.

E.g.,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
invertiría a
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Aquí está mi solución:

val newMap = oldMap.foldLeft(Map[B, Seq[A]]().withDefaultValue(Seq())) { 
    case (m, (a, bs)) => bs.foldLeft(m)((map, b) => map.updated(b, m(b) :+ a)) 
} 

donde oldmap es de tipo Map[A, Seq[B]] y newMap es de tipo Map[B, Seq[A]]

Los foldLefts anidados me hace se encoge un poco, pero esta es la manera más directa que pude encontrar para lograr este ty pe de inversión. ¿Alguien tiene una solución más limpia?

Answer 6

Matemáticamente, el mapeo puede que no sea invertible, por ejemplo, de Map[A,B], no se puede obtener Map[B,A], sino que se obtiene Map[B,Set[A]], porque puede haber diferentes claves asociados con los mismos valores. Por lo tanto, si usted está interesado en conocer todas las claves, aquí está el código:

scala> val m = Map(1 -> "a", 2 -> "b", 4 -> "b") 
scala> m.groupBy(_._2).mapValues(_.keys) 
res0: Map[String,Iterable[Int]] = Map(b -> Set(2, 4), a -> Set(1)) 

Answer 7

Se podría invertir un mapa usando:

val i = origMap.map({case(k, v) => v -> k}) 

El problema con este enfoque es que si sus valores, que tienen ahora se convierten en las teclas hash en su mapa, no son exclusivas, se eliminarán los valores duplicados. Para ilustrar:

scala> val m = Map("a" -> 1, "b" -> 2, "c" -> 3, "d" -> 1) 
m: scala.collection.immutable.Map[String,Int] = Map(a -> 1, b -> 2, c -> 3, d -> 1) 

// Notice that 1 -> a is not in our inverted map 
scala> val i = m.map({ case(k , v) => v -> k}) 
i: scala.collection.immutable.Map[Int,String] = Map(1 -> d, 2 -> b, 3 -> c) 

Para evitar esto se puede convertir el mapa para una lista de tuplas en primer lugar, a continuación, invertir, de modo que no dejar caer ningún valores duplicados:

scala> val i = m.toList.map({ case(k , v) => v -> k}) 
i: List[(Int, String)] = List((1,a), (2,b), (3,c), (1,d)) 

Answer 8

Podemos tratar de usar esta función foldLeft que se ocupará de las colisiones e invertirá el mapa en una sola pasada.

scala> def invertMap[A, B](inputMap: Map[A, B]): Map[B, List[A]] = { 
    |  inputMap.foldLeft(Map[B, List[A]]()) { 
    |  case (mapAccumulator, (value, key)) => 
    |   if (mapAccumulator.contains(key)) { 
    |   mapAccumulator.updated(key, mapAccumulator(key) :+ value) 
    |   } else { 
    |   mapAccumulator.updated(key, List(value)) 
    |   } 
    |  } 
    | } 
invertMap: [A, B](inputMap: Map[A,B])Map[B,List[A]] 

scala> val map = Map(1 -> 2, 2 -> 2, 3 -> 3, 4 -> 3, 5 -> 5) 
map: scala.collection.immutable.Map[Int,Int] = Map(5 -> 5, 1 -> 2, 2 -> 2, 3 -> 3, 4 -> 3) 

scala> invertMap(map) 
res0: Map[Int,List[Int]] = Map(5 -> List(5), 2 -> List(1, 2), 3 -> List(3, 4)) 

scala> val map = Map("A" -> "A", "B" -> "A", "C" -> "C", "D" -> "C", "E" -> "E") 
map: scala.collection.immutable.Map[String,String] = Map(E -> E, A -> A, B -> A, C -> C, D -> C) 

scala> invertMap(map) 
res1: Map[String,List[String]] = Map(E -> List(E), A -> List(A, B), C -> List(C, D))