循环滑动窗迭代

Question

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

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

（所以

^{pr2}$

）

窗长3。在

我想取这个序列的滑动窗口和，但是是循环的；也就是说，计算长度-24list：

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

使用^{}和{a2}，我能想到的最好方法是

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)中的滑动窗口和（即，每个元素的时间不变，与窗口的大小无关）。在

这个想法是做一个“扫描转换”，从一开始就用所有元素的总和替换每个元素（这需要一次通过）。在

然后，从x0到x1的元素之和用O（1）计算

^{pr2}$

代码：

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))])

Answer 2

在每个连续的点上，加上新的（a[i]），减去旧的（a[i-3]）。为了绕回来，你可以把范围串起来。在

s = [sum(a[:3])]
for i in itertools.chain(range(3,len(a)), range(3)) :
  s.append( s[-1] + a[i] - a[i-3] )

Answer 3

一种快速的方法（至少对于大尺寸的窗口）：

sums = []
s = sum(a[:3])
for i, n in enumerate(a, 3-len(a)):
    sums.append(s)
    s += a[i] - n

类似，但使用itertools.accumulate：

^{pr2}$

或者像Shashank的，但是有负指数：

sums = [sum(a[:3])]
for i in range(-len(a), -1):
    sums.append(sums[-1] - a[i] + a[i+3])

一个简短而基本的方法，同样使用负指数：

[a[i] + a[i+1] + a[i+2] for i in range(-len(a), 0)]