1 / 24
文档名称:

并行排序算法.doc

格式:doc   大小:53KB   页数:24页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

并行排序算法.doc

上传人:aihuichuanran1314 2019/6/1 文件大小:53 KB

下载得到文件列表

并行排序算法.doc

文档介绍

文档介绍:并行排序算法先简单说一下给的A,B,C三种算法(见上面引用的那篇博客),A算法将耗时的平方和开平方计算放到比较函数中,,每次亮亮比较都要执行平方和开平方计算,其平均算法复杂度为O(nlog2n)。而B将平方和开平方计算提取出来,算法复杂度降低到O(n),这也就是为什么B比A效率要高很多的缘故。C和B相比,将平方函数替换成了x*x,由于少了远程函数调用和Pow函数本身的开销,效率有提高了不少。我在C的基础上编写了D算法,D算法采用并行计算技术,在我的双核笔记本电脑上数据量比较大的情况下,其排序效率较C要提高30%左右。下面重点介绍这个并行排序算法。算法思路其实很简单,就是将要排序的数组按照处理器数量等分成若干段,然后用和处理器数量等同的线程并行对各个小段进行排序,排序结束和,再在单一线程中对这若干个已经排序的小段进行归并排序,最后输出完整的排序结果。,没有用微软提供的并行库,而是用多线程来实现。下面是测试结果: nABCD 从测试结果上看,当要排序的数组长度较短时,并行排序的效率甚至还没有不进行并行排序高,这主要是多线程的开销造成的。当数组长度增大到25万以上时,并行排序的优势开始体现出来,随着数组长度的增长,排序时间最后基本稳定在但线程排序时间的74%左右,其中并行排序的消耗大概在50%左右,归并排序的消耗在14%左右。由此也可以推断,如果在4CPU的机器上,其排序时间最多可以减少到单线程的14+25=39%。8CPU为14+=%。目前这个算法在归并算法上可能还有提高的余地,如果哪位高手能够进一步提高这个算法,不妨贴出来一起交流交流。下面分别给出并行排序和归并排序的代码: 并行排序类ParallelSort Paralletsort类是一个通用的泛型,调用起来非常简单,下面给一个简单的int型数组的排序示例: parer:IComparer<int> { IComparerMembers#parerMembers pare(intx,inty) { pareTo(y); } #endregion } publicvoidSortInt(int[]array) { <int>parallelSort=<int>(); (array,parer()); }只要实现一个T类型两两比较的接口,然后调用ParallelSort的Sort方法就可以了,是不是很简单? 下面是ParallelSort类的代码 usingSystem; ; ; ; ; namespaceSort { /**//// ///ParallelSort /// /// lassParallelSort<T> { enumStatus { Idle=0, Running=1, Finish=2, } classParallelEntity { publicStatusStatus; publicT[]Array; parer<parer; publicParallelEntity(Statusstatus,T[]array,IComparer<parer) { Status=status; Array=array; parer; } } privatevoidThreadProc(ObjectstateInfo) { ParallelEntitype=stateInfoasParallelEntity; lock(pe) { =ParallelSort<T>.; (,parer); =ParallelSort<T>.; } } publicvoidSort(T[]array,IComparer<parer) { //Calculateprocesscount intprocessorC

最近更新

标准合同范本:民间借贷合同(律师整理) 6页

2025年巨人的花园反思范文 4页

EBC经编织物的工艺设计和编织 2页

DKP系列整流控制设备的存在问题分析及改进措施.. 2页

2025年工程年度的工作总结报告 18页

韩国著名旅游景点和文化习俗介绍英文版 16页

CD100A型煮茧机的研制和应用 2页

极限运动大赛冠名赞助合同模板 7页

BCH-32稠油破乳剂的研制与应用 2页

2025年工作实习自我鉴定社会实践 11页

2025年工作三个月个人工作总结 30页

2025年工人辞职报告 24页

2025年山西财经大学排名第几多少位全国2025 3页

6kV高压电机软启动系统的设计与研究 2页

污泥运输及处置合同 9页

未办理正式手续的劳动合同,合同效力如何认定.. 6页

50kta硫酸装置电加热炉改造技术总结 2页

电力牵引供变电技术第一章及第三章 61页

服装服饰物流服务 9页

旅游业务居间代理批文 9页

第8课《外国诗两首》教案(语文版初三下)1doc初.. 3页

建筑模板长途运输合同模板 9页

25%稻瘟净-杀螟松油混合剂的薄层分析 2页

20项化工标准荣获1992年科学技术进步奖 2页

浅谈企业激励员工中存在的问题及对策 4页

正常猫的外周血象观察 3页

最新管理人员年度考核方案 4页

新能源技术的发展与应用高中作文5 5页

数据库在环境保护和可持续发展中的应用 8页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页