Scala并行排序使用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()更长的时间。所以一定会有一些开销（线程创建？），这些开销占据了一小部分阵列的性能收益。尝试它的10万或一百万元素。其次，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后，我看到的平行版本执行英特尔E5300 CPU的速度是其两倍。