首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在scala中折叠列表的有效方法,同时避免分配和vars

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

Stack Overflow用户
提问于 2012-12-18 21:53:55
回答 7查看 839关注 0票数 4

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

代码语言:javascript
复制
val counts = groupRows.foldLeft( (0,0) )( (pair, row) => 
     if(row.time == 0) (pair._1+1,pair._2) 
     else (pair._1, pair._2+1)
   )

但是,对于许多并行用户,我有很多行要处理,这导致了大量的GC活动(我的part...the GC上的假设可能来自其他方面,但我怀疑这一点,因为我知道它会在折叠的每个项目上分配一个新的元组)。

目前,我已经把这个重写为

代码语言:javascript
复制
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的第一个答案似乎与尾递归的性能相当,这意味着大小传递是超级高效的.事实上,优化后它的运行速度比我的硬件上的尾递归的要快一些。

EN

回答 7

Stack Overflow用户

回答已采纳

发布于 2012-12-19 02:15:46

我看你已经接受了一个答案,但你正确地提到,这个解决方案将遍历列表两次。有效地进行此操作的方法是使用递归。

代码语言:javascript
复制
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,只不过我们使用了两个累加器,它们只是Int(原语)而不是元组(引用类型)。实际上,字节码应该是相同的。

票数 3
EN

Stack Overflow用户

发布于 2012-12-18 22:44:34

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

代码语言:javascript
复制
val complete = groupRows.count(_.time == 0)
val counts = (complete, groupRows.size - complete)

但是,如果在迭代器上使用partition,则可以一次执行:

代码语言:javascript
复制
val (complete, incomplete) = groupRows.iterator.partition(_.time == 0)
val counts = (complete.size, incomplete.size)

这是因为新返回的迭代器是在幕后链接的,调用其中一个迭代器将导致它将原始迭代器向前移动,直到找到匹配的元素为止,但是它会记住其他迭代器的不匹配元素,因此不需要重新计算它们。

一次过解决方案的示例:

代码语言:javascript
复制
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)
票数 11
EN

Stack Overflow用户

发布于 2012-12-18 22:46:54

也许只有我,但如果有可用的话,我更喜欢使用各种专用折叠(.size、.exists、.sum、.product)。我发现它比一般折叠的重型力量更清晰、更容易出错。

代码语言:javascript
复制
val complete = groupRows.view.filter(_.time==0).size
(complete, groupRows.length - complete)
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/13942106

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档