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

Question

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

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

我在Web上找到的唯一一个例子是如何不用 Java编写多线程快速排序,它使用的是繁忙循环(这非常糟糕):

while (helpRequested) { }

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

因此,除了无缘无故地丢失一个线程之外,它确保通过在while循环中忙碌循环来杀死perf(这是令人难以置信的).

因此我的问题是:您是否知道Java中正确的多线程快速排序或mergesort实现将来自信誉良好的来源？

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

所以即使很难复杂性保持O(n log n),我也非常欣赏x7或x8甚至x16加速.

Answer 1

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

Answer 2

Java 8提供了java.util.Arrays.parallelSort使用fork-join框架并行排序数组的方法.该文档提供了有关当前实现的一些详细信息(但这些是非规范性说明):

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

列表似乎没有相应的并行排序方法(即使RandomAccess列表应该对排序很好),因此您需要使用toArray,排序该数组,并将结果存储回列表中.(我在这里问了一个问题.)

Answer 3

对此抱歉,但您要求的是不可能的.我相信有人提到排序是IO绑定的,它们很可能是正确的.来自IBM的Doug Lea的代码是一个很好的工作,但我相信它主要是作为如何编写代码的一个例子.如果你在他的文章中注意到他从未公布过它的基准,而是发布其他工作代码的基准,例如计算平均值和并行找到最大值.如果您使用通用合并排序,快速排序,使用加入叉池的Dougs合并排序,以及使用快速排序加入叉池编写的排序,那么这些基准是什么.您会看到Merge Sort最适合N或100或更低.快速排序为1000到10000,如果您有100000或更高,使用Join Fork Pool进行快速排序可以胜过其余部分.这些测试是运行30次的随机数阵列,以创建每个数据点的平均值,并在具有大约2 gig 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();
                }
            }
        }
    }
}