如何为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加速.