週期性推拉窗迭代

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和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

怎麼樣簡單

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）

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 2

您可以使用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和zip(new,new[1:],new[2:])最終會給你的願望子集，那麼你可以創建new使用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 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)] 

你也可以寫爲這個抽象的窗口長度方面：

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

這裏是另一種解決方案是在窗口長度方面更具擴展性的解決方案：

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

另一種解決方案，能有效地結合了這兩種思路和借鑑變量保存想法從斯特凡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

這將使用islice和總和任何n工作：

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產量：

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

的一個快速方法（至少在大窗口大小）：

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

或者像沙善的，但有負面指標：

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