斯卡拉ParArray排序

如何按升序排序ParArray收集诸如斯卡拉ParArray排序

ParArray(1,3,2)

否则，其并行收集可能更适合于这一目的？

更新

如何落实ParArray并行算法可能比铸造非平行集合顺序排序更有效率？

来源

2014-05-16 elm

我想你最好的选择是使用合并排序算法。你可以尝试使用Hadoop和MapReduce来实现它。 – goral

[这个问题]的答案（http://stackoverflow.com/questions/3969813/which-parallel-sorting-algorithm-has-the-best-average-case-performance）应该提供你正在寻找的答案。 – DCKing

如何落实ParArray并行算法可能比铸造非平行集合顺序排序更效率？

我的第一个obvervation将是那里似乎没有多大的性能损失“转换”平行阵列顺序和回：

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阻止我们做任何事情，可欣赏乐趣。似乎没有任何Scala内置机制（除视图外）仅对一部分集合进行排序。这就是为什么我尝试使用def mergeSort(a: Array[Int], r: Range): Unit的签名来编码我自己的合并排序算法，以便如上所述使用它。不幸的是，它似乎比scala Array.sorted方法的效率低4倍以上，所以我不认为它可以用来提高标准顺序方法的效率。

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

来源

2014-05-24 16:07:13 nietaki

在Scala标准库中没有可用的并行排序算法。因此，并行收集不提供sorted,sortBy或sortWith方法。您必须在排序之前将其转换为适当的顺序课程（例如，使用toArray）。

来源

2014-05-16 22:32:52 wingedsubmariner

感谢您的回复，请注意此问题的更新。 – elm

如果你的数据可以放在内存中，那么内存中的单线程排序就足够快了。如果您需要从磁盘或HDFS加载大量数据，那么您可以在分布式系统上进行排序，如hadoop或spark。

来源

2014-05-19 07:45:52 cloud

这是一个很好的观察，但它更喜欢轻量级的方法;理想情况下是一个在Scala中的实现。 – elm

如果你建立在Java 8的斯卡拉项目，还有就是new Arrays.parallelSort可以使用：

def sort[T <: Comparable](parArray: ParArray[T])(implicit c: ClassTag[T]): ParArray[T] = { 
    var array = new Array[T](parArray.size) // Or, to prevent copying, var array = parArray.seq.array.asInstanceOf[Array[T]] might work? 
    parArray.copyToArray(array) 
    java.util.Arrays.parallelSort(array) 
    ParArray.createFromCopy(array) 
}

来源

2014-05-30 13:09:23 DCKing

def parallelSort[A : Ordering](seq: ParIterable[A]): TreeSet[A] = { 
    seq.aggregate[TreeSet[A]](TreeSet.empty[A])(
    (set, a) => set + a, 
    (set, set) => set ++ set) 
}

来源

2018-01-17 12:24:55 ilyxa

斯卡拉ParArray排序

回答

相关问题