更清晰的元组groupBy

Question

我有一组键值对（String，Int），我想按键将它们分组为一个值序列（即Seq[(String, Int)]) => Map[String, Iterable[Int]])）。

显然，toMap 在这里没有用处，而 groupBy 会保持元组的值。我能想到的最好解决方案是：

val seq: Seq[( String, Int )]
// ...
seq.groupBy( _._1 ).mapValues( _.map( _._2 ) )

有更简洁的方法吗？

- Tomer Gabel

---

我经常使用这个模式，希望它能够内置到某个地方。 - Garrett Hall

Answer 1

这里有一个 pimp，它为 traversable 增加了一个 toMultiMap 方法。它能解决你的问题吗？

import collection._
import mutable.Builder
import generic.CanBuildFrom

class TraversableOnceExt[CC, A](coll: CC, asTraversable: CC => TraversableOnce[A]) {

  def toMultiMap[T, U, That](implicit ev: A <:< (T, U), cbf: CanBuildFrom[CC, U, That]): immutable.Map[T, That] =
    toMultiMapBy(ev)

  def toMultiMapBy[T, U, That](f: A => (T, U))(implicit cbf: CanBuildFrom[CC, U, That]): immutable.Map[T, That] = {
    val mutMap = mutable.Map.empty[T, mutable.Builder[U, That]]
    for (x <- asTraversable(coll)) {
      val (key, value) = f(x)
      val builder = mutMap.getOrElseUpdate(key, cbf(coll))
      builder += value
    }
    val mapBuilder = immutable.Map.newBuilder[T, That]
    for ((k, v) <- mutMap)
      mapBuilder += ((k, v.result))
    mapBuilder.result
  }
}

implicit def commomExtendTraversable[A, C[A] <: TraversableOnce[A]](coll: C[A]): TraversableOnceExt[C[A], A] =
  new TraversableOnceExt[C[A], A](coll, identity)

可以像这样使用：

val map = List(1 -> 'a', 1 -> 'à', 2 -> 'b').toMultiMap
println(map)  // Map(1 -> List(a, à), 2 -> List(b))

val byFirstLetter = Set("abc", "aeiou", "cdef").toMultiMapBy(elem => (elem.head, elem))
println(byFirstLetter) // Map(c -> Set(cdef), a -> Set(abc, aeiou))

如果您添加以下隐式定义，它也将适用于类似于集合的对象，例如String和Array：

如果您添加以下隐式定义，它也将适用于类似于集合的对象，例如String和Array：

implicit def commomExtendStringTraversable(string: String): TraversableOnceExt[String, Char] =
  new TraversableOnceExt[String, Char](string, implicitly)

implicit def commomExtendArrayTraversable[A](array: Array[A]): TraversableOnceExt[Array[A], A] =
  new TraversableOnceExt[Array[A], A](array, implicitly)

然后：

val withArrays = Array(1 -> 'a', 1 -> 'à', 2 -> 'b').toMultiMap
println(withArrays) // Map(1 -> [C@377653ae, 2 -> [C@396fe0f4)

val byLowercaseCode = "Mama".toMultiMapBy(c => (c.toLower.toInt, c))
println(byLowercaseCode) // Map(97 -> aa, 109 -> Mm)

- Jean-Philippe Pellet

---

远超出我的预期，但仍然非常有用。谢谢！ - Tomer Gabel

这非常好。是否有一种简单的方法来覆盖值集合的类型（比如我有一个List(1 -> 'a'，1 -> 'à'，2 -> 'b')，但我希望toMultiMap的结果是Map[Int，Set[String]]？也许可以用breakOut做些小技巧？ - Tomáš Dvořák

Answer 2

标准库中没有相应的方法或数据结构可以做到这一点，你的解决方案看起来就像你能得到的最简洁的解决方案。如果你在多个地方使用它，你可能会想把它提取出来成为一个实用方法。

def groupTuples[A, B](seq: Seq[(A, B)]) = 
  seq groupBy (_._1) mapValues (_ map (_._2))

然后你显然只需调用 groupTuples(seq) 即可。从 CPU 时钟周期的角度来看，这可能不是最高效的方法，但我认为它也不是特别低效。

我对一个由9个元组组成的列表进行了简单的基准测试，这比 Jean-Philippe 的解决方案略快一些。两者都比将序列折叠到映射（有效地重新实现 groupBy 来给出所需输出）要快大约两倍。

- Luigi Plinge

---

mapValues实际上只是包装了构建的映射，因此在查找映射中的内容时可能效率会降低。另外，我已经编辑了我的答案，避免了使用toMap;出于好奇，您可以再次运行相同的基准测试吗？根据我的基准测试，对于9个元组，使用我的提议构建映射和两次查找时间约为原来的三分之一。 - Jean-Philippe Pellet

@Jean-Philippe，我在以上代码中进行了10万次运行，得到了97毫秒的时间，而使用你更新后的代码则需要106毫秒。当然，我们应该尝试不同长度和组合的列表，但我只是想获得一个大致的想法。在实际应用中，它们的速度是相同的。 - Luigi Plinge

@Jean-Philippe 有趣的是 mapValues 包装了现有的 map - 我不知道这一点。使用 seq groupBy (_._1) map (x => (x._1, x._2 map (_._2))) 创建一个全新的 map 需要 165 毫秒，因此对于在内存中创建新的 map，你的方法更快。 - Luigi Plinge

效率实际上并不是一个很大的问题，但了解其影响还是很好的。很遗憾我不能接受两个答案 - 我将不得不选择Jean-Philippe的答案，因为它非常全面 :-) - Tomer Gabel

Answer 3

我不知道你是否认为它更加清晰：

seq.groupBy(_._1).map { case (k,v) => (k,v.map(_._2))}

- Johnny Everson

---

我并不是很满意，我在寻找更简洁和/或语义更清晰的解决方案。 - Tomer Gabel

当然。我想你需要创建一个函数，并在需要时调用它。这样你就可以按照自己的方式编写语法了。 - Johnny Everson

Answer 4

自从Scala 2.13开始，大多数集合都提供了groupMap方法（如其名所示），它是groupBy后跟mapValues的等效（更高效）版本。请参考此链接。请注意保留HTML标记。

List(1 -> 'a', 1 -> 'b', 2 -> 'c').groupMap(_._1)(_._2)
// Map[Int,List[Char]] = Map(2 -> List(c), 1 -> List(a, b))

这样做：

• group 根据元组的第一部分（Map(2 -> List((2,c)), 1 -> List((1,a), (1,b)))）将元素分组。

• map 通过获取其第二个元组部分（List(a, b)）来 map 分组后的值（List((1,a), (1,b)))。

- Xavier Guihot