Ree*_*d B 0 c sorting algorithm performance multithreading
正如标题所示,我需要制作比快速排序更快的算法.有问题的快速排序已经过优化,并在一个天真的并行系统中使用,因此单个线程完全执行每个快速排序,但多个线程同时进行快速排序.我需要制作一个比这个过程更快的算法.通过让额外的线程执行对枢轴每一侧的排序或者这个过程有太多的开销并最终导致减速,并行每个快速排序会更快吗？有关算法的任何建议吗？
如果我理解正确,您目前有一个系统,其中N个排序由N个线程执行.每个单独的排序都由一个线程完成,但可以同时运行多个排序.您要问的是,编写并行排序算法是否更快,以便每个排序都由多个线程执行.
所以,假设你有4个处理器,你必须做10种.假设每种排序花费相同的时间(不切实际,但对讨论很有用),那么如果每个排序在单个线程中运行,则可以同时运行四种排序.调用时间执行一个单线程排序一个时间段.
因此,做各种各样的时间将是三个时间段.在两个时期内,您可以同时运行四种排序,并且在一个时间段内,您有两种并发排序.在上一个时间段内,您有多余的容量(两个空闲处理器).
如果你有一个使用四个线程的并行排序算法,那么最好的情况是每个排序将花费单线程排序的1/4.因此理论上你可以在10/4时间段内执行10种类型,这意味着它只需要2.5个时间段.
所以理论上你可以通过并行排序算法节省一半的时间.但是你不会意识到性能的提升,因为quicksort不是100%可并行化的; 有时会涉及少于四个线程.在每次排序期间,您都会随机处理空闲处理器.很可能使用并行版本总体上会更慢,因为那些小的空闲时间会加起来.
可以这样想:你有四个人需要做10个工作.他们可以分别完成这10项工作并单独完成,或通过合作完成这四项工作,使四项工作中的每项工作完成每项工作的1/4.完成的工作量没有差异.在第一种情况下,您有两个闲置工人,而最后两个工作正在完成.在第二种情况下,在最后一个工作完成时你有一些空闲时间; 工人1空闲3/4的时间段,工人2空闲1/2时间段,工人3空闲1/4的时间段.所以理论上你的总工人闲置时间是6/4,或1.5个时间段.
但是,将工作从工人1转移到工人2等也有空闲时间.这个过渡时间让两个工人都短暂闲置.那些小的时间(每个工作3个转换,加上工人1获得下一个工作和开始的时间,以及工人4交付成品的时间)加起来,并且很可能超过0.5个时间段.表面上得救了.
不过你可以尝试一下.并行化快速排序非常容易.例如,参见http://reedcopsey.com/2010/02/26/parallelism-in-net-part-11-divide-and-conquer-via-parallel-invoke/.