Cách thanh lịch để đảo ngược bản đồ trong Scala

Question

Học Scala hiện tại và cần đảo ngược Bản đồ để thực hiện một số giá trị đảo ngược-> tra cứu chính. Tôi đang tìm kiếm một cách đơn giản để làm điều này, nhưng đã đưa ra chỉ:

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

Bất kỳ ai có một cách tiếp cận thanh lịch hơn?

Answer 1

giá trị Giả sử là duy nhất, công trình này:

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

On Scala 2.8, tuy nhiên, nó dễ dàng hơn:

origMap.map(_.swap) 

Có khả năng làm điều đó là một phần lý do tại sao Scala 2.8 có thư viện sưu tập mới.

Answer 2

Bạn có thể tránh các nội dung ._1 trong khi lặp lại theo nhiều cách.

Đây là một cách. Này sử dụng một hàm từng phần bao gồm một và chỉ một trường hợp đó quan trọng đối với bản đồ:

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

Dưới đây là một cách khác:

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

Các lặp đồ gọi một hàm với một yếu tố tuple hai, và chức năng ẩn danh muốn có hai tham số. Function.tupled làm cho bản dịch.

Answer 3

1. Inverse là một cái tên tốt hơn cho hoạt động này hơn ngược lại (như trong "nghịch đảo của một hàm toán học")

2. tôi thường làm biến đổi nghịch đảo này không chỉ trên bản đồ nhưng trên khác (bao gồm Seq) bộ sưu tập. Tôi thấy tốt nhất là không giới hạn định nghĩa hoạt động nghịch đảo của tôi thành bản đồ một-một. Đây là định nghĩa tôi hoạt động với bản đồ (vui lòng đề xuất cải tiến cho việc triển khai của tôi).

   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 
   } 
   

Nếu đó là một bản đồ one-to-one, bạn kết thúc với danh sách singleton mà có thể được kiểm tra trivially và chuyển thành một bản đồ [B, A] chứ không phải là đồ [B, Danh sách [A ]].

Answer 4

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

Lưu ý rằng lặp lại giá trị này sẽ được ghi đè bởi việc bổ sung mới nhất vào bản đồ:

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

Tôi đến đây tìm kiếm một cách để đảo ngược một bản đồ kiểu Bản đồ [A, Seq [B]] vào Bản đồ [B, Seq [A]], trong đó mỗi B trong bản đồ mới được liên kết với mọi A trong bản đồ cũ mà B được chứa trong chuỗi liên quan của A.

Ví dụ:,
Map(1 -> Seq("a", "b"), 2-> Seq("b", "c"))
sẽ đảo ngược để
Map("a" -> Seq(1), "b" -> Seq(1, 2), "c" -> Seq(2))

Đây là giải pháp của tôi:

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

nơi oldMap là loại Map[A, Seq[B]] và newMap là loại Map[B, Seq[A]]

Các foldLefts lồng nhau làm cho tôi cringe một chút, nhưng đây là cách đơn giản nhất tôi có thể tìm thấy để thực hiện điều này ty pe đảo ngược. Bất cứ ai có một giải pháp sạch hơn?

Answer 6

Về mặt toán học, ánh xạ có thể không đảo ngược, ví dụ: từ Map[A,B], bạn không thể nhận được Map[B,A], mà là bạn nhận được Map[B,Set[A]], vì có thể có các khóa khác nhau được liên kết với cùng giá trị. Vì vậy, nếu bạn đang muốn biết tất cả các phím, đây là các mã:

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

Bạn có thể đảo ngược bản đồ sử dụng:

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

Vấn đề với cách tiếp cận này là nếu giá trị của bạn, mà có bây giờ trở thành các khóa băm trong bản đồ của bạn, không phải là duy nhất bạn sẽ thả các giá trị trùng lặp. Để minh họa:

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) 

Để tránh điều này, bạn có thể chuyển đổi bản đồ của bạn vào một danh sách các hàng đầu tiên, sau đó đảo ngược, do đó bạn không thả bất kỳ giá trị nhân bản:

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

Chúng ta có thể thử sử dụng chức năng foldLeft này sẽ xử lý các va chạm và đảo ngược bản đồ trong một lần truyền tải.

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