什么是多线程编程的最佳排序算法？

我想排序长度为1.000.000到100.000.000的整数数组。我想在使用pthread库的2Mb缓存的core2duo计算机上运行此程序。我想要最快的算法！什么是多线程编程的最佳排序算法？

我写了一个使用mergesort算法的半并行排序代码。但速度不够快！

  ___ sort___ 
     /   \   
     /____ sort ___\  __ merge __ 
    ___/    \___/   \___ merge 
     \ ____ sort ____/ \__ merge __/  
     \   /  
     \___ sort __/

来源

2011-11-10 Sohrab

你有什么试过？什么不起作用？向我们展示您遇到问题的代码段。 –

我写了使用合并排序算法的半并行排序代码。 – Sohrab

如果你发现它没有更快，那么你可能发现你的机器有多个内核，但只有一条内存总线。这是真正的瓶颈。 –

它已经有一段时间，因为我是在大学，但我好像记得PSRS算法好作这样的事情。我相信谷歌会揭示大量的实现/伪代码。

来源

2011-11-10 10:41:08 diagonalbatman

Quicksort很适合多线程。

当你进行分区时，分区的一边在当前线程中排序，另一端在一个新线程中排序。

来源

2011-12-08 18:01:47 Adrian

既然你是在core2duo上，我会看看一个并行Quicksort算法。它就地排序，节省内存，并且可以实现与多达少量处理器的处理器数量成正比的性能增益。

并行快速排序算法基本上执行分区步骤，然后在分开的进程中的左侧和右侧子列表上执行快速排序。这可以通过在共享堆栈中存储边界来实现，如果以更大的线程数运行，最终会成为争用的焦点。

还有其他一些算法，比如PSRS，可以扩展到更多的处理器，但是因为你在core2duo上，这可能会使你在2个真正的内核+两个超线程内核中达到最大值，PSRS所需的额外内存可能会是一种浪费。鉴于你想要分类的元素数量，你可能需要节省内存。

我已经在Github上用Java实现了两个。让我知道你是否愿意看代码作为使用pthreads实现某些东西的指南。

来源

2013-11-11 03:16:50 broadbear

什么是多线程编程的最佳排序算法？

回答

相关问题