Мне нужно скользящее окно (оно же sliding window), которое можно перебирать по последовательности / итератору / генератору. (Итерацию Python по умолчанию можно рассматривать как особый случай, когда длина окна равна 1.) В настоящее время я использую следующий код. Как я могу сделать это более элегантно и / или эффективно?
defrolling_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
В старой версии документации Python есть такой итератор с itertools примерами:
from itertools import islice
defwindow(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)) iflen(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 inrange(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
defwindow(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
defwindow(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): printlist(each)
дает:
[0, 1, 2] [1, 2, 3] [2, 3, 4] [3, 4, 5]
Ответ 4
Существует библиотека, которая делает именно то, что вам нужно: