Вопрос-Ответ

Rolling or sliding window iterator?

Итератор скользящего окна?

Мне нужно скользящее окно (оно же sliding window), которое можно перебирать по последовательности / итератору / генератору. (Итерацию Python по умолчанию можно рассматривать как особый случай, когда длина окна равна 1.) В настоящее время я использую следующий код. Как я могу сделать это более элегантно и / или эффективно?

def rolling_window(seq, window_size):
it = iter(seq)
win = [it.next() for cnt in xrange(window_size)] # First window
yield win
for e in it: # Subsequent windows
win[:-1] = win[1:]
win[-1] = e
yield win

if __name__=="__main__":
for w in rolling_window(xrange(6), 3):
print w

"""Example output:
[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
"""


Для конкретного случая window_size == 2 (т. Е. Перебора соседних, перекрывающихся пар в последовательности) смотрите Также Как я могу перебирать перекрывающиеся (текущие, следующие) пары значений из списка?.

Переведено автоматически
Ответ 1

В старой версии документации Python есть такой итератор с itertools примерами:

from itertools import islice

def window(seq, n=2):
"Returns a sliding window (of width n) over data from the iterable"
" s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ... "
it = iter(seq)
result = tuple(islice(it, n))
if len(result) == n:
yield result
for elem in it:
result = result[1:] + (elem,)
yield result

Вариант из документации немного более лаконичен и использует itertools для большего эффекта, я полагаю.


Если ваш итератор представляет собой простой список / кортеж простым способом перемещения по нему с заданным размером окна было бы:

seq = [0, 1, 2, 3, 4, 5]
window_size = 3

for i in range(len(seq) - window_size + 1):
print(seq[i: i + window_size])

Вывод:

[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
Ответ 2

Это кажется специально разработанным для collections.deque поскольку у вас, по сути, есть FIFO (добавить с одного конца, удалить с другого). Однако, даже если вы используете list, вам не следует выполнять нарезку дважды; вместо этого вам, вероятно, следует просто pop(0) из списка и append() нового элемента.

Вот оптимизированная реализация на основе deque, созданная по образцу вашей оригинальной:

from collections import deque

def window(seq, n=2):
it = iter(seq)
win = deque((next(it, None) for _ in xrange(n)), maxlen=n)
yield win
append = win.append
for e in it:
append(e)
yield win

В моих тестах он в большинстве случаев превосходит все остальное, опубликованное здесь, хотя версия pillmuncher tee превосходит его для больших итераций и маленьких окон. В больших окнах deque снова выходит вперед по скорости raw.

Доступ к отдельным элементам в deque может быть быстрее или медленнее, чем со списками или кортежами. (Элементы в начале быстрее, или элементы в конце, если вы используете отрицательный индекс.) Я поместил sum(w) в тело моего цикла; это играет на руку результату (итерация от одного элемента к следующему выполняется быстро, поэтому этот цикл выполняется на целых 20% быстрее, чем следующий по быстродействию метод, pillmuncher). Когда я изменил его на индивидуальный поиск и добавление элементов в окне из десяти, таблицы поменялись местами, и tee метод стал на 20% быстрее. Я смог восстановить некоторую скорость, используя отрицательные индексы для последних пяти терминов в добавлении, но tee все равно было немного быстрее. В целом я бы оценил, что любой из них достаточно быстр для большинства применений, и если вам нужно немного больше производительности, профилируйте и выбирайте тот, который работает лучше всего.

Ответ 3

Мне нравится tee():

from itertools import tee, izip

def window(iterable, size):
iters = tee(iterable, size)
for i in xrange(1, size):
for each in iters[i:]:
next(each, None)
return izip(*iters)

for each in window(xrange(6), 3):
print list(each)

дает:

[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]
Ответ 4

Существует библиотека, которая делает именно то, что вам нужно:

import more_itertools
list(more_itertools.windowed([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],n=3, step=3))

Out: [(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12), (13, 14, 15)]
python algorithm