Batcher归并网络

✍ dations ◷ 2025-04-02 20:38:35 #并发计算

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阶的双调归并器组成的。

相关

  • Nasub2/subHe氦化钠是一种钠的稀有气体化合物,化学式为Na2He,其结构可表示为(Na+)2He(2e−),于2016年由中国化学家制得。氦化钠由钠与氦在高温与极高压(>113GPa)下合成。Na2He在接近1,500K的
  • 台地台地(英语:Plateau、table land)是一种凸起的面积较大且海拔较低的平面地形。台地中央的坡度平缓,四周较陡,直立于周围的低地丘陵。有人认为台地是高原的一种。但一般而言,海拔较
  • 沙拉武里府 small(北标府)/small沙拉武里府(泰语:จังหวัดสระบุรี,皇家转写:Changwat Saraburi,泰语发音:),是泰国中部的一个府。华人称其为北标府。沙拉武里府为一古老城市,建于1548年的大城时代,是作
  • 穆 青穆青(1921年-2003年),原名穆亚才,笔名穆肃,祖籍中国河南开封杞县,出生于安徽蚌埠,回族,中华人民共和国记者、新闻家。夫人续磊为将军续范亭之女。1937年,穆青参加八路军,并入学延安鲁迅
  • 埃尔山脉艾尔高原或称艾尔古地块,又译为阿伊尔高原(图阿雷格语:Ayăr;豪萨语: 东部 Azbin, 西部 Abzin)为一三角形地块(英语:massif),位于尼日尔北部,同时位在撒哈拉沙漠中。属西撒哈拉山地
  • 自然科学会报《自然科学会报》(The Philosophical Transactions of the Royal Society,缩写为 Phil. Trans.)是一本由英国皇家学会出版的科学期刊。它始创于1665年,是世界上最早专注于科学的
  • Return to myself《Return to myself》是日本女性创作歌手米仓千寻的第13张单曲。2000年7月26日由STARCHILD(King Records旗下公司)发行。《Return to myself》是动画《六门天外》采选当作动画
  • 卵形尖嵴蚌卵形尖嵴蚌(学名:)为蚌科珠蚌亚科尖嵴蚌属的淡水动物。本物种是中国的特有物种,分布于安徽、浙江、江苏、江西、湖北、湖南各省,常栖息于湖泊以及河流。
  • 清江镇 (金堂县)清江镇,是中华人民共和国四川省成都市金堂县下辖的一个乡镇级行政单位。2019年12月,撤消清江镇,所属行政区域划为官仓街道的行政区域。清江镇下辖以下地区:双江社区、花牌坊村、
  • 金融分析金融分析(又称财务分析),指以利润率、偿付能力、流动性、稳定性、增长历史与前景、同业比较等财务指标和方法,对企业、项目或投资的分析。金融分析师又可以细分为证券(股票)分析师