多线程快速排序或归并排序

问题描述

如何为 Java 实现并发快速排序或归并排序算法?

How can I implement a concurrent quicksort or mergesort algorithm for Java?

我们在 16 核(虚拟)核 Mac 上遇到了问题，其中只有一个核(！)在使用默认的 Java 排序算法工作，而且看到非常好的机器完全没有得到充分利用是不好的.所以我们写了我们自己的(我写的)，我们确实获得了很好的加速(我写了一个多线程快速排序，由于它的分区性质，它并行化得很好，但我也可以写一个归并排序)......但我的实现只能扩展最多 4 个线程，它是专有代码，我宁愿使用来自信誉良好的来源的线程，而不是使用我重新发明的轮子.

We've had issues on a 16-(virtual)-cores Mac where only one core (!) was working using the default Java sorting algo and it was, well, not good to see that very fine machine be completely underused. So we wrote our own (I wrote it) and we did indeed gain good speedups (I wrote a multithreaded quicksort and due to its partitioning nature it parallelize very well but I could have written a mergesort too)... But my implementation only scales up to 4 threads, it's proprietary code, and I'd rather use one coming from a reputable source instead of using my re-invented wheel.

我在网上找到的唯一一个例子是如何不用 Java 编写多线程快速排序，它是忙循环(这真的很糟糕)使用:>

The only one I found on the Web is an example of how not to write a multi-threaded quicksort in Java, it is busy-looping (which is really terrible) using a:

while (helpRequested) { }

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

因此，除了无缘无故丢失一个线程之外，还要确保通过在该 while 循环中忙循环(这令人难以置信)来杀死性能.

So in addition to losing one thread for no reason it's making sure to kill the perfs by busy-looping in that while loop (which is mindboggling).

因此我的问题是:您是否知道 Java 中任何正确的多线程快速排序或归并排序实现都来自信誉良好的来源?

Hence my question: do you know of any correctly multithreaded quicksort or mergesort implementation in Java that would be coming from a reputable source?

我强调这样一个事实，即我知道复杂性保持为 O(n log n)，但我仍然很高兴看到所有这些内核开始工作而不是空闲.请注意，对于其他任务，在相同的 16 个虚拟内核 Mac 上，通过并行化代码，我看到了高达 x7 的加速(我绝不是并发方面的专家).

I put the emphasis on the fact that I know that the complexity stays O(n log n) but I'd still enjoy very much to see all these cores start working instead of idling. Note that for other tasks, on that same 16 virtual cores Mac, I saw speedup of up to x7 by parallelizing the code (and I'm by no mean an expert in concurrency).

所以即使复杂度保持 O(n log n)，我真的很感激 x7 或 x8 甚至 x16 加速.

So even tough the complexity stays O(n log n), I'd really appreciate a x7 or x8 or even x16 speedup.

推荐答案

尝试 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)

这篇关于多线程快速排序或归并排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！