在scala中折叠列表的有效方法,同时避免分配和变量

Question

我在列表中有一堆项目,我需要分析内容以找出其中有多少是"完整"的.我开始使用分区,但后来意识到我不需要两个列表,所以我切换到折叠:

val counts = groupRows.foldLeft( (0,0) )( (pair, row) => 
     if(row.time == 0) (pair._1+1,pair._2) 
     else (pair._1, pair._2+1)
   )

但是我为很多并行用户提供了很多行,并且它导致了大量的GC活动(假设我...... GC 可能来自其他东西,但我怀疑这是因为我理解它将在折叠的每个项目上分配一个新的元组.

暂时,我把它重写为

var complete = 0
var incomplete = 0
list.foreach(row => if(row.time != 0) complete += 1 else incomplete += 1)

它修复了GC,但引入了变量.

我想知道是否有一种方法可以在不使用变量而不滥用GC的情况下这样做？

编辑:

我已收到的答案很难打电话.大型列表上的var实现似乎要快得多(比如40%),甚至比尾部递归优化版本更强大,但应该是等效的.

dhg的第一个答案似乎与尾递归的性能相当,这意味着大小传递是超级高效的......事实上,当优化时,它的运行速度比尾递归的速度快一些.我的硬件.

Answer 1

最干净的两次通过解决方案可能只是使用内置count方法:

val complete = groupRows.count(_.time == 0)
val counts = (complete, groupRows.size - complete)

但是如果你partition在迭代器上使用,你可以在一次传递中完成它:

val (complete, incomplete) = groupRows.iterator.partition(_.time == 0)
val counts = (complete.size, incomplete.size)

这是有效的,因为新返回的迭代器在后台链接,并且调用next一个将导致它向前移动原始迭代器,直到找到匹配的元素,但它会记住另一个迭代器的不匹配元素,这样它们就不会需要重新计算.

一次通过解决方案的示例:

scala> val groupRows = List(Row(0), Row(1), Row(1), Row(0), Row(0)).view.map{x => println(x); x}
scala> val (complete, incomplete) = groupRows.iterator.partition(_.time == 0)
Row(0)
Row(1)
complete: Iterator[Row] = non-empty iterator
incomplete: Iterator[Row] = non-empty iterator
scala> val counts = (complete.size, incomplete.size)
Row(1)
Row(0)
Row(0)
counts: (Int, Int) = (3,2)