webentwicklung-frage-antwort-db.com.de

Elegante Möglichkeit, eine Karte in Scala umzukehren

Um Scala aktuell zu lernen, musste eine Karte invertiert werden, um einige invertierte Werte-> Schlüsselsuchen durchzuführen. Ich suchte nach einer einfachen Möglichkeit, dies zu tun, brachte aber nur Folgendes heraus:

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

Hat jemand einen eleganteren Ansatz?

89
AlexeyMK

Angenommen, Werte sind einzigartig, das funktioniert:

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

Auf Scala 2.8 ist es jedoch einfacher:

origMap.map(_.swap)

Dies ist ein Grund, warum Scala 2.8 eine neue Sammlungsbibliothek hat.

158

Mathematisch ist das Mapping möglicherweise nicht invertierbar (injektiv), z. B. von Map[A,B] können Sie Map[B,A] nicht erhalten, sondern Map[B,Set[A]], da möglicherweise andere Schlüssel mit denselben Werten verknüpft sind. Wenn Sie also alle Schlüssel kennen möchten, finden Sie hier den Code: 

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))
40
Rok Kralj

Sie können das ._1-Zeug während der Iteration auf verschiedene Arten vermeiden. 

Hier ist ein Weg. Hierbei wird eine Teilfunktion verwendet, die den einzigen Fall abdeckt, der für die Karte von Bedeutung ist: 

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

Hier ist ein anderer Weg:

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

Die Map-Iteration ruft eine Funktion mit einem Tupel mit zwei Elementen auf, und die anonyme Funktion benötigt zwei Parameter. Function.tupled macht die Übersetzung.

10
Lee Mighdoll

Ich bin hierher gekommen, um eine Map vom Typ Map [A, Seq [B]] in Map [B, Seq [A]] umzukehren, wobei jedes B in der neuen Map mit jedem A in der alten Map für verknüpft ist welches das B in der assoziierten Sequenz von A enthalten war.

Z.B.,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
würde invertieren zu
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Hier ist meine Lösung:

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

wobei oldMap vom Typ Map[A, Seq[B]] und newMap vom Typ Map[B, Seq[A]] ist

Die verschachtelten foldLefts lassen mich ein wenig zusammenzucken, aber dies ist der einfachste Weg, den ich finden könnte, um diese Art der Inversion zu erreichen. Hat jemand eine sauberere Lösung?

6
Eddie Carlson

OK, das ist also eine sehr alte Frage mit vielen guten Antworten, aber ich habe den ultimativen All-and-End-All, das Schweizer Armeemesser, Map Inverter gebaut.

Es sind eigentlich zwei Wechselrichter. Einer für einzelne Wertelemente ...

//from Map[K,V] to Map[V,Set[K]], traverse the input only once
implicit class MapInverterA[K,V](m :Map[K,V]) {
  def invert :Map[V,Set[K]] =
    m.foldLeft(Map.empty[V, Set[K]]) {
      case (acc,(k, v)) => acc + (v -> (acc.getOrElse(v,Set()) + k))
    }
}

... und eine ganz ähnliche für Wertesammlungen.

import scala.collection.generic.CanBuildFrom
import scala.collection.mutable.Builder
import scala.language.higherKinds

//from Map[K,C[V]] to Map[V,C[K]], traverse the input only once
implicit class MapInverterB[K,V,C[_]](m :Map[K,C[V]]
                                     )(implicit ev :C[V] => TraversableOnce[V]) {
  def invert(implicit bf :CanBuildFrom[Nothing,K,C[K]]) :Map[V,C[K]] =
    m.foldLeft(Map.empty[V, Builder[K,C[K]]]) {
      case (acc, (k, vs)) =>
        vs.foldLeft(acc) {
          case (a, v) => a + (v -> (a.getOrElse(v,bf()) += k))
        }
    }.mapValues(_.result())
}

verwendungszweck:

Map(2 -> Array('g','h'), 5 -> Array('g','y')).invert
//res0: Map(g -> Array(2, 5), h -> Array(2), y -> Array(5))

Map('q' -> 1.1F, 'b' -> 2.1F, 'c' -> 1.1F, 'g' -> 3F).invert
//res1: Map(1.1 -> Set(q, c), 2.1 -> Set(b), 3.0 -> Set(g))

Map(9 -> "this", 8 -> "that", 3 -> "thus", 2 -> "thus").invert
//res2: Map(this -> Set(9), that -> Set(8), thus -> Set(3, 2))

Map(1L -> Iterator(3,2), 5L -> Iterator(7,8,3)).invert
//res3: Map(3 -> Iterator(1, 5), 2 -> Iterator(1), 7 -> Iterator(5), 8 -> Iterator(5))

Map.empty[Unit,Boolean].invert
//res4: Map[Boolean,Set[Unit]] = Map()

Ich würde es vorziehen, beide Methoden in derselben impliziten Klasse zu haben, aber je mehr Zeit ich damit verbrachte, desto problematischer wurde es.

2
jwvh

Sie können eine Karte folgendermaßen invertieren:

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

Das Problem bei diesem Ansatz ist, dass, wenn Ihre Werte, die jetzt zu den Hash-Schlüsseln in Ihrer Map geworden sind, nicht eindeutig sind, die doppelten Werte gelöscht werden. Um zu zeigen:

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)

Um dies zu vermeiden, können Sie Ihre Map zuerst in eine Liste von Tupeln konvertieren und dann invertieren, damit keine doppelten Werte gelöscht werden:

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

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

Beachten Sie, dass doppelte Werte durch den letzten Zusatz zur Karte überschrieben werden:

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)
1
yǝsʞǝlA
  1. Inverse ist ein besserer Name für diese Operation als invers (wie in "Inverse einer mathematischen Funktion").

  2. Ich mache diese inverse Transformation oft nicht nur auf Karten, sondern auch auf anderen Sammlungen (einschließlich Seq). Ich finde es am besten, die Definition meiner inversen Operation nicht auf Eins-zu-Eins-Karten zu beschränken. Hier ist die Definition, mit der ich für Karten arbeite (bitte Verbesserungen an meiner Implementierung vorschlagen).

    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
    }
    

Wenn es sich um eine Eins-zu-Eins-Karte handelt, landen Sie mit Singleton-Listen, die trivial getestet und in eine Karte [B, A] anstatt in eine Karte [B, Liste [A]] umgewandelt werden können.

0
Ashwin

Starten Sie Scala 2.13, um Schlüssel/Werte zu vertauschen, ohne Schlüssel zu verlieren, die denselben Werten zugeordnet sind, können Sie Maps new groupMap -Methode verwenden, die (wie der Name schon sagt) ein Äquivalent von groupBy und mapping über gruppierten Elementen ist.

Map(1 -> "a", 2 -> "b", 4 -> "b").groupMap(_._2)(_._1)
// Map("b" -> List(2, 4), "a" -> List(1))

Diese:

  • groups Elemente basierend auf ihrem zweiten Tuple-Teil (_._2) (Gruppenteil von group Map)

  • maps gruppierte Elemente nach ihrem ersten Tuple-Teil (_._1) (Kartenteil von groupMap)

Dies kann als One-Pass-Version von map.groupBy(_._2).mapValues(_.map(_._1)) angesehen werden.

0
Xavier Guihot

Wir können versuchen, diese foldLeft-Funktion zu verwenden, die sich um Kollisionen kümmert und die Karte in eine einzige Traversierung umwandelt.

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