PSRS算法

✍ dations ◷ 2025-02-23 15:05:04 #并发计算,算法

PSRS算法（Parallel Sorting by Regular Sampling）：首先设待处理里序列长n，并行机上有p个处理器。为了使问题简单，我们假设n是p的整倍数。于是将这n个元素划分为p段，每段中有n/p个元素，将这p段分给p个处理器。注意，执行PSRS算法的并行机必须是多指令流多数据流（MIMD）的。

如果注意到一个好的串行排序算法的时间复杂度为 $O(nlogn)$ $O(nlogn)$ 那么，容易证得上述PSRS算法的时间复杂度在 $n>p^{3}$ $n>p^{3}$ 时为 $O({\frac {n}{p}}log{n})$ $O({\frac {n}{p}}log{n})$ 。

缺点：我们注意到，在第五步进行主元划分时时可能会引起不均匀性，即位于某两个主元之间的元素可能要多一些（多于 ${\frac {n}{p}}$ ${\frac {n}{p}}$ 个）。我们可以证明，在算法中进行到第六步全局交换时，可能会有某一个处理器中数据达到 ${\frac {2n}{p}}-{\frac {n}{p^{2}}}-(p-1)$ ${\frac {2n}{p}}-{\frac {n}{p^{2}}}-(p-1)$ 个；这样引起的直接后果是处理器负载不均匀，那么在归并排序中可能会引起排序时间的不均匀。

并行计算并行排序

相关

闺密闺密、闺蜜可以指：
回应过程效度回应过程效度（英语：Response process validity）是心理统计学名词，属于测试效度（英语：Test validity），指的是受试者对于测验内容有多大程度的了解。譬如说：在不是变因的前提下，受试者对
台湾屏东地方法院坐标：22°39′22″N 120°28′59″E / 22.6562479°N 120.4829720°E / 22.6562479; 120.4829720900-05屏东县屏东市棒球路9号08-7550611 屏东简易庭：900-05屏东县屏东市合
路易·保罗·卡耶泰路易·保罗·卡耶泰（法语：Louis Paul Cailletet，1832年9月21日－1913年1月5日），法国物理学家、发明家。卡耶泰生于科多尔省塞纳河畔沙蒂永。他在巴黎接受了教育，后回到沙蒂永经营父
鞍山鞍山市是中华人民共和国辽宁省下辖的地级市，位于辽宁省中南部，是国务院批准的具有地方立法权的较大的市，是中国境内重要的钢铁基地，有钢都之称。鞍山市地处辽宁省中部，地理位置是
分布 (数学分析)数学分析中的分布是广义函数的一种，由法国数学家洛朗·施瓦茨首先于二十世纪五十年代引入。分布推广了普通意义上的函数概念。对于普通意义上不可导甚至不连续的函数，可以具备
东湖塘镇东湖塘镇是中国湖南省宁乡市下辖镇，位于宁乡县东南部。地缘上，东湖塘北与夏铎铺镇、坝塘镇接壤，西接韶山市杨林乡和清溪镇，南界花明楼镇，东与岳麓区雨敞坪镇接壤。辖域面积138平
堀内光雄堀内光雄（1930年1月1日－2016年5月17日），生于山梨县。是日本政治家。毕业于庆应义塾大学经济学部。山梨的铁路公司富士急行会长，曾任通商产业大臣、自民党政策调查会会长，2000年在
迈克尔拉·福克索娃迈克尔拉·福克索娃（捷克语：Michaela Fuchsová，1999年10月27日－），捷克女子羽毛球运动员。2016年9月，迈克尔拉·福克索娃出战斯洛伐克羽毛球公开赛，与阿尔泽比塔·巴索娃打进女子双
2016年夏季奥林匹克运动会男子100米仰泳比赛2016年夏季奥林匹克运动会男子100米仰泳比赛为2016年夏季奥林匹克运动会游泳比赛的其中一项竞赛项目，赛事于2016年8月7日至8月8日在奥林匹克水上运动中心中举行。以下是比赛