스칼라 병렬 정렬 java.util.Arrays 및 scala.concurrent.ops.par을 사용하여

Question

내 코드를 잘못 구현 한 것 같습니다. 필자의 sort (array.sort 사용)가 비 병렬 버전보다 "병렬"버전에서 더 오랜 시간이 걸리는 이유를 알 수는 없습니다 (분명히 두 배열을 함께 다시 넣는 것입니다. 훨씬 더 많은 시간). 만약 누군가 제가 실수를 지적하거나 비 병렬 버전을 통해 병렬 버전을 개선하기위한 조언을 주시면 고맙겠습니다. 배열 병합을보다 효율적으로 수행 할 수 있습니까? 아니면 병렬 처리 할 수 ​​있습니까? 그렇다면 구현을위한 가장 좋은 방법은 무엇입니까? 어떤 도움이라도 대단히 감사하겠습니다. 인텔 코어 i7에

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

    } 
} 

출력 :

Simple Time Taken: 0.01314 
Parallel Time Taken: 0.05882 

Answer 1

난 당신이 여기에 무슨 다른 몇 가지를 가지고 생각합니다. 첫째, 내 시스템에서 ops.par(Arrays.sort(...)) 라인 그 자체가은 모두 Simple.doSort()보다 오래 걸립니다. 그래서 작은 배열에 대한 성능 향상을 지배하는 오버 헤드 (스레드 생성?)가 있어야합니다. 100,000 개 또는 100 만 개 요소를 사용해보십시오. 둘째, Arrays.sort은 적절한 정렬이므로 결과에 대해 새 10k 요소 배열을 만드는 데 드는 비용이 들지 않습니다. 두 번째 배열을 생성 방지하기 위해

, 당신은 내가 병렬 버전 수행을 참조 할, 100,000에 배열 크기 흐름이 완만 한 후 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 
} 

로, 첫 번째 파티션을 다음 병렬로 두 반쪽을 정렬 할 수 있습니다 Intel E5300 CPU에서 약 2 배의 속도 향상.