java - 使用 java.util.Arrays 和 scala.concurrent.ops.par 的 Scala 并行排序

Question

我认为我的某些代码实现有误。我无法弄清楚为什么我的排序(使用 arrays.sort)在“并行”版本中比在非并行版本中花费的时间更长(显然是将两个数组放回一起，但我认为它不会添加更多的时间)。如果有人可以指出我正在犯的任何错误或任何改进非并行版本的并行版本的提示，我将不胜感激。我是否能够更有效地合并数组，甚至可以并行合并？如果是这样，实现的最佳做法是什么。任何帮助将不胜感激。

import java.util.Arrays
import scala.concurrent._
import scala.collection._

trait Sorts {
  def doSort(a: Array[Double]): Array[Double]
}

object Simple extends Sorts {
  def doSort(a: Array[Double]) = {
    Arrays.sort(a)
    a
  }
}

object Parallel extends Sorts {
  def doSort(a: Array[Double]) = {
    val newArray = new Array[Double](a.length)
    val aLength = (a.length)
    val aSplit = ((a.length / 2).floor).toInt
    ops.par(Arrays.sort(a, 0, aSplit), Arrays.sort(a, (aSplit + 1), aLength))
    def merge(w: Int, x: Int, y: Int) {
      var i = w
      var j = x
      var k = y
      while (i <= aSplit && j <= aLength) {
        if (a(i) <= a(j)) {
          newArray(k) = a(i)
          i = i + 1
        } else {
          newArray(k) = a(j)
          j = j + 1
        }
        k = k + 1
      }
      if (i < aSplit) {
        for (i <- i until aSplit) {
          newArray(k) = a(i)
          k = k + 1
        }
      } else {
        for (j <- j until aLength) {
          newArray(k) = a(j)
          k = k + 1
        }
      }
    }
    merge(0, (aSplit + 1), 0)
    newArray
  }
}

object Main {
  def main(args: Array[String]): Unit = {
    val simpleNumbers = Array.fill(10000)(math.random)
    println(simpleNumbers.toList + "\n")
    val simpleStart = System.nanoTime()
    Simple.doSort(simpleNumbers)
    val simpleEnd = System.nanoTime()
    println(simpleNumbers.toList + "\n")
    val simpleDifference = ((simpleEnd - simpleStart) / 1e9).toDouble

    val parallelNumbers = Array.fill(10000)(math.random)
    println(parallelNumbers.toList + "\n")
    val parallelStart = System.nanoTime()
    Parallel.doSort(parallelNumbers)
    val parellelEnd = System.nanoTime()
    println(parallelNumbers.toList + "\n")
    val parallelDifference = ((parellelEnd - parallelStart) / 1e9).toDouble

    println("\n Simple Time Taken: " + simpleDifference + "\n")
    println("\n Parallel Time Taken: " + parallelDifference + "\n")

  }
}

在 Intel Core i7 上的输出:

Simple Time Taken: 0.01314
Parallel Time Taken: 0.05882

Answer 1

我认为您在这里发生了一些不同的事情。首先，在我的系统上，ops.par(Arrays.sort(...)) 行本身 比所有 Simple.doSort()。因此，一定有一些开销(线程创建？)主导了小型数组的性能提升。尝试使用 100,000 或 100 万个元素。其次，Arrays.sort 是就地排序，因此不必为结果创建一个新的 10k 元素数组。

为避免创建第二个数组，您可以先进行分区，然后对两半进行并行排序，如recommended here

def doSort(a: Array[Double]) = {
  val pivot = a(a.length-1)
  var i = 0
  var j = a.length-2
  def swap(i: Int, j: Int) {
    val temp = a(i)
    a(i) = a(j)
    a(j) = temp
  }
  while(i < j-1) {
   if(a(i) <= pivot) {
    i+=1
   }
   else {
    swap(i,j)
    j-=1
   }
  }
  swap(j-1, a.length-1)
  ops.par(Arrays.sort(a,0,a.length/2), Arrays.sort(a,a.length/2+1,a.length))
  a
}

将阵列大小增加到 100k 后，我确实看到并行版本在 Intel E5300 CPU 上的执行速度大约是原来的两倍。