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

Ответ 1

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

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 вероятно предпочтительнее.

Ответ 2

На этой странице показано, как реализовать скользящее окно с 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)]

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

Ответ 3

Это моя версия, которая заполняет, сохраняя подпись так же. Я ранее видел рецепт 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 или не аккумулируйте вывод, так как он многократно возвращает один и тот же изменяемый элемент.

Ответ 4

Хорошо, опомнившись, вот нелепая версия 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 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 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 - размер window - потому что ему не нужно перебирать каждое окно. Но я все же думаю, что имеет смысл давать кортеж в общем случае, потому что вызывающая функция, вероятно, просто собирается перебирать деку в любом случае; это просто сдвиг вычислительной нагрузки. Асимптотика более крупной программы должна оставаться прежней.

Тем не менее, в некоторых особых случаях версия 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 работает довольно быстро, как выясняется - особенно для небольших окон.

Ответ 5

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

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)