Scala集合中高效的分组聚合

Question

我经常需要做类似以下的事情：

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

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

- Daniel Mahler

---

@sschaef 你能解释一下为什么把“最好的方式是什么”改成“是否可能，如果可以，如何实现”吗？这必须是可能的（图灵完备性），而且很容易找到一个笨拙的方法来做到这一点。这也使问题不符合语法。 - Daniel Mahler

"what is the best way"不是一个好的问题格式，通常无法得到明确的回答。但是经过再次考虑，我同意回滚编辑，因为它并没有使问题变得更好。 - kiritsuku

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的回答中所示。

- ziggystar

---

如果我没记错的话，你可以将 m :+ m.get(f(a)).map(g(_,a)).getOrElse(g(init,a)) 简化为 m :+ m.getOrElse(f(a), init).map(g(_,a))。 - john sullivan

请注意，虽然这节省了内存，但实际上比原来的更慢。 - Rex Kerr

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倍。但除非您受到严重的内存压力，否则创建短暂的集合并不会对您造成太大的伤害。

- Rex Kerr

---

谢谢！我的主要问题是内存。我处理非常大的集合。对于输入集合，我可以使用某种延迟加载或离线实现，但这真的无法解决中间集合的问题。 - Daniel Mahler

如果您关心内存问题，可以考虑使用Trove Java集合库，该库提供了特殊的原始类型集合。 - nnythm

@Rex Kerr，哈希表实现在插入、检索或两者方面的速度差异是3倍吗？ - Daniel Mahler

@DanielMahler - 对我来说，在插入方面有一些更大的差异，但它们都在2-3倍的范围内，具体取决于各种难以确定的因素（处理器缓存、JIT编译效果等）。 - Rex Kerr