我目前正在开发一个同时对字符串进行排序的程序。我的程序接收一个文件，将文件的每一行读入一个数组，然后将字符串数组拆分为更小的字符串数组。然后程序为每个较小的数组启动一个线程，并对它们进行快速排序。一旦每个线程完成对其数组的排序，主线程就会从线程对象中收集所有结果。然后应该将较小的、现已排序的数组合并为一个大的、已排序的数组。
我知道我的快速排序实现是有效的——程序使用一个线程对单词进行排序。我需要的是一种将线程返回的数组嵌套在一起的算法。
任何帮助表示赞赏 - 在此先感谢。
问问题
3722 次
4 回答
4
从mergesort的最后一个merge过程开始。您读取每个 m 数组的第一个值（单个子数组的最小值），然后选择 m 个读取值中的最小值（全局最小值），将其推送到结果中，然后将其从包含数组中删除或递增相应的索引加一。然后，迭代直到所有子数组为空，或者所有索引都到达各自数组的末尾。
注意：如果您有一个非常大的数据集（它实际上用于处理这种情况），这可能会减少内存使用量，但由于拆分成本（如果您复制子数组将变为线性）和多线程开销。考虑到当应用于大型数组时，就地合并排序更节省空间。还要考虑编写您正在使用的快速排序的人可能花费时间优化调用和分支执行。
这是基本的理论 CS，但请注意，您不能简单地通过使用并行性来降低计算复杂度等级，您只能获得线性加速。最后，Quicksort 碰巧达到了比较排序算法的平均复杂度的下限：如果你想超越 Quicksort O(nlog(n))，我有个坏消息要告诉你。
于 2013-05-06T12:17:46.180 回答
1
就像其他帖子中提到的那样，算法的最后一步是合并排序。
但是，快速排序本身是一种递归算法，允许自然地引入并发，这样您的“合并步骤”就已过时，请参见http://ricardozuasti.com/2012/java-concurrency-examples-forkjoin-framework/
在枢轴元素处于其最终位置后，您可以在两个分区上调用快速排序。这可以同时进行。由于这是递归的，它将跨越其他线程。
于 2013-05-06T12:35:03.290 回答
1
我认为使用合并排序是非常标准的。
我建议使用尽可能多的线程作为开始的 CPU。
您可能会发现读取文件的时间比例很高，因此可以在读取字符串时对字符串进行排序的方法可能会更快。
例如，使用 TreeSets 进行基数排序可能会更快，因为它会在您读取文件时进行排序。
于 2013-05-06T12:04:43.403 回答
1
您可以在此处使用合并程序。该算法非常简单，请参阅维基百科上的合并排序。使用可以在两个数组合并时使用简单的双向合并，或者在同时合并多个数组时使用多路合并。
另外，检查这项工作：Parallelized QuickSort 和 RadixSort with Optimal Speedup。
最后，还有可以并行的 3 路字符串快速排序。
于 2013-05-06T12:20:24.300 回答