Scala Parallel Sort使用java.util.Arrays和scala.concurrent.ops.par

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")

  }
}

英特尔酷睿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元素数组.

为避免创建第二个数组,您可以先执行分区,然后按照此处的建议并行对两个部分进行排序

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上的运行速度提高了两倍.