Cyclical Sliding Window Iteration

Question

Consider some given sequence and a window length, say the list

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

(so that

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

)

and window length 3.

I'd like to take the sliding window sum of this sequence, but cyclically; i.e., to calculate the length-24 list:

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

The best I could come up with, using collections.deque and Stupid Lambda Tricks, was

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

Is there something less horrible?

Answer 1

What about the simple

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

Note that if the window is big there are better ways to compute a sliding window sum in O(n) (i.e. with a constant time per element, independently of the size of the window).

The idea is to do a "scan conversion" replacing each element with the sum of all elements from the start (this requires single pass).

After that the sum of elements from x0 to x1 is then computed in O(1) with

sum_table[x1] - sum_table[x0]

In code:

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

At each successive point, add in the new one (a[i]) and subtract out the old (a[i-3]). To wrap back around, you can chain the ranges.

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

A fast way (at least for large window sizes):

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

Similar, but using itertools.accumulate:

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

Or like Shashank's but with negative indexes:

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

And a short and basic one, again using negative indexes:

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

Answer 4

If you don't mind using itertools, this is one solution:

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

You could also write an abstraction for this in terms of the window length:

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

Here is another solution that is more scalable solution in terms of window length:

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

Another solution which efficiently combines the two ideas and borrows the variable save idea from Stefan Pochmann's solution:

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