并行排序算法

《并行排序算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、并行排序算法先简单说一下给的A,B,C三种算法(见上面引用的那篇博客)，A算法将耗时的平方和开平方计算放到比较函数中，导致Array.Sort时，每次亮亮比较都要执行平方和开平方计算，其平均算法复杂度为O(nlog2n)。而B将平方和开平方计算提取出来，算法复杂度降低到O(n),这也就是为什么B比A效率要高很多的缘故。C和B相比，将平方函数替换成了xx,由于少了远程函数调用和Pow函数本身的开销，效率有提高了不少。我在C的基础上编写了D算法，D算法采用并行计算技术，在我的双核笔记本电脑上数据量比较大的情况下，其排序效率较C要提高30施右。下面重点介绍这个并行排序算法。算法思路其实很简单

2、，就是将要排序的数组按照处理器数量等分成若干段，然后用和处理器数量等同的线程并行对各个小段进行排序，排序结束和，再在单一线程中对这若干个已经排序的小段进行归并排序，最后输出完整的排序结果。考试大考虑到和.Net2.0兼容，没有用微软提供的并行库，而是用多线程来实现。下面是测试结果：nABCD327680.73450.041220.02160.0254精品资料655351.54640.088630.051390.051491310723.27060.18580.1180.1082621446.84230.40560.295860.2184952428815.03420.96890.731

3、80.4906104857631.63121.99781.46461.074209715266.91344.17633.08282.3095从测试结果上看，当要排序的数组长度较短时，并行排序的效率甚至还没有不进行并行排序高，这主要是多线程的开销造成的。当数组长度增大到25万以上时，并行排序的优势开始体现出来，随着数组长度的增长，排序时间最后基本稳定在但线程排序时间的74%左右，其中并行排序的消耗大概在50%左右，归并排序的消耗在14%左右。由此也可以推断，如果在4CPU勺机器上，其排序时间最多可以减少到单线程的14+25=39%。8CPU为14+12.5=26.5%。目前这个算法在归并

4、算法上可能还有提高的余地，如果哪位高手能够进一步提高这个算法，不妨贴出来一起交流交流。下面分别给出并行排序和归并排序的代码：并行排序类ParallelSortParalletsort类是一个通用的泛型，调用起来非常简单，下面精品资料给一个简单的int型数组的排序示例：classIntComparer:IComparer{IComparerMembers#regionIComparerMemberspublicintCompare(intx,inty){returnx.CompareTo(y);}#endregion}publicvoidSortInt(int[]array){

5、Sort.ParallelSortparallelSort=newSort.ParallelSort();parallelSort.Sort(array,newIntComparer());ParallelSort的只要实现一个T类型两两比较的接口，然后调用精品资料Sort方法就可以了，是不是很简单?下面是ParallelSort类的代码usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Threading;namespaceSort{//

6、//////ParallelSort//////publicclassParallelSort精品资料{enumStatus{精品资料{Idle=0,Running=1,Finish=2,}classParallelEntity{publicStatusStatus;publicT[]Array;publicIComparerComparer;publicParallelEntity(Statusstatus,T[]array,IComparercomparer){Status=status;精品资料Array=array;Comparer=comparer;}}pr

7、ivatevoidThreadProc(ObjectstateInfo){ParallelEntitype=stateInfoasParallelEntity;lock(pe){pe.Status=ParallelSort.Status.Running;Array.Sort(pe.Array,pe.Comparer);pe.Status=ParallelSort.Status.Finish;}}publicvoidSort(T[]a