4

我的列表中有一堆项目，我需要分析内容以找出其中有多少是“完整的”。我从分区开始，但后来意识到我不需要两个列表，所以我切换到折叠：

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，但引入了 vars。

我想知道是否有一种方法可以在不使用 vars 的同时又不滥用 GC 来做到这一点？

编辑：

强烈要求我收到的答案。var 实现在大型列表上似乎要快得多（比如 40%），甚至比功能更强大但应该等效的尾递归优化版本要快得多。

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

4

7 回答 7

11

最干净的两遍解决方案可能只是使用内置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)
于 2012-12-18T22:44:34.257 回答
3

我看到您已经接受了一个答案，但您正确地提到该解决方案将遍历列表两次。有效地做到这一点的方法是递归。

def counts(xs: List[...], complete: Int = 0, incomplete: Int = 0): (Int,Int) = 
  xs match {
    case Nil => (complete, incomplete)
    case row :: tail => 
      if (row.time == 0) counts(tail, complete + 1, incomplete)
      else               counts(tail, complete, incomplete + 1)
  }

这实际上只是一个自定义的fold，除了我们使用 2 个累加器，它们只是Ints （原语）而不是元组（引用类型）。它也应该与 vars 的 while 循环一样有效 - 事实上，字节码应该是相同的。

于 2012-12-19T02:15:46.953 回答
2

也许只有我一个人，但如果可用的话，我更喜欢使用各种专门的折叠（.size、.exists、.sum、.product）。我发现它比一般折叠的重型功能更清晰，更不容易出错。

val complete = groupRows.view.filter(_.time==0).size
(complete, groupRows.length - complete)
于 2012-12-18T22:46:54.120 回答
2

好的，受上述答案的启发，但我真的想只传递一次列表并避免 GC，我决定，面对缺乏直接 API 支持，我会将其添加到我的中央库代码中：

class RichList[T](private val theList: List[T]) {
  def partitionCount(f: T => Boolean): (Int, Int) = {
    var matched = 0
    var unmatched = 0
    theList.foreach(r => { if (f(r)) matched += 1 else unmatched += 1 })
    (matched, unmatched)
  }
}

object RichList {
  implicit def apply[T](list: List[T]): RichList[T] = new RichList(list)
}

然后在我的应用程序代码中（如果我导入了隐式），我可以编写无变量表达式：

val (complete, incomplete) = groupRows.partitionCount(_.time != 0)

并得到我想要的：一个优化的对 GC 友好的例程，它可以防止我用 var 污染程序的其余部分。

但是，我随后看到了 Luigi 的基准，并将其更新为：

  • 使用更长的列表，以便列表中的多次通过在数字中更明显
  • 在所有情况下都使用布尔函数，以便我们公平地比较事物

http://pastebin.com/2XmrnrrB

var 实现肯定要快得多，即使 Luigi 的例程应该是相同的（正如人们对优化尾递归所期望的那样）。令人惊讶的是，dhg 的双通道原始版本与尾递归版本一样快（如果编译器优化打开，则速度稍快）。我不明白为什么。

于 2012-12-19T01:03:55.143 回答
2

这个怎么样？没有进口税。

import scala.collection.generic.CanBuildFrom
import scala.collection.Traversable
import scala.collection.mutable.Builder

case class Count(n: Int, total: Int) {
  def not = total - n
}
object Count {
  implicit def cbf[A]: CanBuildFrom[Traversable[A], Boolean, Count] = new CanBuildFrom[Traversable[A], Boolean, Count] {
    def apply(): Builder[Boolean, Count] = new Counter
    def apply(from: Traversable[A]): Builder[Boolean, Count] = apply()
  }
}
class Counter extends Builder[Boolean, Count] {
  var n = 0
  var ttl = 0
  override def +=(b: Boolean) = { if (b) n += 1; ttl += 1; this }
  override def clear() { n = 0 ; ttl = 0 }
  override def result = Count(n, ttl)
}

object Counting extends App {
  val vs = List(4, 17, 12, 21, 9, 24, 11)
  val res: Count = vs map (_ % 2 == 0)
  Console println s"${vs} have ${res.n} evens out of ${res.total}; ${res.not} were odd."
  val res2: Count = vs collect { case i if i % 2 == 0 => i > 10 }
  Console println s"${vs} have ${res2.n} evens over 10 out of ${res2.total}; ${res2.not} were smaller."
}
于 2012-12-19T03:35:02.203 回答
0

像这样使用可变累加器模式会稍微整洁一些，特别是如果您可以重复使用您的累加器：

case class Accum(var complete = 0, var incomplete = 0) {
  def inc(compl: Boolean): this.type = {
    if (compl) complete += 1 else incomplete += 1
    this
  }
}
val counts = groupRows.foldLeft( Accum() ){ (a, row) => a.inc( row.time == 0 ) }

如果你真的想，你可以将你的变量隐藏为私有；如果不是，您仍然比使用 vars 的模式更加独立。

于 2012-12-18T22:15:14.387 回答
0

您可以像这样使用差异来计算它：

def counts(groupRows: List[Row]) = {
  val complete = groupRows.foldLeft(0){ (pair, row) => 
    if(row.time == 0) pair + 1 else pair
  }
  (complete, groupRows.length - complete)
}
于 2012-12-18T22:21:19.467 回答