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

Question

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

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

Answer 1

给一个尝试fork/join framework by 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）

Answer 2

你可能没有考虑这一点，但它可能会帮助看一下，从更高层次上的具体问题，例如，如果您不仅仅排序一个数组或列表，使用传统算法可以更容易地同时对各个集合进行排序，而不是尝试同时对单个集合进行排序。

Answer 3

为什么你认为平行排序会有帮助？我认为大多数排序是I/O界限，而不是处理。除非你的比较做了很多计算，否则加速是不太可能的。

Answer 4

对不起，但你要求的是不可能的。我相信别人提到排序是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(); 
       } 
      } 
     } 
    } 
} 

Answer 5

我最近几天一直在面对多线程排序问题。正如on this caltech slide所解释的那样，只需简单地多线程处理线程明显数量（分割数）上的分割和征服方法的每一步就能做到最好。我想这是因为虽然你可以在你的机器的所有64个内核的64个线程上运行64个分区，但这4个分区只能运行在4个线程，2个2和1个1等等上，所以对于很多级别递归的机器未被充分利用。

昨晚我发现了一个解决方案，可能对我自己的工作很有用，所以我会在这里发布。

因此，你的排序函数的第一个标准是基于最大尺寸s的整数，可以是一个实际的整数或字符串中的字符，例如这个整数或字符完全定义了排序的最高级别，那么我认为有一个非常快速（和简单）的解决方案。只需使用该初始整数将排序问题分为较小的排序问题，然后使用您选择的标准单线程排序算法对其进行排序。我认为，可以一次性完成对各个班级的划分。在完成独立排序之后没有合并问题，因为您已经知道第1课中的所有内容都在第2课之前排序，依此类推。

示例：如果您希望根据strcmp（）进行排序，则使用字符串中的第一个字符将数据分为256个类，然后在下一个可用线程中对每个类进行排序，直到完成全部任务。

这种方法充分利用了所有可用的内核，直到问题解决，我认为它很容易实现。尽管如此，我还没有实现它，所以可能存在我还没有找到的问题。它显然不适用于浮点类型，并且对于大型s来说效率不高。它的性能也将严重依赖于用于定义类的整数/字符的熵。

这可能是Fabian Steeg用较少的话来建议的，但我明确表示在某些情况下可以从更大的排序中创建多个更小的排序。

Answer 6

刚刚编码了上面的MergeSort和性能非常差。

代码块引用“coInvoke（left，right）;”但没有提及这个，并用invokeAll（左，右）替换它;

测试代码：

MergeSort mysort = new MyMergeSort(array,0,array.length); 
ForkJoinPool threadPool = new ForkJoinPool(); 
threadPool.invoke(mysort); 

但不得不停止它因表现不佳。

我看到上面的文章已经快一年了，也许事情现在已经改变了。

我发现替代本文中的代码的工作：http://blog.quibb.org/2010/03/jsr-166-the-java-forkjoin-framework/

Answer 7

爪哇8提供java.util.Arrays.parallelSort，其使用fork-join框架并行排序阵列。该文件提供了有关当前执行的一些细节（但这些都是不规范票据）：

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

似乎没有成为列表（即使RandomAccess列表应该玩排序不错）相应的并行排序方法，所以你需要使用toArray，那种阵列，并将结果返回到列表。 （我已经问了一个关于这个问题here。）