Java中的并发排序 [英] Concurrent sorting in Java

问题描述

我目前正在开发一个同时对字符串进行排序的程序。我的程序接收一个文件，将文件的每一行读入一个数组，并将字符串数组拆分成较小的字符串数组。然后程序为每个较小的阵列启动一个线程，并快速排序。一旦每个线程完成对其数组的排序，主线程就会收集线程对象的所有结果。然后它应该将较小的，现在排序的数组合并为一个大的排序数组。

I am currently working on a program to sort strings concurrently. My program takes in a file, reads each line of the file into an array, and splits the array of strings into smaller arrays of strings. The program then starts up one thread for each of the smaller arrays, and quicksorts them. Once every thread has finished sorting its array, the main thread gathers all the results from the thread objects. It is then supposed to merge the smaller, now sorted, arrays into one large, sorted array.

我知道我的快速排序实现有效 - 使用一个线程程序对单词进行排序。我需要的是一个算法，用于将线程返回的数组嵌套在一起。

I know for a fact that my quicksort implementation works -- using one thread the program sorts the words. What I need is an algorithm to nest together the arrays returned by the threads.

感谢任何帮助 - 提前感谢。

Any help is appreciated -- thanks in advance.

推荐答案

从合并程序开始/ wiki / Merge_sortrel =nofollow> mergesort 。您读取每个m数组的第一个值（单个子数组的最小值），然后选择m个读取值的最小值（全局最小值），将其推入结果中并从包含的数组中删除它或增加相应的索引一个。然后，迭代直到所有子数组都为空，或者所有索引都到达相应数组的末尾。

Start from the final merge procedure of mergesort. You read the first value of each of your m arrays (minimum of the single subarray), then you pick the minimum of the m read values (global minimum), push it in the result and and remove it from the containing array or increment the respective index by one. Then, iterate until all subarrays are empty, or all indexes have reached the end of the respective arrays.

注意：如果你有一个非常大的数据集，这可能会减少内存使用量（它实际上用于处理这种情况），但由于分割成本（如果复制子阵列变为线性）和多线程开销，可能比原始Quicksort表现更差。考虑到应用于大型数组时，就地Mergesort更节省空间。还要考虑一下你编写Quicksort的人可能花时间优化调用和分支执行。

NOTE: This may reduce memory usage if you have a really large dataset (it is actually used to handle such situations), but may perform worse than raw Quicksort beacause of the split cost (which becomes linear if you copy over the subarrays) and the multithreading overhead. Consider that inplace Mergesort is more space-efficient when applied to large arrays. Consider also that who wrote the Quicksort you are using probably spent time optimizing the calls and branch execution.

这是基本的理论CS，但请注意，你不能降低计算复杂度只需使用并行性，您只能获得线性加速。最后，Quicksort恰好达到了比较排序算法的平均复杂度的下限：如果你试图超越Quicksort O（nlog（n））我有坏消息对你而言。

This is basic theoretical CS, but note that you cannot lower the computational complexity class simply by using parallelism, you only get a linear acceleration. Finally, Quicksort happens to hit the lower limit of average complexity for comparision-sorting algorithms: if you are trying to outperform the Quicksort O(nlog(n)) I have bad news for you.

这篇关于Java中的并发排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！