concatenate - scala mutable collections

Manera elegante de invertir un mapa en Scala

Question

Aprendiendo Scala actualmente y necesitando invertir un Mapa para hacer algunas búsquedas de valor invertido-> clave. Estaba buscando una manera simple de hacer esto, pero se me ocurrió solo:

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

¿Alguien tiene un enfoque más elegante?

Answer 1

1. Inverso es un nombre mejor para esta operación que invertir (como en "inverso de una función matemática")

2. A menudo hago esta transformación inversa no solo en mapas sino en otras colecciones (incluida Seq). 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 de uno a uno, terminas con listas de singleton que pueden probarse trivialmente y transformarse en un mapa [B, A] en lugar de un mapa [B, lista [A]].

Answer 2

Asumiendo que los valores 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 cual Scala 2.8 tiene una nueva biblioteca de colecciones.

Answer 3

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 serán sobrescritos por 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 4

Matemáticamente, el mapeo puede no ser invertible, por ejemplo, desde el Map[A,B] , no puede obtener el Map[B,A] , sino que obtiene el Map[B,Set[A]] , porque puede haber diferentes claves asociadas con los mismos valores. Entonces, si 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 5

Podemos intentar usar esta función foldLeft que se ocupará de las colisiones e invertirá el mapa en un solo recorrido.

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

Answer 6

Podrías invertir un mapa usando:

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

El problema con este enfoque es que si sus valores, que ahora se han convertido en las claves hash en su mapa, no son únicos, eliminará 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, primero puede convertir su mapa en una lista de tuplas, luego invierta, para que no caiga ningún valor duplicado:

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 7

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

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

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

Aquí hay otra forma:

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

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

Answer 8

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

P.ej,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
se 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 pliegues plegados anidados me hacen temblar un poco, pero esta es la manera más directa que pude encontrar para lograr este tipo de inversión. ¿Alguien tiene una solución más limpia?