知识卡片
并行归并先写临时数组再拷回
并行归并把两个有序输入段的结果写到临时数组,使递归子任务写入互不重叠的位置;完成后再并行拷回原数组。
临时空间换来了清晰的输出边界与并发写安全。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第26章 并行算法 · 查看原书依据
It allocates a new array B[p : r] to hold the output of P-MERGE-AUX in line 1. It then calls P-MERGE-AUX in line 2, passing the indices of the two subarrays to be merged and providing B as the output destination of the merged result, starting at index p. After P-MERGE-AUX returns, lines 3–4 perform a parallel copy of the output B[p : r] into the subarray A[p : r], which is where P-MERGE-SORT expects it.
参考来源
- 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[70000,75000))。
- 结论依据:第26章 P-MERGE 第1–4行:分配临时 B、调用 P-MERGE-AUX 写 B,返回后 parallel for 拷回 A;P-MERGE-AUX 第9–14行以 q₃ 分割 B 的互不重叠输出区间。
- 原始内容:It allocates a new array B [ p : r ] to hold the output of P-M ERGE -A UX in line 1. It then calls P-M ERGE -A UX in line 2, passing the indices of the two subarrays to be merged and providing B as the output destination of the merged result, starting at index p . After P-M ERGE -A UX returns, lines 3–4 perform a parallel copy of the output B [ p : r ] into the subarray A [ p : r ], which is where P-M ERGE -S ORT expects it.
- 伪代码核对:P-MERGE-AUX 第9–14行将枢轴放在 B[q₃],两次递归写 B[p₃:q₃−1] 与 B[q₃+1:r₃]。