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

sorting multithreading java mergesort quicksort

2022-09-01 17:27:43

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

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

我在Web上找到的唯一一个是如何在Java中编写多线程快速排序的示例，它是忙碌循环（这真的很可怕）使用：

while (helpRequested) { }

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

因此，除了无缘无故地丢失一个线程之外，它还确保通过在那个 while 循环中忙于循环来杀死性能（这令人难以置信）。

因此，我的问题是：您是否知道Java中任何正确的多线程快速排序或合并排序实现，这些实现将来自信誉良好的来源？

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

因此，即使困难的复杂性也保持在O（n log n）中，我真的很感激x7或x8甚至x16加速。

答案 1

尝试使用 Doug Lea 的分叉/加入框架：

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)

答案 2

Java 8 提供了 java.util.Arrays.parallelSort，它使用 fork-join 框架对数组进行并行排序。该文档提供了有关当前实现的一些详细信息（但这些都是非规范性说明）：

排序算法是一种并行排序合并，它将数组分解为子数组，这些子数组本身进行排序然后合并。当子数组长度达到最小粒度时，将使用相应的 Arrays.sort 方法对子数组进行排序。如果指定数组的长度小于最小粒度，则使用相应的 Arrays.sort 方法对其进行排序。该算法需要的工作空间不大于原始数组的大小。ForkJoin 公共池用于执行任何并行任务。

列表似乎没有相应的并行排序方法（即使RandomAccess列表应该可以很好地进行排序），因此您需要使用，对该数组进行排序，并将结果存储回列表中。（我在这里问了一个关于这个问题的问题。toArray