并行排序算法

并行排序算法 先简洁说一下给的A，B，C 三种算法见上面引用的那篇博客，A算法将耗时的平方和开平方计算放到比较函数中，导致Array.Sort 时，每次亮亮比较都要执行平方和开平方计算，其平均算法困难度为 Onlog2n 。 而B 将平方和开平方计算提取出来，算法困难度降低到 On ，这也就是为什么B比A效率要高许多的原因。C 和 B 相比，将平方函数替换成了 x*x ，由于少了远程函数调用和Pow函数本身的开销，效率有提高了不少。我在C的基础上编写了D算法，D算法采纳并行计算技术，在我的双核笔记本电脑上数据量比较大的状况下，其排序效率较C要提高30左右。 下面重点介绍这个并行排序算法。算法思路其实很简洁，就是将要排序的数组根据处理器数量等分成若干段，然后用和处理器数量等同的线程并行对各个小段进行排序，排序结束和，再在单一线程中对这若干个已经排序的小段进行归并排序，最终输出完整的排序结果。考试大考虑到和.Net 2.0 兼容，没有用微软供应的并行库，而是用多线程来实现。 下面是测试结果 n A B C D 32768 0.7345 0.04122 0.0216 0.0254 65535 1.5464 0.08863 0.05139 0.05149 131072 3.2706 0.1858 0.118 0.108 262144 6.8423 0.4056 0.29586 0.21849 524288 15.0342 0.9689 0.7318 0.4906 1048576 31.6312 1.9978 1.4646 1.074 2097152 66.9134 4.1763 3.0828 2.3095 从测试结果上看，当要排序的数组长度较短时，并行排序的效率甚至还没有不进行并行排序高，这主要是多线程的开销造成的。当数组长度增大到25万以上时，并行排序的优势起先体现出来，随着数组长度的增长，排序时间最终基本稳定在但线程排序时间的 74 左右，其中并行排序的消耗也许在50左右，归并排序的消耗在 14左右。由此也可以推断，假如在4CPU的机器上，其排序时间最多可以削减到单线程的 14 25 39。8 CPU 为 14 12.5 26.5。 目前这个算法在归并算法上可能还有提高的余地，假如哪位高手能够进一步提高这个算法，不妨贴出来一起沟通沟通。 下面分别给出并行排序和归并排序的代码 并行排序类 ParallelSort Paralletsort 类是一个通用的泛型，调用起来特别简洁，下面给一个简洁的int型数组的排序示例 class IntComparer IComparer int { IComparer Members region IComparer Members public int Compare int x, int y { return x.CompareToy; } endregion } public void SortInt int [] array { Sort.ParallelSort int parallelSort new Sort.ParallelSort int ; parallelSort.Sortarray, new IntComparer; } 只要实现一个T类型两两比较的接口，然后调用ParallelSort 的 Sort 方法就可以了，是不是很简洁 下面是 ParallelSort类的代码 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; namespace Sort { /**/ /// /// ParallelSort /// /// public class ParallelSort T { enum Status { Idle 0 , Running 1 , Finish 2 , } class ParallelEntity { public Status Status; public T[] Array; public IComparer T Comparer; public ParallelEntityStatus status, T[] array, IComparer T comparer { Status status; Array array; Comparer comparer; } } private void ThreadProcObject stateInfo { ParallelEntity pe stateInfo as ParallelEntity; lock pe { pe.Status ParallelSort T .Status.Running; Array.Sortpe.Array, pe.Comparer; pe.Status ParallelSort T .Status.Finish; } } public void SortT[] array, IComparer T comparer { // Calculate process count int processorCount Environment.ProcessorCount; // If array.Length too short, do not use Parallel sort if processorCount 1 || array.Length processorCount { Array.Sortarray, comparer; return ; } // Split array ParallelEntity[] partArray new ParallelEntity[processorCount]; int remain array.Length; int partLen array.Length / processorCount; // Copy data to splited array for int i 0 ; i processorCount; i { if i