多线程快速排序或合并排序
我怎样才能为Java实现一个并发的quicksort或mergesort算法？
我们在16位（虚拟）核心Mac上出现了问题，其中只有一个核心（！）正在使用默认的Java排序算法，而且很不好看到这台非常精细的机器被完全滥用。 所以我们写了自己的（我写了它），并且确实获得了很好的加速（我写了一个多线程的快速排序，并且由于它的分区性质，它很好地并行化，但我也可以写一个mergesort）但是我的实现只是扩展多达4个线程，它是专有代码，我宁愿使用来自信誉良好的源代码，而不是使用我重新发明的轮子。
我在网上找到的唯一例子就是如何不用 Java编写多线程快速排序，它是使用以下代码进行繁忙循环（这非常糟糕）：
while (helpRequested) { }
http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html
所以除了无缘无故地丢失一个线程之外，它还要确保通过在while循环中进行繁忙循环来杀死perfs（这是令人惊叹的）。
因此我的问题是：你是否知道任何正确的多线程quicksort或Java中的合并实现将来自信誉良好的源代码？
我把重点放在了我知道复杂性保持O（n log n）的事实上，但我仍然非常乐意看到所有这些内核开始工作而不是闲置。 请注意，对于其他任务，在同一个16个虚拟核心Mac上，我通过并行化代码（我并不是指并发专家）加速到x7。
所以即使艰难的复杂性保持O（n log n），我真的很感激x7或x8甚至x16的加速。
Doug Lea尝试fork / join框架：
public class MergeSort extends RecursiveAction {
final int[] numbers;
final int startPos, endPos;
final int[] result;
private void merge(MergeSort left, MergeSort right) {
int i=0, leftPos=0, rightPos=0, leftSize = left.size(), rightSize = right.size();
while (leftPos < leftSize && rightPos < rightSize)
result[i++] = (left.result[leftPos] <= right.result[rightPos])
? left.result[leftPos++]
: right.result[rightPos++];
while (leftPos < leftSize)
result[i++] = left.result[leftPos++];
while (rightPos < rightSize)
result[i++] = right.result[rightPos++];
}
public int size() {
return endPos-startPos;
}
protected void compute() {
if (size() < SEQUENTIAL_THRESHOLD) {
System.arraycopy(numbers, startPos, result, 0, size());
Arrays.sort(result, 0, size());
} else {
int midpoint = size() / 2;
MergeSort left = new MergeSort(numbers, startPos, startPos+midpoint);
MergeSort right = new MergeSort(numbers, startPos+midpoint, endPos);
coInvoke(left, right);
merge(left, right);
}
}
}
（来源：http://www.ibm.com/developerworks/java/library/j-jtp03048.html?S_TACT=105AGX01&S_CMP=LP）
对此抱歉，但你所要求的是不可能的。 我相信别人提到排序是IO界限，他们很可能是正确的。 来自IBM的Doug Lea的代码是一件很好的工作，但我相信它主要是作为如何编写代码的一个例子。 如果你在他的文章中注意到，他从未发布过基准，而是发布了其他工作代码的基准，例如计算平均值和并行寻找最小最大值。 如果您使用通用合并排序，快速排序，使用加入分叉池的双合并排序，以及使用快速排序加入分叉池编写的基准，以下是测试的基准。 你会看到合并排序对于100或更小的N是最好的。 快速排序1000到10000，如果你有100000和更高的分数，使用加入分叉池的快速排序比其他的快。 这些测试是运行30次的随机数组的阵列，为每个数据点创建一个平均值，并且运行在具有大约2个RAM的四核上。 在下面我有快速排序的代码。 这大多表明，除非你试图对一个非常大的数组进行排序，否则你应该退出尝试改进你的代码排序算法，因为并行的在小N上运行速度非常慢。
Merge Sort
10 7.51E-06
100 1.34E-04
1000 0.003286269
10000 0.023988694
100000 0.022994328
1000000 0.329776132
Quick Sort
5.13E-05
1.60E-04
7.20E-04
9.61E-04
0.01949271
0.32528383
Merge TP
1.87E-04
6.41E-04
0.003704411
0.014830678
0.019474009
0.19581768
Quick TP
2.28E-04
4.40E-04
0.002716065
0.003115251
0.014046681
0.157845389
import jsr166y.ForkJoinPool;
import jsr166y.RecursiveAction;
// derived from
// http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html
// Copyright © 2007, Robert Sedgewick and Kevin Wayne.
// Modified for Join Fork by me hastily.
public class QuickSort {
Comparable array[];
static int limiter = 10000;
public QuickSort(Comparable array[]) {
this.array = array;
}
public void sort(ForkJoinPool pool) {
RecursiveAction start = new Partition(0, array.length - 1);
pool.invoke(start);
}
class Partition extends RecursiveAction {
int left;
int right;
Partition(int left, int right) {
this.left = left;
this.right = right;
}
public int size() {
return right - left;
}
@SuppressWarnings("empty-statement")
//void partitionTask(int left, int right) {
protected void compute() {
int i = left, j = right;
Comparable tmp;
Comparable pivot = array[(left + right) / 2];
while (i <= j) {
while (array[i].compareTo(pivot) < 0) {
i++;
}
while (array[j].compareTo(pivot) > 0) {
j--;
}
if (i <= j) {
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}
}
Partition leftTask = null;
Partition rightTask = null;
if (left < i - 1) {
leftTask = new Partition(left, i - 1);
}
if (i < right) {
rightTask = new Partition(i, right);
}
if (size() > limiter) {
if (leftTask != null && rightTask != null) {
invokeAll(leftTask, rightTask);
} else if (leftTask != null) {
invokeAll(leftTask);
} else if (rightTask != null) {
invokeAll(rightTask);
}
}else{
if (leftTask != null) {
leftTask.compute();
}
if (rightTask != null) {
rightTask.compute();
}
}
}
}
}
Java 8提供了java.util.Arrays.parallelSort ，它使用fork-join框架并行排列数组。 文档提供了一些关于当前实现的细节（但这些是非规范性注释）：
排序算法是一种并行排序合并，将数组分解为自己排序然后合并的子数组。 当子数组长度达到最小粒度时，使用适当的Arrays.sort方法对子数组进行排序。 如果指定数组的长度小于最小粒度，则使用适当的Arrays.sort方法对其进行排序。 该算法需要一个不大于原始数组大小的工作空间。 ForkJoin公共池用于执行任何并行任务。
似乎没有相应的列表并行排序方法（即使RandomAccess列表应该在排序时表现良好），所以您需要使用toArray ，对该数组进行排序，然后将结果存储回列表中。 （我在这里问过一个关于这个问题。）