并行排序算法.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.ParallelSortparallelSort=newSort.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;
publicIComparerComparer;
publicParallelEntity（Statusstatus,T[]array,IComparercomparer）
{
Status=status;
Array=array;
Comparer=comparer;
}
}
privatevoidThreadProc（ObjectstateInfo）
{
ParallelEntitype=stateInfoasParallelEntity;
lock（pe）
{
pe.Status=ParallelSort.Status.Running;
Array.Sort（pe.Array,pe.Comparer）;
pe.Status=ParallelSort.Status.Finish;
}
}
publicvoidSort（T[]array,IComparercomparer）
{
//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.Status.Finish）
{
break;
}
}
Thread.Sleep（0）;
}
}
//Mergesort
MergeSortmergeSort=newMergeSort（）;
Listsource=newList（processorCount）;
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,Listsource,IComparercomparer）
{
//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.ParallelSortparallelSort=newSort.ParallelSort（）;
parallelSort.Sort（vectors,newVectorComparer2（））;
}
}
}
升级会员 