📄 chapter1_1.htm
字号:
<html>
<!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>算法与数据结构 -- 表排序</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
previous = "chapter1.htm";
next = "chapter1_2.htm";
contents="";
topic="并行算法——指针转移";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" -->
<h3>1.1 表排序</h3>
<p>我们介绍的第一个并行算法是有关列表的。列表在PRAM中的存储方式与普通的 RAM相同。为了便于并行地对列表中的对象进行操作，我们为每个对象分配一个“响应”处理器。假定处理器数目与列表中的对象一样多，并且第i个处理器负责处理第i个对象。例如，图2(a)说明了一个由对象序列<3,4,6,1,0,5>组成的链表。由于每个对象对应于一个处理器，所以表中的每个对象都可由其响应处理器在O(1)的时间内对其进行操作。</p>
<p align="center"><img border="0" src="images/fig2a.gif" width="572" height="49"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/fig2b.gif" width="572" height="87"></p>
<p align="center">(b)</p>
<p align="center"><img border="0" src="images/fig2c.gif" width="572" height="89"></p>
<p align="center">(c)</p>
<p align="center"><img border="0" src="images/fig2d.gif" width="572" height="49"></p>
<p align="center">(d)</p>
<p align="center">图2 运用指针转移在O(lgn)时间内求出n个对象组成的链表中每个对象到表尾的距离</p>
<p>假定已知一个包含n个对象的单链表L，我们希望计算出表L中的每个对象到表尾的距离。更形式地说，如果next是指针域，我们希望计算出表中每个对象i的值d[i]，使得：</p>
<blockquote>
<p><img border="0" src="images/Eqn1.gif" width="270" height="49"></p>
</blockquote>
<p>我们把这一计算d值的问题称为表排序问题。</p>
<p>解决表排序问题的一种方法是从表尾把距离往回传输。因为表中从末端开始的第k个对象必须等到其后的k-1个对象确定了它们到表尾的距离后才能确定其自身到表尾的距离，所以这一方法需要O(n)的运行时间。实际上，这一解决方法是一种串行算法。</p>
<p>下面的代码给出了一种有效的并行算法，其运行时间仅为O(lgn)。<a name="ListRank"></a></p>
<pre><code class="pseudocode">List-Rank(L)
1. for 每个处理器i，并行地执行
2. do if next[i]=NIL
3. then d[i]←0
4. else d[i]←1;
5. while 存在一个对象i，满足next[i]≠NIL
6. do for 每个处理器i，并行地执行
7. do if next[i]≠NIL
8. then d[i]←d[i]+d[next[i]];
9. next[i]←next[next[i]];</code></pre>
<p>图2说明了算法是如何计算出各个距离值的。图中的每个部分说明了执行第5-9行的while循环的迭代操作以前列表的状态。在第一次迭代中，表中开头5个对象的指针不为NIL，所以由其响应处理器分别执行第8-9行的操作。其操作结果见图中的(b)部分。在第二次迭代中，只有前面4个对象的指针不是NIL，该次迭代后的结果见图中的(c)部分，在第3次迭代中，只对表中开头2个对象进行操作，最后所有对象的指针均变为NIL，其结果见图中的(d)部分。</p>
<p>在第9行中，对所有非NIL指针next[i]，我们置next[i]← next[next[i]]，它实现的设计思想称为指针转移。注意，由于指针转移操作改变了指针域，因而也就破坏了链表的结构。如果必须保持链表结构，则我们可以对next指针做备份并使用该备份来计算距离的值。</p>
<p class = "noindent"><b>正确性</b></p>
<p>List-Rank维持以下不变条件：在第5-9行while循环中每次迭代开始时，对每个对象i，如果对以i作表头的子表的各个d值求和，就得到了从i到初始表L尾的正确距离。例如，在图2(b)中，对象3作表头的子表是序列<3,6,0>，其d值分别为2,2,和1，它们的和为5，这就是该对象到初始表尾的距离。上述不变条件成立的原因是当每个对象与其在表中的后继进行“拼接”时，它把其后继的d值加到自身的d值中。</p>
<p>必须注意，为使指针转移算法能正确执行，必须使并行的存储器存取保持同步。每次执行第9行代码可以对数个next指针进行更新。我们要求赋值式右边的存储器读操作（读
next[next[i]]）出现在赋值式左边的任何存储器写操作（写next[i]）之前。</p>
<p>现在让我们看看List-Rank是一个EREW算法的原因。因为每个处理器至多响应一个对象，所以第2-7行的每个读操作和写操作都是互斥的，第8-9行的写操作也是如此。请注意指针转移维持下列不变条件：对任意两个不同的对象i和j，或者有next[i]≠next[j]，或者有next[i]=next[j]=NIL。对初始表这一条件显然成立，并且通过第9行操作该条件一直保持成立。因为所有非NIL的next值都是不同的，所以第9行中的读操作也是互斤的。</p>
<p>如果所有读操作都是互斥的，我们就无需假设在第8行中执行了某种同步操作。特定地，我们要求所有处理i只能先读d[i]，然后才能读d[next[i]]。有了这种同步要求，如果一个对象i有next[i]≠NIL，并且有另外一个对象j指向i（即next[j]=i），则第1个读操作为处理器i取得值d[i]，然后第
2个读操作才能为处理器j取得值d[i]。因此，所以 List-Rank是一种EREW算法。</p>
<p>从现在起，我们忽略有关同步的细节描述并假定PRAM与其伪代码设计环境都以始终如一的同步方式进行操作，所有处理器可同时执行读操作与写操作。</p>
<p class = "noindent"><b>分析</b></p>
<p>我们现在来证明如果表L中有n个对象，则List-Rank的运行时间为O(lgn)。因为初始化占用的时间为O(1)，并且while循环中的每次迭代所需时间也是O(1)，所以只需证明总共有
「lgn」次迭代操作就可以了。我们注意到关键是：指针转移的每一步把每个表转化为交错的两个表：一个表由偶数位置上的对象构成，另一个表由奇数位置上的对象构成。因此每个指针转移步使表的数目增加一倍而使其长度减为一半。因此，在「lgn」次迭代结束时，所有的表均包含一个对象。</p>
<p>第5行中的终止条件测试所需时间为O(1)。事实上，只要在循环体内用一个变量记录next[i]≠NIL的i的个数，就可以在O(1)的时间内完成第5行的测试。</p>
<p>除了并行的运行时间外，对于并行算法还存在另一种有趣的性能评价方法。我们定义并行算法执行的<dfn>工作</dfn>为其运行时间与所需的处理器数目的积。从直观上看，工作是一个串行RAM模拟并行算法时所执行的计算量。</p>
<p>过程List-Rank执行了O(nlgn)的工作，这是因为它需要n个处理器且其运行时间为O(lgn)。关于表排序问题的简单的串行算法的运行时间为O(n)，这说明List-Rank执行的某些工作并不是必需的，但两者仅差一个对数因子。</p>
<p>已知一个PRAM算法A和求解同一个问题的另一种(串行或并行)算法B，如果A执行的工作不超过B执行的工作乘以一个常数因子，我们就说算法A对于算法B来说高效。如果算法A对于串行RAM上最好的算法来说是高效的，我们就更简单地称PRAM算法A高效。因为在串行RAM上关于表排序的最好算法的运行时间为O(n)，所以List-Rank不是高效的算法。我们将在第4节中阐述一个关于表排序的高效的并行算法。</p>
<!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -