- 1、本文档共188页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
单元IV 非数值并行算法MPI编程实现
第十三章 排序
第十四章 串匹配
第十五章 图论
第十六章 组合优化
第十七章 计算几何
这一单元主要介绍典型的非数值并行算法的MPI编程实现,包括排序(第十三章)、串匹配(第十四章)、图论(第十五章)、组合优化(第十六章)和计算几何(第十七章)等。
本单元的第十三章介绍并行排序算法及其MPI编程实现,包括枚举排序、快速排序和正则采样并行排序(PSRS)等;第十四章介绍并行串匹配算法及其MPI编程实现,包括并行KMP串匹配、并行随机串匹配和并行近似串匹配等;第十五章介绍图论并行算法及其MPI编程实现,包括使用矩阵乘求传递闭包、顶点倒塌法求连通分量、Dijkstra单源最短路径算法和Sollin最小生成树算法等;第十六章介绍组合优化算法及其MPI编程实现,包括八皇后问题、SAT问题、装箱问题、背包问题和TSP问题等;第十七章介绍计算机几何算法及其MPI编程实现,包括包含问题、相交问题和凸壳问题等。
为了压缩篇幅,第十三章只给出了PSRS算法的MPI源程序,第十四章只给出了KMP 串匹配并行算法的MPI源程序,第十五章只给出了连通分量并行算法的MPI源程序,第十六章只给出了八皇后问题并行算法的MPI源程序,其余者均放在随书的光盘中,也可从中国科学技术大学国家高性能计算中心(合肥)的网站下载。
第十三章 排序
排序是数据处理中经常使用的一种重要运算,如何进行排序,特别是如何进行高效的排序,是计算机应用中的重要课题。排序的对象一般是一组记录组成的文件,而记录则是由若干数据项组成,其中的一项可用来标志一个记录,称为关键字项,该数据项的值称为关键字。
所谓排序,就是要整理文件中的记录,使得它按关键字递增(或递减)的次序排列起来。若给定的文件含有n个记录{R1,R2,…,Rn},它们的关键字分别为{K1,K2,…,Kn},要把这n个记录重新排列成为{Ri1,Ri2,…,Rin},使得{Ki1≥Ki2≥…≥Kin}(或{Ki1≤Ki2≤…≤Kin})。
本章主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。
枚举排序
枚举排序及其串行算法
枚举排序(Enumeration Sort)是一种最简单的排序算法,通常也称为秩排序(Rank Sort)。该算法的具体思想是(假设按关键字递增排序),对每一个待排序的元素统计小于它的所有元素的个数,从而得到该元素最终处于序列中的位置。假定待排序的n个数存在a[1]…a[n]中。首先将a[1]与a[2]…a[n]比较,记录比其小的数的个数,令其为k,a[1]就被存入有序的数组b[1]…b[n]的b[k+1]位置上;然后将a[2]与a[1],a[3]…a[n]比较,记录比其小的数的个数,依此类推。这样的比较操作共n(n-1)次,所以串行秩排序的时间复杂度为O(n2)。
算法13.1 枚举排序串行算法
输入:a[1]…a[n]
输出:b[1]…b[n]
Begin
for i=1 to n do
(1) k=1
(2) for j=1 to n do
if a[i]a[j] then
k=k+1
end if
end for
(3) b[k]= a[i]
end for
End
枚举排序的并行算法
对该算法的并行化是很简单的,假设对一个长为n的输入序列使用n个处理器进行排序,只需是每个处理器负责完成对其中一个元素的定位,然后将所有的定位信息集中到主进程中,由主进程负责完成所有元素的最终排位。该并行算法描述如下:
算法13.2 枚举排序并行算法
输入:无序数组a[1]…a[n]
输出:有序数组b[1]…b[n]
Begin
(1) P0播送a[1]…a[n]给所有Pi
(2) for all Pi where 1≤i≤n para-do
(2.1) k=1
(2.2) for j = 1 to n do
if (a[i] a[j]) or (a[i] = a[j] and ij) then
k = k+1
end if
end for
(3) P0收集k并按序定位
End
在该并行算法中,使用了n个处理器,由于每个处理器定位一个元素,所以步骤⑵的时间复杂度为O(n);步骤⑶中主进程完成的数组元素重定位操作的时间复杂度为O(n),通信复杂度分别为O(n);同时⑴中的通信复杂度为O(n2);所以总的计算复杂度为O(n),总的通信复杂度为O(n2)。
MPI源程序请参见所附光盘。
快速排序
快速排序及其串行算法
快速排序(Quick Sort)是一种最基本的排序算法,它的基本思想是:在当前无序区R[1,n]中取一个记录作为比较的“基准”(一般取第一个、最后一个或中
您可能关注的文档
最近下载
- 备战2023年高考语文一轮复习考点微专题(新高考地区专用)考向28 诗歌鉴赏之语言(含详解).docx VIP
- 飞机交易平台及飞机拆解项目可行性研究报告.doc
- 视听语言PPT全套教学课件.pptx
- 健康评估-河南大学-中国大学MOOC慕课答案.pdf
- 初中音乐人音版《七年级上册青年友谊圆舞曲》课件_1.ppt
- 基于Java的小区物业管理系统的设计与实现.docx VIP
- 普通话课件(完整版)教学文案.ppt
- 【清风语文精品课件】2021高中语文《静女》优质课一等奖.pptx
- 某区南1#矿石泊位升级10万吨级散货泊位工程环境影响报告书.pdf
- 2024高中语文教师课程标准考试模拟试卷及参考答案.docx VIP
文档评论(0)