当前位置: 首页 > 面试题库 >

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

徐峰
2023-03-14
问题内容

如何为Java实现并发的quicksort或mergesort算法?

我们在16(虚拟)核的Mac上遇到问题,其中只有一个核(!)使用默认的Java排序算法工作,而且很好的机器没有得到充分利用是不好的。因此,我们编写了自己的代码(我编写了代码),并且确实取得了不错的提速(我编写了多线程快速排序,由于其分区特性,它可以很好地并行化,但我也可以编写合并排序)……但是我的实现只能扩展最多4个线程,这是专有代码,我宁愿使用一个来自知名来源的线程,也不要使用重新发明的轮子。

我在网上找到的唯一一个例子是如何不使用Java编写多线程快速排序的示例,它使用以下命令进行忙循环(这确实很糟糕):

while (helpRequested) { }

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

因此,除了无缘无故丢失一个线程外,还要确保通过在while循环中进行忙循环来杀死perfs(这令人难以置信)。

因此,我的问题是:你是否知道有信誉良好的Java中正确的多线程quicksort或mergesort实现?

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

因此,即使复杂度保持为O(n log n),我也非常感谢x7或x8甚至x16的加速。


问题答案:

尝试使用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);
        }
    }
}


 类似资料:
  • 问题内容: 我正在尝试使用Java并行化算法。我从合并排序开始,然后在这个问题上发表了自己的尝试。我修改后的尝试在下面的代码中,在这里我尝试并行化快速排序。 我的多线程实现或方法中是否有菜鸟错误?如果不是,我是否应该期望对决核上的顺序算法和并行算法之间的速度提高超过32%(请参阅底部的时序)? 这是多线程算法: 这是我的开始方式: 我针对Arrays.sort和类似的顺序快速排序算法进行了测试。以

  • 问题内容: [http://jsperf.com/optimized-mergesort-versus- quicksort][1] 为什么这个半缓冲区合并排序的工作速度与quicksort一样快? QuickSort是: 就地虽然会占用递归(堆栈空间) 缓存友好 这一半缓冲区合并排序: 使用Buffer进行合并。 使用递归。 进行较少的比较。 我的问题是,在这种情况下,为什么半缓冲区合并排序与Q

  • 问题:Mergesort将一个数字列表分成两半,并对这两个数字进行递归调用。相反,您能在左半部分执行quicksort,在右半部分执行mergesort吗?如果是,则通过显示每个步骤来显示它将如何对下面的数字列表进行排序。如果没有,请解释为什么不能。 Iam应该使用MergeSort对数字列表进行排序。左半部分将使用快速排序进行排序? 我想出来了。安:是的,我们可以 使用mergeSort对数组的

  • 快速排序 from typing import List def quick_sort(arr: List, left, right) -> List: """ 快速排序是对冒泡排序的改进,核心思想是找到一个中值点pivot,然后将小于等于pivot的放在pivot的左边,大于pivot的放在右边,一直递归到无法拆分pivot点。 :param arr: :re

  • 在处理接近排序的数组时,哪种算法的快速排序或合并排序性能更好?为什么?我意识到,在这种情况下,其他算法可能会比这些算法表现得更好。

  • 本文向大家介绍Java迭代快速排序程序,包括了Java迭代快速排序程序的使用技巧和注意事项,需要的朋友参考一下 下面是用于迭代快速排序的Java程序 示例 输出结果 一个名为Demo的类包含3个函数,“swap”用于使用临时变量交换值,一个“partition”函数根据主元素值将数组分为两半,以及“quick_sort”函数,该函数使用主元素值并基于该值对数组中的值进行排序。 在main函数中,将