scala - Scala 集合上的高效分组聚合

Question

我经常需要做类似的事情

coll.groupBy(f(_)).mapValues(_.foldLeft(x)(g(_,_)))

实现相同效果的最佳方法是什么，但要避免使用 显式构造中间集合groupBy？

Answer 1

您可以将初始集合折叠在包含中间结果的地图上：

def groupFold[A,B,X](as: Iterable[A], f: A => B, init: X, g: (X,A) => X): Map[B,X] = 
  as.foldLeft(Map[B,X]().withDefaultValue(init)){
    case (m,a) => {
      val key = f(a)
      m.updated(key, g(m(key),a))
    }
  }

你说收藏，我写Iterable，但你必须考虑在你的问题中顺序是否重要。

如果您想要高效的代码，您可能会使用 Rex 的答案中的可变映射。

Answer 2

您不能真正将其作为单行符来完成，因此在编写像这样更详细的内容之前，您应该确保需要它（因为您要求“高效”，所以从某种注重性能的角度编写）：

final case class Var[A](var value: A) { }
def multifold[A,B,C](xs: Traversable[A])(f: A => B)(zero: C)(g: (C,A) => C) = {
  import scala.collection.JavaConverters._
  val m = new java.util.HashMap[B, Var[C]]
  xs.foreach{ x =>
    val v = { 
      val fx = f(x)
      val op = m.get(fx)
      if (op != null) op
      else { val nv = Var(zero); m.put(fx, nv); nv }
    }
    v.value = g(v.value, x)
  }
  m.asScala.mapValues(_.value)
}

（根据您的用例，您可能希望在最后一步中打包到不可变映射中。）这是一个实际操作示例：

scala> multifold(List("salmon","herring","haddock"))(_(0))(0)(_ + _.length)
res1: scala.collection.mutable.HashMap[Char,Int] = Map(h -> 14, s -> 6)        

现在，您可能会注意到这里有些奇怪：我使用的是 Java HashMap。这是因为 Java 的 HashMap 比 Scala 快 2-3 倍。（您可以使用 Scala HashMap 编写等效的东西，但它实际上并没有使事情比您原来的更快。）因此，此操作比您发布的快 2-3 倍。但是，除非您承受着严重的内存压力，否则创建瞬态集合实际上并不会对您造成太大伤害。