循环滑动Window迭代

Question

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

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

(所以

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

)

和window长度3.

我想取这个序列的滑动 window 总和，但是是循环的；即，计算长度 24 list:

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

使用 collections.deque and Stupid Lambda Tricks 我能想到的最好的是

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

您可以将 map 与 zip 函数一起使用：

>>> new=a+a[:2]
>>> new
[1, 14, 27, 40, 53, 66, 79, 92, 105, 118, 131, 144, 157, 170, 183, 196, 209, 222, 235, 248, 261, 274, 287, 300, 1, 14]
>>> map(sum,zip(new,new[1:],new[2:]))
[42, 81, 120, 159, 198, 237, 276, 315, 354, 393, 432, 471, 510, 549, 588, 627, 666, 705, 744, 783, 822, 861, 588, 315]
>>>

请注意，我们通过将 a 的前 2 个元素连接到 a 的末尾来创建 new，然后 zip(new,new[1:],new[2:]) 将为您提供所需的子集您可以使用 map 函数对其应用 sum 函数：

>>> zip(new,new[1:],new[2:])
[(1, 14, 27), (14, 27, 40), (27, 40, 53), (40, 53, 66), (53, 66, 79), (66, 79, 92), (79, 92, 105), (92, 105, 118), (105, 118, 131), (118, 131, 144), (131, 144, 157), (144, 157, 170), (157, 170, 183), (170, 183, 196), (183, 196, 209), (196, 209, 222), (209, 222, 235), (222, 235, 248), (235, 248, 261), (248, 261, 274), (261, 274, 287), (274, 287, 300), (287, 300, 1), (300, 1, 14)]

Answer 2

那简单的呢

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

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

想法是 "scan conversion" 从一开始就用所有元素的总和替换每个元素（这需要单遍）。

然后用

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

Answer 3

如果您不介意使用 itertools，这是一种解决方案：

from itertools import cycle, islice
a_one = islice(cycle(a), 1, None)
a_two = islice(cycle(a), 2, None)
sums = [sum(t) for t in zip(a, a_one, a_two)]

您还可以根据 window 长度为此编写一个抽象：

wlen = 3
a_rotations = (islice(cycle(a), i, None) for i in range(1, wlen))
sums = [sum(t) for t in zip(a, *a_rotations)]

这是另一种解决方案，在 window 长度方面更具可扩展性：

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

另一个有效结合这两个想法并借鉴了 Stefan Pochmann 解决方案的变量保存想法的解决方案：

from itertools import islice, cycle
wlen = 3
rotatediterator = islice(cycle(a), wlen, None)
sums = []
lastsum = sum(a[:wlen])
for addval, subval in zip(rotatediterator, a):
    sums.append(lastsum)
    lastsum += addval - subval

Answer 4

这适用于任何 n 使用 islice 和 sum:

from itertools import cycle, islice
def rolling_window(func, l, n):
    for i in xrange(len(l)):
        yield func(islice(cycle(l), i, n+i))


print(list(rolling_window(sum,l,3)))

[42, 81, 120, 159, 198, 237, 276, 315, 354, 393, 432, 471, 510, 549, 588, 627, 666, 705, 744, 783, 822, 861, 588, 315]

或使用 python3 中的 yield:

from itertools import cycle, islice
def rolling_window(func, l, n):
     yield from (func(islice(cycle(l), i, n+i)) for i in range(len(l)))

或使用模数：

out, ln, n = [], len(l), 3
sm = sum(l[:n])
for i in range(1, 25):
    out.append(sm)
    sm = sm - l[(i - 1) % ln] + l[(i+n-1) % ln]
print(out)

Answer 5

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

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

类似，但使用 itertools.accumulate:

acc = list(accumulate([0] + a + a))
print([acc[i+3] - acc[i] for i in range(len(a))])

或者像 Shashank's 但有负索引：

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

Answer 6

在每个连续的点，添加新的 (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] )

循环滑动Window迭代

Cyclical Sliding Window Iteration

python

list-comprehension

itertools