计算思维导论第8讲-算法与计算环境

第8讲-算法与计算环境哈尔滨工业大学计算学部教学委员会主任国家教学名师战德臣第8讲-算法与计算环境一、为什么要研究排序算法

二、基本排序算法-内排序

三、算法与计算环境--外排序与多路归并四、从表连接为例看算法与计算环境【拓展】一、网页排序Rank思想与算法对一组对象按照某种规则进行有序排列。通常是把一组对象整理成按关键字递增(或递减)的排列，关键字是指对象的一个用于排序的特性。例如：对一组“人”，按“年龄”或“身高”排序；

对一组“商品”，按“价格”排序；

对一组“网页”，按“重要度”排序；

对一组“词汇”，按“首字母”字典序排序。……为什么要研究排序算法什么是排序问题

结构化数据表的查找问题【算法A：未排序数据查找算法】StartofalgorithmStep1.从第1条记录开始，直到最后一条记录为止，读取每一条记录，做Step2。Step2.对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。Endofalgorithm学号姓名成绩120300101李鹏88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73查找成绩为80分的所有同学?算法效率：读取并处理所有记录，即n条记录数据表记录数:n未排序从结构化数据表查找看排序问题为什么要研究排序算法

O(n)结构化数据表的查找与统计需要排序【算法B：已排序数据查找算法】StartofalgorithmStep1.从第1条记录开始，直到最后一条记录为止，读取每一条记录，做Step2和Step3步。Step2.对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。Step3.判断该条记录的成绩是否小于给定的分数：如果不是，则继续循环；否则，退出循环，算法结束。Endofalgorithm学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44查找成绩为80分的所有同学?算法效率：读取并处理部分记录，即<=n条记录数据表记录数:n已排序从结构化数据表查找看排序问题为什么要研究排序算法

O(n)结构化数据表的查找与统计需要排序学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44查找成绩为80分的所有同学?数据表记录数:n【算法C：已排序数据查找算法】StartofalgorithmStep1.假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n；Step2.计算中间记录位置I=(Start+Finish)/2，读取第I条记录。Step3.判断第I条记录成绩是否大于给定查找分数：(1)如果是小于，调整Finish=I-1,如果Start>Finish则结束，否则继续做Step2；(2)如果是大于，调整Start=I+1，如果Start>Finish则结束，否则继续做Step2；(3)如果是等于，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。Endofalgorithm算法效率：除极端情况外读取并处理<=n/2条记录已排序从结构化数据表查找看排序问题为什么要研究排序算法

O(log2n)结构化数据表的查找与统计需要排序学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44学号姓名成绩120300101李鹏88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73统计各个分数段的人数统计每个同学的平均分数统计每门课的平均分数???算法效率：需要读取并处理???条记录才能完成呢？从结构化数据表查找看排序问题为什么要研究排序算法

结构化数据表的查找与统计需要排序学号姓名成绩120300107闫宁95120300103李宁94120300101李鹏88120300106徐月85120300102王刚79120300109江海77120300110周峰73120300104赵凯69120300105张伟66120300108杜岩44学号姓名成绩120300101李鹏88120300105张伟66120300107闫宁95120300102王刚79120300103李宁94120300106徐月85120300108杜岩44120300104赵凯69120300109江海77120300110周峰73统计各个分数段的人数统计每个同学的平均分数统计每门课的平均分数???算法效率：需要读取并处理???条记录才能完成呢？排序算法是计算学科中很重要的算法排序算法是很多复杂算法的基础当对数据集合需要多遍处理时，先排序-好从结构化数据表查找看排序问题为什么要研究排序算法测练题：你是怎样理解算法的时间复杂性的，你的选择是_____。算法的时间复杂性，是关于算法执行时间位于哪一个量级的表述算法的时间复杂性，是关于问题规模增大时算法执行时间增长趋势的一种表述算法的时间复杂性，是关于算法步骤执行次数的精准表述算法的时间复杂性，是关于算法执行的绝对时间的表述ABCD提交多选题1分怎样按照关键词找到相应的文档呢?关键词查询包含<关键词>的文档是哪一个?有多少个?怎样找?怎样快速地找?为什么要研究排序算法

从非结构化数据(文档)的查找看排序问题

怎样按照关键词找到相应的文档呢?对所有文档建立关键词查询查找文档关键词索引表倒排索引正排：一个文档包含了哪些词汇?#Doc1,{Word1,Word2,…}倒排：一个词汇包含在哪些文档中

Word1,{#Doc1,#Doc2,…}怎样建立索引?怎样利用索引快速地找?排序or不排序?从非结构化数据(文档)的查找看排序问题--索引与倒排索引为什么要研究排序算法关键词索引表--倒排索引文档能否自动找出文档中的关键词?哪些是关键词?排序or不排序?从非结构化数据(文档)的查找看排序问题--关键词的提取

为什么要研究排序算法

非结构化数据文档的查找与搜索也需要排序怎样按照关键词找到相应的文档呢?对所有文档建立关键词查询查找文档关键词索引表--倒排索引文档怎样快速找到关键词呢?哪些是关键词呢?从非结构化数据(文档)的查找看排序问题--小结

为什么要研究排序算法非结构化数据文档的查找与搜索也需要排序怎样按照关键词找到相应的文档呢?对所有文档建立关键词查询查找文档关键词索引表--倒排索引文档怎样快速找到关键词呢?哪些是关键词呢?从非结构化数据(文档)的查找看排序--小结

为什么要研究排序算法排序：字母序排序：数值序查找：反复进行不同类别的查找，不同类别的排序测练题：从非结构化数据查找问题中，你看出了哪些地方需要用到排序算法_____。自动确定文档关键词时，需要按词汇在文档中出现的频率排序形成关键词时，需要按词频（数值）排序；关键词匹配时，需要按字母序排序建立倒排索引时，需要对索引项（词汇）排序用关键词匹配文档中的所有词汇，最好能对文档按词汇排序ABCD提交没有看出在哪里需要排序E投票最多可选5项第8讲-算法与计算环境一、为什么要研究排序算法

二、基本排序算法-内排序

三、算法与计算环境--外排序与多路归并四、从表连接为例看算法与计算环境【拓展】一、网页排序Rank思想与算法类似于打扑克牌时，一边抓牌，一边理牌的过程：每抓一张牌就把它插入到适当的位置；牌抓完了，也理完了。这种策略被称为插入排序基本排序算法-内排序（1）插入排序法-基本思想?1274978193366505180i=2i=3i=4i=512345678910Ai=57124978193366505180A7124978193366505180A7124978193366505180A7121949783366505180A7121933495051667880Ai=9…i=57124978783366505180Ai=57124949783366505180A插入排序:递增排序示意.其中三角形左侧为已排好序的元素,其右侧为未排序的元素,实心三角形本身为待插入的元素.图中示意了为待排序元素19腾挪空间的过程,由箭头示意.空心三角形表示新插入的元素基本排序算法-内排序（1）插入排序法-过程模拟?INSERTION-SORT(A)1.fori=2toN2.{key=A[i];3. j=i-1;4. While(j>0andA[j]>key)do5. {A[j+1]=A[j];6. j=j-1;}7. A[j+1]=key;8.} O(N2)

基本排序算法-内排序（1）插入排序法-算法表达首先在所有数组元素中找出最小值的元素，放在A[1]中；接着在不包含A[1]的余下数组元素中再找出最小值元素，放置在A[2]中；如此下去，一直到最后一个元素。这一排序策略被称为简单选择法排序。基本排序算法-内排序（2）简单选择法排序-基本思想?12

749

78193366505180i=1i=3i=412345678910A71249

78193366505180A71219

78493366505180A7121933495051667880Ai=9…i=471219

78493366505180Ai=471219

33497866505180A(b)选择排序:递增排序示意.其中三角形代表本轮要找的最小元素应在的位置,方形代表本轮次至今为止所找到的最小元素所在位置,三角形左侧为已排好序的元素,三角形右侧的每一元素依次和方形位置元素比较.实线双向箭头代表两个元素交换.虚线双向箭头代表两个元素需要比较基本排序算法-内排序（2）简单选择法排序-过程模拟?SELECTION-SORT(A)1.fori=1toN-12.{ k=i;3．

forj=i+1toN4. {ifA[j]<A[k]thenk=j;}5. ifk<>ithen6. {7. temp=A[k];8. A[k]=A[i];9. A[i]=temp;10. }11.} O(N2)

基本排序算法-内排序（2）简单选择法排序-算法表达?一个轮次一个轮次的处理。在每一轮次中依次对待排序数组元素中相邻的两个元素进行比较，将大的放前，小的放后--递减排序(或者是将小的放前，大的放后--递增排序)。当没有交换时，则数据已被排好序。基本排序算法-内排序（3）冒泡排序法-基本思想?12

7

49

78

1933665051

80i=112

497

78

1933665051

80j=1i=1j=212

49787

1933665051

80i=1j=3…12

497819336650517

80i=1j=9i=9j=180

7866515049331912

712345678910AAAAA…12

4978193366505180

7i=2j=1Ai=8j=178

8066515049331912

7A(c)冒泡排序:递减排序示意，其中小圆点代表本轮本次比较的两个元素,双向弧线箭头代表两个元素要相互交换12

7

49

78

1933665051

80Ai=1j=4基本排序算法-内排序（3）冒泡排序法-过程模拟?BUBBLE-SORT(A)1.fori=1toN-12.{haschange=false;3. forj=1toN-i4. {ifA[j]>A[j+1]then5. {temp=A[j];6. A[j]=A[j+1];7. A[j+1]=temp;8. haschange=true;9. }10. }11.if(haschange==false)thenbreak;12.} O(N2)

基本排序算法-内排序（3）冒泡排序法-算法表达?测练题：关于选择排序、插入排序和冒泡排序，下列说法正确的是___________。三种排序算法的时间复杂度是不同的，因此三种算法的执行时间也是不一样的三种排序算法按执行时间长短排序：(1)选择排序(2)插入排序(3)冒泡排序。越排前越快。三种排序算法的时间复杂度是相同的，但三种算法的执行时间是不一样的三种排序算法的时间复杂度是相同的，因此三种算法的执行时间是一样的ABCD提交三种排序算法好坏，主要看【交换】的次数，交换次数越多越慢、E多选题1分第8讲-算法与计算环境一、为什么要研究排序算法

二、基本排序算法-内排序

三、算法与计算环境--外排序与多路归并四、从表连接为例看算法与计算环境【拓展】一、网页排序Rank思想与算法内排序问题:待排序的数据可一次性地装入内存中，即排序者可以完整地看到和操纵所有数据，使用数组或其他数据结构便可进行统一的排序处理的排序问题；外排序问题:待排序的数据保存在磁盘上，不能一次性装入内存，即排序者不能一次完整地看到和操纵所有数据，需要将数据分批装入内存分批处理的排序问题；问题类比：某教师要对学生按身高排序。教师只能在房间(相当于内存)中对学生进行排序，假设房间仅能容纳100人，那么对于小于100人的学生排序便属于内排序问题。而对于大于100人，如1000人的学生排序，学生并不能都进入房间，而只能在操场(相当于磁盘)等候，轮流进入房间，这样的排序便属于外排序问题。算法与计算环境--外排序与多路归并排序问题的复杂性在哪里

内存:2GB待排序数据:7GB,10GB,100GB?--大数据集合这种需要使用硬盘等外部存储进行大数据集合排序的算法称为外排序算法与计算环境--外排序与多路归并外排序环境与问题示例外排序算法的环境/资源(仅介绍思想,忽略一些细节),假设:读写磁盘块函数:ReadBlock,WriteBlock内存大小:共Bmemory=6块,每块可装载Rblock=5个元素待排序数据:Rproblem=60个元素,共占用Bproblem=12块问题:Bproblem块的数据怎样利用Bmemory块的内存进行排序?算法与计算环境--外排序与多路归并外排序环境与问题示例基本排序策略

Bproblem块数据可划分为N个子集合,使每个子集合的块数小于等于内存可用块数，即：Bproblem/N

<=Bmemory。每个子集合都可装入内存并采用内排序算法排好序并重新写回磁盘。问题转化为:N个已排序子集合的数据怎样利用内存进行总排序?Bmemory=6块,Rblock=5个元素Rproblem=60个元素

Bproblem=12块算法与计算环境--外排序与多路归并外排序的基本处理策略?子集合已排好序，如何进行总排序内存不能装下所有子集合算法与计算环境--外排序与多路归并外排序问题

磁盘内存Bmemory=6第1块第2块第3块第4块第5块第6块子集合存储在磁盘上的若干块算法与计算环境--外排序与多路归并内存资源的使用分配

N个子集合各自依次序读取一块装入内存内存中的N块(对应N个子集合)各自依次序读取一个元素形成一个待比较集合将待比较集合中的最小元素取出写入输出块中输出块依序写回磁盘上算法与计算环境--外排序与多路归并基本归并动作

908682807555453530278078726252727068646270605843322420181009504238343160454238352815110805080806040329191613102520150908050310080504100805061008080610080808100803030403040503040506030405060803040506080808100908081009080910091109100908080808080808080809内存磁盘2815110805080806040329191613102520150908写磁盘读磁盘

24201810092420181009算法与计算环境--外排序与多路归并过程模拟-1过程模拟小结

算法与计算环境--外排序与多路归并算法的效率：读写磁盘块的次数，即I/O数=4Bproblem

子集合排序阶段读一遍写一遍2Bproblem归并阶段读一遍写一遍2Bproblem算法与计算环境--外排序与多路归并

算法的复杂性问题

大数据集块数>=Bmemory2如何排序呢？算法的应用条件：子集合数<Bmemory子集合的块数<=Bmemory

即大数据集块数<Bmemory2

算法在任何情况下都可以应用吗

算法与计算环境--外排序与多路归并内存大小:共Bmemory=3块待排序数据:

共占用Bproblem=30块基本策略:30块的数据集

10个子集合，每个子集合3块，排序并存储。10个已排序子集合分成5个组：每个组2个子集合,分别进行二路归并，则可得到5个排好序的集合；5个集合再分成3个组：每个组2个子集，剩余一个单独1组，分别进行二路归并，可得3个排好序的集合；再分组，再归并得到2个排好序的集合；再归并便可完成最终的排序。

当更大规模的数据需要排序时怎么办?算法与计算环境--外排序与多路归并假如内存共有8块，问其如何排序有70块的数据集呢？你是采用二路归并、三路归并、…、七路归并？你设计的具体算法，磁盘读写次数是多少呢？磁盘读写次数最少的应是几路归并？

思考一下下列情况排序，应该怎么办

算法与计算环境--外排序与多路归并测练题：假如内存共有8块，其能一次性完成内排序的数据集最大是几块？8块ABCD提交7块6块多少块都可以单选题1分测练题：假如内存共有8块，问其如何排序有70块的数据集呢？你是采用二路归并、三路归并、…、七路归并？磁盘读写次数最少的应是几路归并？（1）首先划分为9个数据集，每个数据集8块，将子数据集装入内存，做内排序，然后写回磁盘。（2）再做一个五路归并。(3)最后做一个五路归并。这样磁盘读写次数最少ABCD提交（1）首先划分为10个数据集，每个数据集7块，将子数据集装入内存，做内排序，然后写回磁盘。（2）再做一个六路归并。(3)最后做一个五路归并。这样磁盘读写次数最少（1）首先划分为9个数据集，每个数据集8块，将子数据集装入内存，做内排序，然后写回磁盘。（2）再做一个三路归并。(3)最后做一个七路归并。这样磁盘读写次数最少（1）首先划分为9个数据集，每个数据集8块，将子数据集装入内存，做内排序，然后写回磁盘。（2）再做一个七路归并。(3)最后做一个三路归并。这样磁盘读写次数最少单选题1分第8讲-算法与计算环境一、为什么要研究排序算法

二、基本排序算法-内排序

三、算法与计算环境--外排序与多路归并四、从表连接为例看算法与计算环境【拓展】一、网页排序Rank思想与算法表连接操作的逻辑实现算法【P0】Fori=1toTR

geti-th

recordofR；

Forj=1toTS

getj-th

recordofS；

ifR.AS.Bthen {串接i-th

recordofR和j-th

recordofS； 存入结果表中；} NextjNexti

R.A

S.BRSTR：表R的行/记录数目；

TS：表S的行/记录数目；这只是逻辑算法,物理上复杂得多！从表连接为例看算法与计算环境什么是表连接表连接：将表R中A属性值与表S中B属性值满足条件的任何两行连接起来数据库与数据处理领域频繁使用的一种运算表数据在计算环境中的存储b：每个磁盘块的字节数

TR：表R的行/记录数目

IR：表R的每行的字节数

一个磁盘块能存储的表R的行数b/IR

BR：表R所占用的磁盘块数目=TR*IR/b

M：主存缓冲区的页数(主存每页容量等于一个磁盘块的容量)

物理实现算法需要考虑表中数据是存储在磁盘上的。磁盘是以磁盘块为操作单位。首先要被装载进内存(I/O操作)，然后再进行记录/行的处理。从表连接为例看算法与计算环境R.A

S.BRS外存-内存-CPU计算环境P1：一块一块装入内存，一条记录一条记录处理表连接操作的基本实现算法【P1】Fori=1toBR

readi-thblockofR；

Forj=1toBS

readj-thblockofS；

Forp=1tob/IR

getp-threcordofR；

Forq=1tob/IS

getq-threcordofS；

ifR.AS.Bthen{串接p-threcordofR和q-threcordofS;

存入结果表中;}NextqNextp NextjNexti

应用条件：仅需要三个内存页即可应用，一页装入R，一页装入S，一页输出。算法复杂性：I/O次数估计为BR+BR

BS(暂忽略保存结果表的I/O次数)磁盘I/O操作内存操作从表连接为例看算法与计算环境R.A

S.BRS外存-内存-CPU计算环境P2：两个关系一次性装入内存，然后一条记录一条记录处理表连接操作的全主存实现算法【P2】Fori=1toBR//注：有可能一次性读入连续的多块

readi-thblockofR；Nexti

Forj=1toBS

//注：有可能一次性读入连续的多块

readj-thblockofS；NextjForp=1toTR

getp-threcordofR；

Forq=1toTS

getq-threcordofS；

ifR.AS.Bthen{串接p-threcordofR和q-threcordofS;

存入结果表中；}NextqNextp 应用条件：M>=BR+BS。算法复杂性：I/O次数估计为BR+BS(暂忽略保存结果表的I/O次数)降低I/O操作次数是关键充分利用内存内存如能装下两个表从表连接为例看算法与计算环境R.A

S.BRS外存-内存-CPU计算环境P3：一个表全装入内存，另一个表一块一块处理表连接操作的半主存实现算法【P3】Fori=1toBR

//注：有可能一次性读入连续的多块

readi-thblockofR；Nexti

Forj=1toBS

//注：一次读入一块

readj-thblockofS；

Forp=1toTR

getp-threcordofR；

Forq=1tob/IS

getq-threcordofS；

ifR.AS.Bthen{串接p-threcordofR和q-threcordofS；存入结果表中；}NextqNextpNextj应用条件：BS

>=BR，BR<M

算法复杂性：I/O次数估计为BR+BS(暂忽略保存结果表的I/O次数)充分利用内存内存仅能装下一个表从表连接为例看算法与计算环境R.A

S.BRS外存-内存-CPU计算环境P4:一块输出，一块存一个表，其余尽可能存另一个表表连接操作的大关系实现算法【P4】把表S划分为BS/(M-2)个子集合，每个子集合具有M-2块。令MS为M-2块容量存S，MR为1块容量存R，还有1块作为输出结果

Fori=1toBS/(M-2)//注：一次读入M-2块

readi-thSub-setofSintoMS；

Forj=1toBR

//注：一次读入一块

readj-thblockofRintoMR；

Forp=1to(M-2)b/IS

getp-threcordofS；

Forq=1tob/IR

getq-threcordofR；

ifR.AS.Bthen{串接p-threcordofSandq-threcordofR； 存入结果表中；}NextqNextpNextjNexti

应用条件：BS

>=M，BR>=M。算法复杂性：I/O次数估计为BR(BS/(M-2))+BS(暂忽略保存结果表的I/O次数)充分利用内存两个表都不能完全装入内存从表连接为例看算法与计算环境R.A

S.BRS外存-内存-CPU计算环境由单机计算环境到并行分布计算环境从表连接为例看算法与计算环境作业的第1部分作业的第2部分作业的第3部分作业的拆分与合并CPU1CPU2CPU3CPU4作业作业的拆分与合并CPUCPUCPUCPU作业作业的第1部分作业的第2部分作业的第3部分ComputerNetwork或Internet网络传输网络传输网络传输网络传输R.A

S.BRS外存-内存-CPU计算环境多核并行计算环境多机分布计算环境基于散列的R和S的连接算法（思想）

散列：有M个桶，一个桶相当于一个磁盘块。散列函数h(k)将键值k映射到{0,1,…,m-1}，则具有键值k的记录将被存储在对应h(k)的桶中。

以连接属性Y作键值，设计散列函数。

第一趟：使用相同散列函数散列两个操作对象R和S，形成R1,…,RM和S1,…,SM，

第二趟：将Si再整体散列读入到内存中，再依次处理Ri的每一块。进行连接。从表连接为例看算法与计算环境内存磁盘磁盘原始表输出2输入1散列计算hpM子表12M...R和S的子表Ri输入Si(<=M块)的散列数据内存磁盘输出磁盘结果关系散列计算hrhrh(k)例如

k

modMk主桶溢出桶10M-1RSite1RSite2RSite3FinalSiteInputSplittingMappingShufflingReducingFinalresult从表连接为例看算法与计算环境一种多机并行执行的表连接算法（思想）MSite1MSite2按B属性散列，将B属性值相同的散列到一起，由同一机器处理按R中B属性值和S中B属性值相同的汇聚到同一台机器形成最终连接结果散列散列排序连接第8讲【拓展】算法与计算环境哈尔滨工业大学计算学部教学委员会主任国家教学名师战德dechen@第8讲【拓展】算法与计算环境一、网页排序Rank思想与算法4,540,000条检索记录1,210,000条检索记录怎样把最重要的检索记录显示给用户?网页排序Rank思想与算法网页排序问题：搜索引擎?<标记>文本</标记><AHREF=“/realcorp/products.html”>OurProductInform