Итерация над «окном» соседних элементов в Python

На этой странице показано, как реализовать скользящее окно с помощью itertools . http://docs.python.org/release/2.3.5/lib/itertools-example.html

 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 

Пример вывода:

 >>> list(window(range(10))) [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)] 

Вам нужно будет изменить его, чтобы заполнить влево и вправо, если вам нужно.

Это моя версия, которая заполняет, сохраняя подпись так же. Я ранее видел рецепт itertools , но не смотрел на него, прежде чем писать это.

 from itertools import chain from collections import deque def ia(gen, fill=0, size=2, fill_left=True, fill_right=False): gen, ssize = iter(gen), size - 1 deq = deque(chain([fill] * ssize * fill_left, (next(gen) for _ in xrange((not fill_left) * ssize))), maxlen = size) for item in chain(gen, [fill] * ssize * fill_right): deq.append(item) yield deq 

Изменить: я также не видел ваших комментариев по вашему вопросу, прежде чем публиковать это.

Изменить 2: Исправлено. Я пытался сделать это с одной chain но для этого дизайна нужны два.

Редактирование 3: Как заметил @senderle, используйте его только как генератор, не обертывайте его list или не накапливайте вывод, так как он многократно возвращает один и тот же изменяемый элемент.

Хорошо, после того, как я опомнился, вот нелепая версия window_iter_fill . Моя предыдущая версия (видимая в редактировании) была ужасной, потому что я забыл использовать izip . Не уверен, что я думал. Используя izip, это работает и, по сути, является самым быстрым вариантом для небольших входов!

 def window_iter_fill(gen, size=2, fill=None): gens = (chain(repeat(fill, size - i - 1), gen, repeat(fill, i)) for i, gen in enumerate(tee(gen, size))) return izip(*gens) 

Это тоже отлично подходит для кормления, но не так быстро.

 def window_iter_deque(it, size=2, fill=None, fill_left=False, fill_right=False): lfill = repeat(fill, size - 1 if fill_left else 0) rfill = repeat(fill, size - 1 if fill_right else 0) it = chain(lfill, it, rfill) d = deque(islice(it, 0, size - 1), maxlen=size) for item in it: d.append(item) yield tuple(d) 

Новейшее решение HoverHell по-прежнему является лучшим решением для высоких затрат.

Некоторые тайминги:

 Arguments: [xrange(1000), 5, 'x', True, True] ============================================================================== window HoverHell's frankeniter : 0.2670ms [1.91x] window_itertools from old itertools docs : 0.2811ms [2.02x] window_iter_fill extended `pairwise` with izip : 0.1394ms [1.00x] window_iter_deque deque-based, copying : 0.4910ms [3.52x] ia_with_copy deque-based, copying v2 : 0.4892ms [3.51x] ia deque-based, no copy : 0.2224ms [1.60x] ============================================================================== 

Масштабирование:

 Arguments: [xrange(10000), 50, 'x', True, True] ============================================================================== window HoverHell's frankeniter : 9.4897ms [4.61x] window_itertools from old itertools docs : 9.4406ms [4.59x] window_iter_fill extended `pairwise` with izip : 11.5223ms [5.60x] window_iter_deque deque-based, copying : 12.7657ms [6.21x] ia_with_copy deque-based, copying v2 : 13.0213ms [6.33x] ia deque-based, no copy : 2.0566ms [1.00x] ============================================================================== 

Решение, получающее deque от agf, является супер быстрым для больших входов – по-видимому, O (n) вместо O (n, m), как и другие, где n – длина итера, а m – размер окна – потому что ему не нужно перебирать каждое окно. Но я все же думаю, что имеет смысл давать кортеж в общем случае, потому что вызывающая функция, вероятно, просто собирается перебирать деку в любом случае; это просто сдвиг вычислительной нагрузки. Асимптотика более крупной программы должна оставаться неизменной.

Тем не менее, в некоторых особых случаях версия с deque версией, вероятно, будет быстрее.

Еще несколько таймингов, основанных на тестовой структуре HoverHell.

 >>> import testmodule >>> kwa = dict(gen=xrange(1000), size=4, fill=-1, fill_left=True, fill_right=True) >>> %timeit -n 1000 [a + b + c + d for a, b, c, d in testmodule.window(**kwa)] 1000 loops, best of 3: 462 us per loop >>> %timeit -n 1000 [a + b + c + d for a, b, c, d in testmodule.ia(**kwa)] 1000 loops, best of 3: 463 us per loop >>> %timeit -n 1000 [a + b + c + d for a, b, c, d in testmodule.window_iter_fill(**kwa)] 1000 loops, best of 3: 251 us per loop >>> %timeit -n 1000 [sum(x) for x in testmodule.window(**kwa)] 1000 loops, best of 3: 525 us per loop >>> %timeit -n 1000 [sum(x) for x in testmodule.ia(**kwa)] 1000 loops, best of 3: 462 us per loop >>> %timeit -n 1000 [sum(x) for x in testmodule.window_iter_fill(**kwa)] 1000 loops, best of 3: 333 us per loop 

В целом, как только вы используете izip , window_iter_fill довольно быстро, как выясняется – особенно для маленьких окон.

Результирующая функция (из редактирования вопроса),

frankeniter с идеями из ответов @agf, @FogleBird, @senderle, получившийся в некоторой степени аккуратный фрагмент кода:

 from itertools import chain, repeat, islice def window(seq, size=2, fill=0, fill_left=True, fill_right=False): """ Returns a sliding window (of width n) over data from the iterable: s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ... """ ssize = size - 1 it = chain( repeat(fill, ssize * fill_left), iter(seq), repeat(fill, ssize * fill_right)) result = tuple(islice(it, size)) if len(result) == size: # `<=` if okay to return seq if len(seq) < size yield result for elem in it: result = result[1:] + (elem,) yield result 

и, для некоторой информации о производительности относительно deque / tuple:

 In [32]: kwa = dict(gen=xrange(1000), size=4, fill=-1, fill_left=True, fill_right=True) In [33]: %timeit -n 10000 [a+b+c+d for a,b,c,d in tmpf5.ia(**kwa)] 10000 loops, best of 3: 358 us per loop In [34]: %timeit -n 10000 [a+b+c+d for a,b,c,d in tmpf5.window(**kwa)] 10000 loops, best of 3: 368 us per loop In [36]: %timeit -n 10000 [sum(x) for x in tmpf5.ia(**kwa)] 10000 loops, best of 3: 340 us per loop In [37]: %timeit -n 10000 [sum(x) for x in tmpf5.window(**kwa)] 10000 loops, best of 3: 432 us per loop 

но в любом случае, если это цифры, то numpy, вероятно, предпочтительнее.

Я удивлен, что никто не принял простой сопрограммный подход.

 from collections import deque def window(n, initial_data=None): if initial_data: win = deque(initial_data, n) else: win = deque(((yield) for _ in range(n)), n) while 1: side, val = (yield win) if side == 'left': win.appendleft(val) else: win.append(val) win = window(4) win.next() print(win.send(('left', 1))) print(win.send(('left', 2))) print(win.send(('left', 3))) print(win.send(('left', 4))) print(win.send(('right', 5))) ## -- Results of print statements -- deque([1, None, None, None], maxlen=4) deque([2, 1, None, None], maxlen=4) deque([3, 2, 1, None], maxlen=4) deque([4, 3, 2, 1], maxlen=4) deque([3, 2, 1, 5], maxlen=4)