处理scala.collections.parallel中令人惊讶的ParList缺失

Question

因此scala 2.9最近出现在Debian测试中,带来了新奇的并行集合.

假设我有一些相当于的代码

  def expensiveFunction(x:Int):Int = {...}

  def process(s:List[Int]):List[Int} = s.map(expensiveFunction)

现在,在我的机器上实际显示文档之前,我已经收集到了关于并行集合的那些内容,我希望通过将List切换到ParList... 来并行化这个...但令我惊讶的是,没有一个!(只是ParVector,ParMap,ParSet...).

作为一个工作区,这个(或一行等效)似乎运作良好:

  def process(s:List[Int]):List[Int} = {
    val ps=scala.collection.parallel.immutable.ParVector()++s
    val pr=ps.map(expensiveFunction)
    List()++pr
  }

在我的测试代码中实现了大约x3的性能提升,并实现了更高的CPU使用率(四核和超线程i7).但它似乎有点笨重.

我的问题是一种汇总的:

• 为什么没有ParList？
• 鉴于没有ParList,我应该采用哪种更好的模式/习语,以至于我不觉得他们错过了？
• 在我的scala程序中,我只是"在时代背后"使用了很多列表(就像我在2.7天内买过的所有Scala书籍一样)我应该更多地使用它 Vectors？(我指的是C++的土地,我通常会需要一个很好的理由使用 std::list过std::vector).

Answer 1

List当你想要模式匹配(即case x :: xs)和有效的前置/迭代时,s很棒.但是,当您想要快速访问索引,或拆分成块或加入(即xs ::: ys)时,它们并不是那么好.

因此,List当您认为这种事物(分裂和连接)正是高效并行性所需要的时候,没有多大意义(并行).使用:

xs.toIndexedSeq.par

Answer 2

首先,让我向您展示如何制作该代码的并行版本:

def expensiveFunction(x:Int):Int = {...}

def process(s:List[Int]):Seq[Int] = s.par.map(expensiveFunction).seq

这将让Scala为您解决问题 - 顺便说一句,它使用ParVector.如果你真的想要List,请致电.toList而不是.seq.

至于问题:

• 没有ParList因为a List是本质上非并行的数据结构,因为对它的任何操作都需要遍历.

• 你应该代码,性状,而不是类- Seq,ParSeq并且GenSeq,例如.甚至a的性能特征List也得到保证LinearSeq.

• Scala 2.8之前的所有书籍都没有考虑新的馆藏库.特别是,这些集合确实没有共享一致且完整的API.现在他们做了,你将通过利用它获得更多.

  此外,没有VectorScala 2.7中的集合 - 具有(近)常量索引访问的不可变集合.

Answer 3

A List不能轻易地拆分成各种子列表,这使得难以并行化.首先,它有O(n)访问权限; 也是一个List不能去掉它的尾巴,所以需要包含一个长度参数.

我想,采取一个Vector将是更好的解决方案.

请注意,Scala Vector不同于std::vector.后者基本上是标准数组的包装器,是内存中的连续块,需要在添加或删除数据时不时复制.Scala Vector是一种专用数据结构,允许有效复制和拆分,同时保持数据本身不可变.