01先把问题说具体
每个位置都要知道自己之前元素的总和,怎样避免逐个等待前一项,也避免重复做大量加法?
02一步步得到方法
先区分包含当前元素与排除当前元素
输入 [3,1,7,0] 的排他扫描为 [0,3,4,11],第 i 项等于下标小于 i 的所有元素之和。包含当前元素的扫描则是 [3,4,11,11],可以在排他结果上逐项加原输入。
一种直接倍增方法每轮读更远的左邻居,虽然只有 O(log n) 轮,却做 O(n log n) 总工作。Blelloch 扫描使用树形上扫和下扫,把总工作降为 O(n)。
上扫先构造区间和
长度补成二次幂,空位填加法单位元 0。上扫先求长度 2 区间的和,再求长度 4、8 等区间,结果存放在各区间最右端。根节点最终保存整个数组总和。
扫描需要的是每个区间之前的总和,所以把根改成 0 开始下扫。对每个父区间,左孩子继承父前缀,右孩子得到父前缀加左子区间总和。
下扫传递前缀而非重复求和
原地布局中要先暂存左孩子的旧区间和,再用父前缀覆盖左孩子,最后把暂存值加到右孩子。顺序写反会丢失必要信息。
同一树层的区间互不重叠,可同时处理。以下代码串行模拟这些层,展示正确的数据依赖;真实实现还需要线程与层间同步。
03把一个小例子完全算清楚
输入 [3,1,7,0]。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 上扫 | [3,4,7,11] | 长度 2 局部和为 4、7,根为 11 |
| 根置零、第一轮下扫 | [3,0,7,4] | 左半前缀 0,右半前缀 4 |
| 第二轮下扫 | [0,3,4,11] | 每个叶子得到它之前的总和 |
窄屏可左右滑动表格,阅读完整计算与理由。
排他扫描结果为 [0,3,4,11],总和 11 可以单独保存。
04为什么这个方法成立
- 上扫不变量:每个已完成节点存储其区间的元素和。
- 下扫不变量:进入某节点时,已有该区间之前的总和;左孩子继承,右孩子再加左区间和。
- 叶子区间只含一个元素,因此叶子收到的值正是排他前缀;补零不改变真实元素的前缀。
05把推导翻译成代码
Python · Blelloch 扫描的串行层级模拟
def exclusive_scan(values):
n = len(values)
size = 1
while size<n:
size *= 2
data = list(values)+[0]*(size-n)
width = 2
while width<=size:
for end in range(width-1,size,width):
data[end] += data[end-width//2]
width *= 2
data[-1] = 0
width = size
while width>=2:
for end in range(width-1,size,width):
left = end-width//2
old_left = data[left]
data[left] = data[end]
data[end] += old_left
width //= 2
return data[:n]
print(exclusive_scan([3,1,7,0]))逐个理解关键决定
data[-1] = 0- 根从整段总和改成整段之前的空前缀。
old_left = data[left]- 覆盖左节点前保存其区间和,否则右前缀无法计算。
data[:n]- 移除二次幂补齐部分,只返回原输入对应的结果。
06时间、空间与实现范围
补齐长度小于 2n(n>0),上扫、下扫工作均为 O(n),跨度 O(log n)。
串行模拟耗时 O(n),使用 O(n) 空间;在真实并行机器上,层间同步与内存访问也有成本。
07改变条件,检查哪里会出错
根置零之前忘记保存总和
如果还需要总和,应先保存;扫描输出的最后一项不包含最后元素。
把原地改写次序颠倒
会把左子树总和覆盖掉,右前缀随之错误。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[2,5,1] 的排他扫描是什么?
需要一点提示
第 0 项是空前缀。
查看解析与答案
[0,2,7]。
如何从排他结果得到包含当前项的前缀和?
需要一点提示
逐项加原数组。
查看解析与答案
inclusive[i]=exclusive[i]+values[i]。
扫描可如何分配并行输出的位置?
需要一点提示
把每个任务的输出个数作扫描。
查看解析与答案
排他扫描给出各任务不重叠输出区间的起始偏移,用于压缩、过滤等操作。