并行排序算法.doc
- 文档编号:2104668
- 上传时间:2023-05-02
- 格式:DOC
- 页数:24
- 大小:34KB
并行排序算法.doc
《并行排序算法.doc》由会员分享,可在线阅读,更多相关《并行排序算法.doc(24页珍藏版)》请在冰点文库上搜索。
并行排序算法
先简单说一下给的A,B,C三种算法(见上面引用的那篇博客),A算法将耗时的平方和开平方计算放到比较函数中,导致Array.Sort时,每次亮亮比较都要执行平方和开平方计算,其平均算法复杂度为O(nlog2n)。
而B将平方和开平方计算提取出来,算法复杂度降低到O(n),这也就是为什么B比A效率要高很多的缘故。
C和B相比,将平方函数替换成了x*x,由于少了远程函数调用和Pow函数本身的开销,效率有提高了不少。
我在C的基础上编写了D算法,D算法采用并行计算技术,在我的双核笔记本电脑上数据量比较大的情况下,其排序效率较C要提高30%左右。
下面重点介绍这个并行排序算法。
算法思路其实很简单,就是将要排序的数组按照处理器数量等分成若干段,然后用和处理器数量等同的线程并行对各个小段进行排序,排序结束和,再在单一线程中对这若干个已经排序的小段进行归并排序,最后输出完整的排序结果。
考试大考虑到和.Net2.0兼容,没有用微软提供的并行库,而是用多线程来实现。
下面是测试结果:
nABCD
327680.73450.041220.02160.0254
655351.54640.088630.051390.05149
1310723.27060.18580.1180.108
2621446.84230.40560.295860.21849
52428815.03420.96890.73180.4906
104857631.63121.99781.46461.074
209715266.91344.17633.08282.3095
从测试结果上看,当要排序的数组长度较短时,并行排序的效率甚至还没有不进行并行排序高,这主要是多线程的开销造成的。
当数组长度增大到25万以上时,并行排序的优势开始体现出来,随着数组长度的增长,排序时间最后基本稳定在但线程排序时间的74%左右,其中并行排序的消耗大概在50%左右,归并排序的消耗在14%左右。
由此也可以推断,如果在4CPU的机器上,其排序时间最多可以减少到单线程的14+25=39%。
8CPU为14+12.5=26.5%。
目前这个算法在归并算法上可能还有提高的余地,如果哪位高手能够进一步提高这个算法,不妨贴出来一起交流交流。
下面分别给出并行排序和归并排序的代码:
并行排序类ParallelSort
Paralletsort类是一个通用的泛型,调用起来非常简单,下面给一个简单的int型数组的排序示例:
classIntComparer:
IComparer
{
IComparerMembers#regionIComparerMembers
publicintCompare(intx,inty)
{
returnx.CompareTo(y);
}
#endregion
}
publicvoidSortInt(int[]array)
{
Sort.ParallelSort
parallelSort.Sort(array,newIntComparer());
}
只要实现一个T类型两两比较的接口,然后调用ParallelSort的Sort方法就可以了,是不是很简单?
下面是ParallelSort类的代码
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
usingSystem.Threading;
namespaceSort
{
/**////
///ParallelSort
///
///
publicclassParallelSort
{
enumStatus
{
Idle=0,
Running=1,
Finish=2,
}
classParallelEntity
{
publicStatusStatus;
publicT[]Array;
publicIComparer
publicParallelEntity(Statusstatus,T[]array,IComparer
{
Status=status;
Array=array;
Comparer=comparer;
}
}
privatevoidThreadProc(ObjectstateInfo)
{
ParallelEntitype=stateInfoasParallelEntity;
lock(pe)
{
pe.Status=ParallelSort
Array.Sort(pe.Array,pe.Comparer);
pe.Status=ParallelSort
}
}
publicvoidSort(T[]array,IComparer
{
//Calculateprocesscount
intprocessorCount=Environment.ProcessorCount;
//Ifarray.Lengthtooshort,donotuseParallelsort
if(processorCount==1||array.Length { Array.Sort(array,comparer); return; } //Splitarray ParallelEntity[]partArray=newParallelEntity[processorCount]; intremain=array.Length; intpartLen=array.Length/processorCount; //Copydatatosplitedarray for(inti=0;i { if(i==processorCount-1) { partArray[i]=newParallelEntity(Status.Idle,newT[remain],comparer); } else { partArray[i]=newParallelEntity(Status.Idle,newT[partLen],comparer); remain-=partLen; } Array.Copy(array,i*partLen,partArray[i].Array,0,partArray[i].Array.Length); } //Parallelsort for(inti=0;i { ThreadPool.QueueUserWorkItem(newWaitCallback(ThreadProc),partArray[i]); } ThreadProc(partArray[processorCount-1]); //Waitallthreadsfinish for(inti=0;i { while(true) { lock(partArray[i]) { if(partArray[i].Status==ParallelSort { break; } } Thread.Sleep(0); } } //Mergesort MergeSort List foreach(ParallelEntitypeinpartArray) { source.Add(pe.Array); } mergeSort.Sort(array,source,comparer); } } } 多路归并排序类MergeSort usingSystem; usingSystem.Collections.Generic; usingSystem.Linq; usingSystem.Text; namespaceSort { /**//// ///MergeSort /// /// publicclassMergeSort { publicvoidSort(T[]destArray,List { //MergeSort int[]mergePoint=newint[source.Count]; for(inti=0;i { mergePoint[i]=0; } intindex=0; while(index { intmin=-1; for(inti=0;i { if(mergePoint[i]>=source[i].Length) { continue; } if(min<0) { min=i; } else { if(comparer.Compare(source[i][mergePoint[i]],source[min][mergePoint[min]])<0) { min=i; } } } if(min<0) { continue; } destArray[index++]=source[min][mergePoint[min]]; mergePoint[min]++; } } } } 主函数及测试代码在蛙蛙池塘代码基础上修改 usingSystem; usingSystem.Collections.Generic; usingSystem.Diagnostics; namespaceVector4Test { publicclassVector { publicdoubleW; publicdoubleX; publicdoubleY; publicdoubleZ; publicdoubleT; } internalclassVectorComparer: IComparer { publicintCompare(Vectorc1,Vectorc2) { if(c1==null||c2==null) thrownewArgumentNullException("Bothobjectsmustnotbenull"); doublex=Math.Sqrt(Math.Pow(c1.X,2) +Math.Pow(c1.Y,2) +Math.Pow(c1.Z,2) +Math.Pow(c1.W,2)); doubley=Math.Sqrt(Math.Pow(c2.X,2) +Math.Pow(c2.Y,2) +Math.Pow(c2.Z,2) +Math.Pow(c2.W,2)); if(x>y) return1; elseif(x return-1; else return0; } } internalclassVectorComparer2: IComparer { publicintCompare(Vectorc1,Vectorc2) { if(c1==null||c2==null) thrownewArgumentNullException("Bothobjectsmustnotbenull"); if(c1.T>c2.T) return1; elseif(c1.T return-1; else return0; } } internalclassProgram { privatestaticvoidPrint(Vector[]vectors) { //foreach(Vectorvinvectors) //{ //Console.WriteLine(v.T); //} } privatestaticvoidMain(string[]args) { Vector[]vectors=GetVectors(); Console.WriteLine(string.Format("n={0}",vectors.Length)); Stopwatchwatch1=newStopwatch(); watch1.Start(); A(vectors); watch1.Stop(); Console.WriteLine("Asorttime: "+watch1.Elapsed); Print(vectors); vectors=GetVectors(); watch1.Reset(); watch1.Start(); B(vectors); watch1.Stop(); Console.WriteLine("Bsorttime: "+watch1.Elapsed); Print(vectors); vectors=GetVectors(); watch1.Reset(); watch1.Start(); C(vectors); watch1.Stop(); Console.WriteLine("Csorttime: "+watch1.Elapsed); Print(vectors); vectors=GetVectors(); watch1.Reset(); watch1.Start(); D(vectors); watch1.Stop(); Console.WriteLine("Dsorttime: "+watch1.Elapsed); Print(vectors); Console.ReadKey(); } privatestaticVector[]GetVectors() { intn=1<<21; Vector[]vectors=newVector[n]; Randomrandom=newRandom(); for(inti=0;i { vectors[i]=newVector(); vectors[i].X=random.NextDouble(); vectors[i].Y=random.NextDouble(); vectors[i].Z=random.NextDouble(); vectors[i].W=random.NextDouble(); } returnvectors; } privatestaticvoidA(Vector[]vectors) { Array.Sort(vectors,newVectorComparer()); } privatestaticvoidB(Vector[]vectors) { intn=vectors.Length; for(inti=0;i { Vectorc1=vectors[i]; c1.T=Math.Sqrt(Math.Pow(c1.X,2) +Math.Pow(c1.Y,2) +Math.Pow(c1.Z,2) +Math.Pow(c1.W,2)); } Array.Sort(vectors,newVectorComparer2()); } privatestaticvoidC(Vector[]vectors) { intn=vectors.Length; for(inti=0;i { Vectorc1=vectors[i]; c1.T=Math.Sqrt(c1.X*c1.X +c1.Y*c1.Y +c1.Z*c1.Z +c1.W*c1.W); } Array.Sort(vectors,newVectorComparer2()); } privatestaticvoidD(Vector[]vectors) { intn=vectors.Length; for(inti=0;i { Vectorc1=vectors[i]; c1.T=Math.Sqrt(c1.X*c1.X +c1.Y*c1.Y +c1.Z*c1.Z +c1.W*c1.W); } Sort.ParallelSort parallelSort.Sort(vectors,newVectorComparer2()); } } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 并行 排序 算法