Elegante Möglichkeit, eine Karte in Scala umzukehren

97

Lernen Sie Scala aktuell und müssen Sie eine Karte invertieren, um einige invertierte Wert-> Schlüsselsuchen durchzuführen. Ich suchte nach einem einfachen Weg, aber ich fand nur:

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

Hat jemand einen eleganteren Ansatz?

AlexeyMK
quelle

Antworten:

173

Unter der Annahme, dass Werte eindeutig sind, funktioniert dies:

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

Bei Scala 2.8 ist es jedoch einfacher:

origMap.map(_.swap)

Dies zu tun ist einer der Gründe, warum Scala 2.8 eine neue Sammlungsbibliothek hat.

Daniel C. Sobral
quelle
1
Vorsichtig! Mit dieser Lösung können Sie Werte verlieren. Zum Beispiel Map(1 -> "A", 2 -> "B", 3 -> "B").map(_.swap)ergibt sichMap(A -> 1, B -> 3)
dev-null
1
@ dev-null Es tut mir leid, aber Ihr Beispiel fällt nicht unter die erforderliche Annahme.
Daniel C. Sobral
Genau. Entschuldigung, das habe ich übersehen.
dev-null
45

Mathematisch gesehen ist die Zuordnung möglicherweise nicht invertierbar (injektiv), z. B. von Map[A,B], Sie können nicht erhalten Map[B,A], sondern Sie erhalten Map[B,Set[A]], weil möglicherweise unterschiedliche 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))
Rok Kralj
quelle
2
.map(_._1)wäre mehr lesbar als nur.keys
Cheezsteak
Jetzt dank dir sogar ein paar Zeichen kürzer. Der Unterschied besteht nun darin, dass Sie wie zuvor Sets anstelle von Lists erhalten.
Rok Kralj
1
Seien Sie vorsichtig bei der Verwendung, .mapValuesda eine Ansicht zurückgegeben wird. Gelegentlich ist dies das, was Sie wollen, aber wenn Sie nicht aufpassen, kann es viel Speicher und CPU verbrauchen. Um es in eine Karte zu erzwingen, können Sie tun m.groupBy(_._2).mapVaues(_.keys).map(identity), oder Sie können den Anruf ersetzen .mapValues(_.keys)mit .map { case (k, v) => k -> v.keys }.
Mark T.
10

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

Hier ist eine Möglichkeit. Dies verwendet eine Teilfunktion, 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 Karteniteration ruft eine Funktion mit einem Tupel mit zwei Elementen auf, und die anonyme Funktion möchte zwei Parameter. Function.tupled macht die Übersetzung.

Lee Mighdoll
quelle
6

Ich bin hierher gekommen, um nach einer Möglichkeit zu suchen, eine Karte vom Typ Karte [A, Seq [B]] in Karte [B, Seq [A]] umzukehren, wobei jedes B in der neuen Karte jedem A in der alten Karte für zugeordnet ist welches das B in A's assoziierter Sequenz enthalten war.

ZB
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
würde sich umkehren
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))
}

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

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

Eddie Carlson
quelle
sehr schöne Lösung! @Rok, seine Lösung ist irgendwie anders als Ihr ein bisschen Ich denke , weil er verwandelt: Map[A, Seq[B]]zu , Map[B, Seq[A]]wo Ihre Lösung trasnforms Map[A, Seq[B]]zu Map[Seq[B], Seq[A]].
YH
1
In diesem Fall ohne zwei verschachtelte Falten und möglicherweise leistungsfähiger:a.toSeq.flatMap { case (a, b) => b.map(_ -> a) }.groupBy(_._2).mapValues(_.map(_._1))
Rok Kralj
6

OK, das ist also eine sehr alte Frage mit vielen guten Antworten, aber ich habe das ultimative Schweizer Taschenmesser, den MapWechselrichter, gebaut und hier kann ich es posten.

Es sind eigentlich zwei Wechselrichter. Eine 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 andere, ganz ähnliche, für Wertsammlungen.

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

Verwendung:

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, sie zu untersuchen, desto problematischer erschien sie.

jwvh
quelle
3

Sie können eine Karte invertieren, indem Sie:

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

Das Problem bei diesem Ansatz besteht darin, dass Sie die doppelten Werte löschen, wenn Ihre Werte, die jetzt zu den Hash-Schlüsseln in Ihrer Karte geworden sind, nicht eindeutig sind. 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 Karte zuerst in eine Liste von Tupeln konvertieren und dann invertieren, damit Sie keine doppelten Werte löschen:

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

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 beim letzten Hinzufügen 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)
yǝsʞǝla
quelle
1

Starten Scala 2.13, um die Swap - Schlüssel / Werte ohne Schlüssel zugeordnet gleichen Werte zu verlieren, wir können Mapneue s groupMap Methode, die (wie der Name schon sagt) ist ein Äquivalent eines groupByund ein mapPing über gruppierte Elemente.

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

Dies:

  • groups Elemente basierend auf ihrem zweiten Tupelteil ( _._2) (Gruppenteil der Gruppenzuordnung )

  • mapgruppierten Elemente s mit ihrem ersten Tupel Teil unter ( _._1) (Teil der Gruppe Karte Karte )

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

Xavier Guihot
quelle
Schade, dass es sich nicht verwandeln Map[K, C[V]]wird Map[V, C[K]].
Jwvh
0
  1. Inverse ist ein besserer Name für diese Operation als Reverse (wie in "Inverse einer mathematischen Funktion").

  2. Ich mache diese inverse Transformation oft nicht nur auf Karten, sondern auch auf anderen (einschließlich Seq) Sammlungen. 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 schlagen Sie Verbesserungen für meine Implementierung vor).

    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, erhalten Sie Singleton-Listen, die trivial getestet und in eine Karte [B, A] anstatt in eine Karte [B, Liste [A]] umgewandelt werden können.

Ashwin
quelle
0

Wir können versuchen, diese foldLeftFunktion zu verwenden, die Kollisionen beseitigt und die Karte in einer einzelnen Durchquerung invertiert.

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))
Pavithran Ramachandran
quelle