Batcher归并网络

✍ dations ◷ 2025-09-18 19:31:36 #并发计算

Batcher排序网络是由一系列Batcher比较器(Batcher's Comparator)组成的。Batcher比较器是指在两个输入端给定输入x,y,再在两个输出端输出最大值max{x,y}和最小值min{x,y}。

比较器网络是用Batcher比较器连成的完成某一功能的网络。

所谓双调序列(Bitonic Sequence)是指由一个非严格增序列X和非严格减序列Y(其中X的最小元素正好是Y的最大元素)构成的序列,比如序列(23,10,8,3,5,7,11,78)。

定义:一个序列a1,a2,…,an是双调序列(Bitonic Sequence),如果:

输入两个已排好序的序列,对这两个序列进行归并排序,在串行算法中的时间复杂度为O(n)。在并行计算中可以用奇偶归并算法来实现的。以输入的两个4元素有序序列为A和B为例,首先将这两个序列进行逆洗牌(Unshuffle)得到两个序列:其中一个是由A,B中奇数号元素组成的序列,记作奇序列OM,另一个则是由A,B中偶数号元素组成的序列,记作偶序列序列EM。接着将OM送入(2,2)奇归并器中,将EM送入(2,2)偶归并器中。于是得到一组有序的奇序列和一组有序偶序列。最后除了奇序列一个元素之外将这两个序列进行洗牌(Shuffle)比较操作即可得到一个有序序列。

算法的递归性:一个n阶的归并器是由两个n/2阶的归并器加一个洗牌比较网络构成的。比如上面的两个(2,2)归并器和最后的洗牌比较网络就构成了一个(4,4)的归并器。

一个四阶奇偶归并的例子:假设归并前的的序列是(1,5,7,6)和(2,3,4,9),那么第一次操作就将(1,2,7,4)送入(2,2)归并器中归并,得到结果为(1,2,4,7);(5,3,6,9)送入(2,2)归并器中归并,得到结果为(3,5,6,9),接着将这两个排号序的序列进行洗牌比较:(1,3<->2,5<->4,6<->7,9)=>(1,2,3,4,5,6,7,9)。

可以证明这个算法是正确的,我们要用到高德纳(Donald Ervin Knuth)的0-1原理,我们发现,对于输入的任意两个有序的0,1序列,奇序列与偶序列正好相差0个,1个或2个0。由于奇序列的第一个元素不参与最后的洗牌比较,所以参与比较的0,1数偶只有0个或1个,所以对0,1序列一定能够得到正确的排序。故而对任意的序列,奇偶归并网络可以产生正确的排序。

双调归并网络是基于Batcher定理而构建的。Batcher定理是说将任意一个长为2n的双调序列A分为等长的两半X和Y,将X中的元素与Y中的元素一一按原序比较,即 a i {\displaystyle a_{i}} a i + n ( i n ) {\displaystyle a_{i+n}(i\leq n)} 比较,将较大者放入MAX序列,较小者放入MIN序列。则得到的MAX和MIN序列仍然是双调序列,并且MAX序列中的任意一个元素不小于MIN序列中的任意一个元素。

根据这个原理,我们可以将一个输入的n元素双调序列首先通过洗牌比较操作得到一个MAX序列和一个MIN序列,然后通过两个n/2阶双调归并器处理就可以得到一个有序序列。

这个算法也是递归的,因为n阶的双调归并器是由一个洗牌比较网络两个n/2阶的双调归并器组成的。

相关

  • 文艺复兴文艺复兴是一场大致发生在14世纪至17世纪欧洲的文化运动,在中世纪晚期发源于意大利中部的佛罗伦萨,即意大利文艺复兴,后扩展至欧洲各国。其辞源为意大利语“Rinascimento”,由ri
  • 美国化学学会美国化学学会(英语:American Chemical Society,简称为ACS)是一个化学领域的专业组织。1876年于美国纽约大学成立,现有157,000位来自化学与化工界各个分支的会员,总部位于华盛顿哥
  • 沙蚕约120种沙蚕(学名:Nereis),俗称沙虫,在福州称作流蜞,是多毛纲叶须虫目沙蚕科的一种环节动物。常栖息于泥沙中,生殖季节或夜出觅食时能游泳。可作为鱼类、虾、蟹等动物的食饵。体长1
  • 公路自行车公路自行车,俗称“公路车”或“自行车赛车”,是为公路骑行而设计的自行车车种,可用于公路自行车比赛。其赛事受到国际自行车联盟(UCI)规则的约束。这里所指的公路车,指的是竞赛用
  • 男性优于女性大男子主义(英语:Male chauvinism),又称男性沙文主义、男性至上主义、男性优越主义或者大男人主义,是一种认为男尊女卑、男性必定优于女性,因此男性更应统治女性的意识形态。沙文
  • 汗液汗液,或汗,是由人等高等动物透过汗腺所分泌出的液体。汗的分泌受到植物性神经系统调节。汗液的主要成分是水,约占总成分的98%到99%,其余物质为氯化钠,极少量的尿素、氨和其他盐类
  • 三氧化二镍三氧化二镍是镍的氧化物之一,化学式为Ni2O3。灰黑色无气味有光泽的块状物,易碎成细粉末。不溶于水,溶于氨水。溶于热盐酸并放出氯气。溶于硫酸和硝酸并放出氧气。600°C分解为
  • 筒井定庆筒井定庆(1556年?—1615年/1621年)是日本战国时代至江户时代初期的武将、大名。父亲是福住顺弘。母亲是筒井顺昭的次女。生年不详(一说1556年),家中次男。本名正次。哥哥顺元继承福
  • 听觉过敏听觉过敏是一种听力障碍,是听觉系统异常敏锐而失去对声音的忍受度,以及适听范围(dynamic range)明显的降低,有时也会伴随着耳鸣和耳痛,患有听觉过敏者难以忍受日常的声音,这些声
  • 三菱GTO三菱GTO,是日本三菱汽车生产的旗舰车款,为三菱最高精神超跑,1990年登场,2001年停产,属于三菱Starion的后继车。GTO,全名为Grand Touring Organization,GTO之名最早出现于1970年,当时