循环滑动窗口迭代

Question

考虑一些给定的序列和窗口长度,比如说 list

a = [13 * i + 1 for i in range(24)]

(以便

In [61]: a
Out[61]: 
[1,
 14,
 27,
 40,
 ...,
 287,
 300]

)

和窗口长度3.

我想把这个序列的滑动窗口总和,但是周期性地; 即,计算长度-24 list:

[sum([1, 14, 27]),
 sum([14, 27, 40]),
 ...,
 sum([287, 300, 1]),
 sum([300, 1, 14])]

我能想到的最好的,使用collections.deque和愚蠢的Lambda技巧,是

d = collections.deque(range(24))
d.rotate(1)
map(lambda _: d.rotate(-1) or sum(a[i] for i in list(d)[: 3]), range(24))

有什么不那么可怕的东西吗？

Answer 1

那简单的呢

a = [13 * i + 1 for i in range(24)]
w = 3

aa = a + a[:w]
print([sum(aa[i:i+w]) for i in range(len(a))])

请注意，如果窗口很大，则有更好的方法来计算滑动窗口总和O(n)（即每个元素的时间恒定，与窗口的大小无关）。

这个想法是进行“扫描转换”，从一开始就将每个元素替换为所有元素的总和（这需要单遍）。

之后，在 O(1) 中计算从 x0 到 x1 的元素之和：

sum_table[x1] - sum_table[x0]

在代码中：

sum_table = [0]
for v in a:
    sum_table.append(sum_table[-1] + v)
for v in a[:w]:
    sum_table.append(sum_table[-1] + v)
print([sum_table[i+w] - sum_table[i] for i in range(len(a))])