知识卡片

普通读书笔记卡 · 3673.a.2

并行归并先写临时数组再拷回

理解等级:中级

并行归并把两个有序输入段的结果写到临时数组,使递归子任务写入互不重叠的位置;完成后再并行拷回原数组。

临时空间换来了清晰的输出边界与并发写安全。

这张卡片看不懂?

已有反馈 · 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₃]。