PSRS算法

✍ dations ◷ 2025-11-12 00:43:06 #并发计算,算法

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)$ 个；这样引起的直接后果是处理器负载不均匀，那么在归并排序中可能会引起排序时间的不均匀。

并行计算并行排序

相关

口吃口吃（俗称“结巴”、“磕巴”、“漏口”，在台湾，国语念作“kǒu jí”；中国大陆普通话与新马两地则念作“kǒu chī”；古汉语中叫謇。），是一种言语障碍，表现为言语频繁地与正常流利
车苏语彝语东部方言，是彝语的一种方言，主要分布在云南省东北部和中部、四川省南部、贵州省西部、广西壮族自治区西部，使用人数约有120万。操这种方言的人自称“诺苏”.mw-parser-outp
星期二星期二，又称为礼拜二或周二。是指在星期一和星期三之间的一天。拉丁语名字为dies Martis来源于古罗马神话战神玛尔斯或火星；法语为mardi，来源于拉丁语；英文名字（Tuesday）来源于北
美国联合碳化物美国联合碳化物（Union Carbide），创办于1898年，是美国的主要石油化工公司，现时为美国陶氏化工的全资附属公司。该公司在1917年前，都不算主要的大公司，直至1917年，该公司取得乙烯（Ethen
猪血猪血是指猪的血液。在世界各地都有人类食用猪血的例子。在中国，满族，藏族，蒙古族人民有食用血肠的习惯，在欧洲和美国，也有人制作各式各样的血肠，血肠制作成分包含猪血。猪血也被人
观察家报观察家报（）是英国的一份报纸。于每周周日发行。观察家报实际上是周一到周六发行的卫报的周日版。政治立场偏向自由主义和社会民主主义。观察家报创刊于1791年12月4日，是世界第
圣托纳圣托纳（德语：Heilige Totnan，？年－689年) 是一位公元7世纪出生、在今德国境内弗兰肯传教的爱尔兰传教士，他和圣基利安、圣柯尔曼在弗兰肯共同进行基督教的传播。689年，他与和他共事
杜尔加普尔杜尔加普尔（Durgapur），是印度马哈拉施特拉邦钱德拉布尔县的一个城镇。总人口17369（2001年）。该地2001年总人口17369人，其中男性8688人，女性8681人；0—6岁人口2486人，其中男1305人，女11
吴都文粹《吴都文粹》，宋朝郑虎臣编，共九卷，记载了吴郡（今苏州）遗文。所录有宋朝李寿朋、汪应辰、赵肃等札奏。《四库总目提要》：“书虽称文粹，实与地志相表里。东南文献，藉是有征；与范成大《
桌上游戏列表下面的列表列举了部分桌上游戏。同一游戏按不同的标准分类时可能重复出现，对于在某一标准下类别不明的游戏未将其列出。