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 (т. Е. Перебора соседних, перекрывающихся пар в последовательности) смотрите Также Как я могу перебирать перекрывающиеся (текущие, следующие) пары значений из списка?.}

В старой версии документации 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]

Это кажется специально разработанным для 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 все равно было немного быстрее. В целом я бы оценил, что любой из них достаточно быстр для большинства применений, и если вам нужно немного больше производительности, профилируйте и выбирайте тот, который работает лучше всего.

Мне нравится 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]

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

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