多线程快速排序或合并排序 [英] Multithreaded quicksort or mergesort

问题描述

如何为Java实现并发快速排序或合并排序算法？

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

我们在一个只有一个核心的16-（虚拟）核心Mac上遇到过问题（！）正在使用默认的Java排序算法，并且很好地看到非常好的机器被完全未充分利用。所以我们编写了自己的（我写的）并且我们确实获得了很好的加速（我编写了一个多线程的快速排序，由于它的分区性质，它很好地并行化，但我也可以编写一个mergesort）...但是我的实现只能扩展最多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.

我发现的唯一一个在Web上是一个如何不在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) { }

< a href =http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html =nofollow noreferrer> http://broadcast.oreilly.com/2009/06/may -column-multithreaded-algor.html

因此，除了无缘无故地丢失一个线程之外，它确保通过忙碌循环来消除穿孔while循环（最小值dboggling）。

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中任何正确的多线程快速排序或mergesort实现来自信誉良好的来源？

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 ）

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