Scala groupBy 项目列表中的所有元素

Question

我有一个元组列表，其中第一个元素是一个字符串，第二个是一个字符串列表。

例如...（忽略语音标记）

val p = List((a, List(x,y,z)), (b, List(x)), (c, List(y,z)))

我的目标是将此列表分组到一个映射中，其中嵌套列表的元素充当键。

val q = Map(x -> List(a,b), y -> List(a,c), z-> List(a,c))

我最初的想法是按 p 的第二个元素分组，但这会将整个列表分配给键。

我是 Scala 的初学者，因此非常感谢任何建议。我应该期望能够使用高阶函数完成此操作还是 for 循环在这里有用？

提前致谢:)

Answer 1

这里有两个变体：

val p = List(("a", List("x","y","z")), ("b", List("x")), ("c", List("y","z")))

// 1. "Transducers"
p.flatMap{ case (k, v) => v.map { _ -> k }  }  // List((x,a), (y,a), (z,a), (x,b), (y,c), (z,c))
  .groupBy(_._1) // Map(z -> List((z,a), (z,c)), y -> List((y,a), (y,c)), x -> List((x,a), (x,b)))
  .mapValues(_.map(_._2)) // Map(z -> List(a, c), y -> List(a, c), x -> List(a, b))

// 2. For-loop
var res = Map[String, List[String]]()

for ( (k, vs) <- p;  v <- vs) {
  res += v -> k :: res.getOrElse(v, List())
}

res  // Map(x -> List(b, a), y -> List(c, a), z -> List(c, a))

// Note, values of `res` are inverted, 
// because the efficient "cons" operator (::) was used to add values to the lists
// you can revert the lists afterwards as this:

res.mapValues(_.reverse) // Map(x -> List(a, b), y -> List(a, c), z -> List(a, c))

第二个变体性能更高，因为没有创建中间集合，但它也可以被认为“不那么惯用”，因为使用了可变变量 res。但是，在私有方法中使用可变方法是完全没问题的。

更新。根据@LuisMiguelMejíaSuárez 的建议：

在(1)中，从scala 2.13开始，groupBy后面的mapValues可以换成groupMap，所以整个链条变成：

p.flatMap{ case (k, v) => v.map { _ -> k }  }
   .groupMap(_._1)(_._2)

另一个没有中间集合的功能变体可以使用 foldLeft:

实现

p.foldLeft(Map[String, List[String]]()) {
  case (acc, (k, vs)) =>
    vs.foldLeft(acc) { (acc1, v) =>
      acc1 + (v -> (k :: acc1.getOrElse(v, List())))
    }
}

或者使用 updatedWith (scala 2.13) 稍微更有效：

p.foldLeft(Map[String, List[String]]()) {
  case (acc, (k, vs)) =>
    vs.foldLeft(acc) { (acc1, v) =>
      acc1.updatedWith(v) {
        case Some(list) => Some(k :: list)
        case None       => Some(List(k))
      }
    }
}

...或同样的东西稍微短一点：

p.foldLeft(Map[String, List[String]]()) {
  case (acc, (k, vs)) =>
    vs.foldLeft(acc) { (acc1, v) =>
      acc1.updatedWith(v)(_.map(k :: _).orElse(Some(List(k))))
    }
}

总的来说，我建议使用 foldLeft 变体（最高性能和功能），或者第一个 groupMap 变体（更短，可以说更具可读性，但性能较差），具体取决于关于你的目标。

Answer 2

您的输入列表 p 距离成为 Map 仅一步之遥。从那里你只需要一个通用的地图逆变器。

import scala.collection.generic.IsIterableOnce
import scala.collection.Factory

// from Map[K,C[V]] to Map[V,C[K]] (Scala 2.13.x)
implicit class MapInverter[K,V,C[_]](m: Map[K,C[V]]) {
  def invert(implicit iio: IsIterableOnce[C[V]] {type A = V}
                    , fac: Factory[K,C[K]]): Map[V,C[K]] =
    m.foldLeft(Map.empty[V, List[K]]) {
      case (acc, (k, vs)) =>
        iio(vs).iterator.foldLeft(acc) {
          case (a, v) =>
            a + (v -> (k::a.getOrElse(v,Nil)))
        }
    }.map{case (k,v) => k -> v.to(fac)}
}

用法：

val p = List(("a", List("x","y","z")), ("b", List("x")), ("c", List("y","z")))
val q = p.toMap.invert
//Map(x -> List(b, a), y -> List(c, a), z -> List(c, a))

Scala groupBy 项目列表中的所有元素

Scala groupBy all elements in the item's list

functional-programming

scala