英文:
Parallel multiway merge sort for Unix
问题
我已经搜索过了，看看是否能找到在Unix命令行上运行的并行多路归并排序，但我找不到。
GNU Sort使用归并排序，但最终的合并是单线程的。parsort在最终的合并步骤中也是单线程的。
https://en.wikipedia.org/wiki/Merge_sort#Parallel_multiway_merge_sort 显示了如何并行化最终的合并步骤。
在我花时间实现维基百科上的多线程算法之前：
- 这已经有人做过了吗？
- 如果Unix没有命令行工具：是否至少有一个可以并行执行最终合并步骤的库（换句话说：我是否可以简单地为现有库创建一个命令行包装器）？
英文:
I have searched to see if I could find a parallel multiway merge sort that would run on a Unix command line. I could find none.
GNU Sort uses merge sort, but the final merge is single threaded. parsort is also single threaded in the final merge step.
https://en.wikipedia.org/wiki/Merge_sort#Parallel_multiway_merge_sort shows how it is possible to parallelize the final merge step.
Before I spend time on implementing the multithreaded algorithm from Wikipedia:
- Is this already done?
- If there is not a command line tool for Unix: Is there at least a library that does the final merge step in parallel (in other words: can I simply make a command line wrapper for an existing library?)?
答案1
得分: 0
- 这已经完成了吗？
截止发布日期 - 没有。所以你会是第一个。
- 如果没有Unix的命令行工具：至少有一个库来并行执行最终合并步骤吗（换句话说：我可以简单地为现有库创建一个命令行包装器吗）？
GNU parallel 扩展到 标准C++库 包括一个名为 multiway_mergesort.h 的文件，它实现了 并行多路归并排序。
MPDMSort 使用 OpenMP 库开发了该算法的并行实现，可以用来创建一个现有的 并行多路归并排序 实现的命令行包装器。
只是一些初始思考。
英文:
- Is this already done?
As of posting date - nope. So you'd be the 1st one
- If there is not a command line tool for Unix: Is there at least a library that does the final merge step in parallel (in other words: can I simply make a command line wrapper for an existing library?)?
A GNU parallel extension to the Standard C++ Library includes a file called multiway_mergesort.h which implements a parallel multiway merge sort
MPDMSort uses the OpenMP library to develop a parallel implementation of the algorithm which could be used to create a command line wrapper for an existing implementation of parallel multiway merge sort.
Just some starter thoughts
答案2
得分: 0
我怀疑实际上并不这样做，因为即使在多路归并中，合并已排序的列表也非常快，所以很可能一个单独的CPU核心就能饱和利用的I/O带宽。
回答你的问题，我反问你：你为什么认为通过优化最终合并来显著提高排序的性能呢？
英文:
I suspect this isn't done in practice because merging sorted lists, even in a multiway merge, is really fast, so it's likely that a single CPU core can saturate the available I/O bandwidth.
To answer your question with another question: why do you believe sort's performance could be significantly improved by optimizing the final merge?
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论