双核CPU的快速排序效率.doc

《双核CPU的快速排序效率.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、双核CPU上的快速排序效率 为了试验一下多核CPU上排序算法的效率，得比较单任务情况下和多任务并行排序算法的差距，因此选用快速排序算法来进行比较。测试环境：双核CPU2.66GHZ单核CPU2.4GHZ以下是一个快速排序算法的源代码：UINTSplit(void**ppData,UINTuStart,UINTuEnd,COMPAREFUNCCompareFunc){void*pSelData;UINTuLow;UINTuHigh;uLow=uStart;uHigh=uEnd;pSelData=ppData[uLow

2、];while(uLow0&&uLow!=uHigh){--uHigh;}if(uHigh!=uLow){ppData[uLow]=ppData[uHigh];++uLow;}while((*CompareFunc)(ppData[uLow],pSelData)<0&&uLow!=uHigh){++uLow;}if(uLow!=uHigh){ppData[uHigh]=ppData[uLow];--uHigh;

3、}}ppData[uLow]=pSelData;returnuLow;}voidQuickSort(void**ppData,UINTuStart,UINTuEnd,COMPAREFUNCCompareFunc){UINTuMid=Split(ppData,uStart,uEnd,CompareFunc);if(uMid>uStart){QuickSort(ppData,uStart,uMid-1,CompareFunc);}if(uEnd>uMid){QuickSort(ppData,uMid+1,uEnd,Co

4、mpareFunc);}}先测试一下这个快速排序算法排一百万个随机整数所花的时间：voidTest_QuickSort(void){UINTi;UINTuCount=1000000;//1000000个srand(time(NULL));void**pp=(void**)malloc(uCount*sizeof(void*));for(i=0;i

5、IntCompare);clock_tt2=clock();printf("QuickSort1000000Time%ld",t2-t1);free(pp);}在双核CPU2.66GHZ机器上运行测试程序，打印出花费的时间约为406ms在单核CPU2.4GHZ机器上运行测试程序，打印出花费时间约为484ms可见在双核CPU上运行单任务程序和单核CPU基本是一样的，效率没有任何提高。下面再来把上面的快速排序程序变成并行的，一个简单的方法就是将要排序的区间分成相同的几个段，然后对每个段进行快速排序，排序完后再使用归

6、并算法将排好的几个区间归并成一个排好序的表，我们先四个线程来进行排序，代码如下：void**Merge(void**ppData,UINTuStart,UINTuEnd,void**ppData2,UINTuStart2,UINTuEnd2,COMPAREFUNCcfunc){UINTi,j,k;UINTu1,u2,v1,v2;void**pp1;void**pp2;void**pp=(void**)malloc((uEnd-uStart+1+uEnd2-uStart2+1)*sizeof(void*));if(p

7、p==NULL){returnNULL;}if((*cfunc)(ppData2[uStart2],ppData[uStart])>0){u1=uStart;u2=uEnd;v1=uStart2;v2=uEnd2;pp1=ppData;pp2=ppData2;}else{u1=uStart2;u2=uEnd2;v1=uStart;v2=uEnd;pp1=ppData2;pp2=ppData;}k=0;pp[k]=pp1[u1];j=v1;for(i=u1+1;i<=u2;i++){while(j<=v2){if((

8、*cfunc)(pp2[j],pp1[i])<0){++k;pp[k]=pp2[j];j++;}else{break;}}++k;pp[k]=pp1[i];}if(j