Циклическое раздвижное окно Iteration

Рассмотрим некоторую заданную последовательность и длину окна, скажем, 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 и глупые трюки лямбда, было

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

Есть ли что-то менее ужасное?

Ответ 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))])

Ответ 2

Если вы не против использования 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])

Другое решение, которое эффективно объединяет две идеи и заимствует идею сохранения переменных из решения Стефана Похмана:

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

Ответ 3

Это будет работать для любого 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:

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

Или используя modulo:

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)

Ответ 4

Быстрый способ (по крайней мере, для больших размеров окна):

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, но с отрицательными индексами:

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

Ответ 5

В каждую последующую точку добавьте новый (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] )

Ответ 6

Вы можете использовать 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]
>>>

Обратите внимание, что мы создали new с конкатенированием первых двух элементов a до конца a, а 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)]