Scala ParArray 排序

Question

如何按升序对 ParArray 集合进行排序，例如

ParArray(1,3,2)

否则，哪些并行集合可能更适合此目的？

更新

如何在 ParArray 上实现并行算法，这可能比强制转换为非并行集合以进行顺序排序更有效？

Answer 1

How to implement a parallel algorithm on ParArray that may prove more efficient than casting to a non parallel collection for sequential sorting?

我的第一个观察是，将并行数组“转换”为顺序数组并返回似乎没有太多性能损失:

def time[R](block: => R): R = {
  val t0 = System.nanoTime()
  val result = block    // call-by-name
  val t1 = System.nanoTime()
  val diff: Long = t1 - t0
  println(s"Elapsed time: ${diff * 1.0 / 1E9}s")
  result
}

def main(args: Array[String]): Unit = {
  val size: Int = args.headOption.map(_.toInt).getOrElse(1000000)
  val input = Array.fill(size)(Random.nextInt())
  val arrayCopy: Array[Int] = Array.ofDim(size)
  input.copyToArray(arrayCopy)
  time { input.sorted }
  val parArray = arrayCopy.par
  val result = time { parArray.seq.sorted.toArray.par }
}

给予

> run 1000000
[info] Running Runner 1000000
Elapsed time: 0.344659236s
Elapsed time: 0.321363896s

对于所有 Array 大小，我测试的结果非常相似，并且通常以某种方式支持第二个表达式。因此，如果您担心转换为顺序集合并返回会破坏您在其他操作中获得的性能提升 - 我认为您不应该担心。

当谈到利用 Scala 的并行集合实现并行排序时，在某些情况下会比默认的执行得更好——我认为没有明显的好方法，但尝试一下也无妨:

我认为应该可行的是将输入数组拆分为与您的计算机中的内核一样多的子数组(最好没有任何不必要的复制)并同时对这些部分进行排序。之后可能会将这些部分合并(如 merge sort 中)。代码可能如下所示:

val maxThreads = 8 //for simplicity we're not configuring the thread pool explicitly
val groupSize:Int = size/maxThreads + 1
val ranges: IndexedSeq[(Int, Int)] = (0 until maxThreads).map(i => (i * groupSize, (i + 1) * groupSize))
time {
  //parallelizing sorting for each range
  ranges.par.foreach {case (from, to) =>
    input.view(from, to).sortWith(_ < _)
  }
  //TODO merge the parts together
}

不幸的是 this old bug这会阻止我们对 View 做任何有趣的事情。似乎没有任何 Scala 内置机制( View 除外)仅用于对集合的一部分进行排序。这就是为什么我尝试使用 def mergeSort(a: Array[Int], r: Range): Unit 的签名编写我自己的合并排序算法，以便如上所述使用它。不幸的是，它的效率似乎比 scala Array.sorted 方法低 4 倍以上，因此我认为它不能用于提高标准顺序方法的效率。

如果我正确理解您的情况，您的数据集适合内存，因此使用 Hadoop 和 MapReduce 之类的东西还为时过早。你可能会尝试的是 Apache Spark - 除了添加依赖项之外，您不需要设置任何集群或安装任何东西，Spark 就可以在基本配置中使用您机器的所有核心。它的 RDD 在思想上类似于 Scala 的并行集合，但具有额外的功能。它们 ( in a way ) 支持并行排序。