知识卡片

普通读书笔记卡 · 3674

归约把数组折叠为一个值

理解等级:初级

归约用结合运算把数组各项合为单一结果,例如求和。

结合律允许改变括号结构,因此可将连续区段并行归约后合并;若运算不满足结合律,重排可能改变结果。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第26章 并行算法 · 查看原书依据

      A ⊗-reduction of an array x[1 : n], where ⊗ is an associative operator, is the value y = x[1] ⊗ x[2] ⊗ ⋯ ⊗ x[n]. The REDUCE procedure computes the ⊗-reduction of a subarray x[i : j] serially. REDUCE (x, i, j) 1 y = x[i]

    参考来源

    - 位置:《算法导论(第4版)》第26章《并行算法》(OEBPS/chapter026.xhtml,文本字符[85000,90000))。 - 结论依据:原文定义或分析相应的并行结构、复杂度及约束条件;内容补充了使用边界。 - 原始内容:A ⊗- reduction of an array x [1 : n ], where ⊗ is an associative operator, is the value y = x [1] ⊗ x [2] ⊗ ⋯ ⊗ x [ n ]. The R EDUCE procedure computes the ⊗-reduction of a subarray x [ i : j ] serially. R EDUCE ( x , i , j ) 1 y = x [ i ]