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

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

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

Это кажется специально для 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

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

Доступ к отдельным элементам в dequeможет быть быстрее или медленнее, чем с помощью списков или кортежей. (Элементы в начале быстрее или элементы в конце, если вы используете отрицательный индекс.) Я помещаю sum(w)в тело моего цикла; это играет на прочность deque (итерация от одного элемента к другому выполняется быстро, поэтому этот цикл выполняется на 20% быстрее, чем следующий самый быстрый метод, pillmuncher's). Когда я изменил его, чтобы индивидуально искать и добавлять элементы в окне из десяти, таблицы поворачивались, и 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]

Вот обобщение , которое добавляет поддержку step, fillvalueпараметры:

from collections import deque
from itertools import islice

def sliding_window(iterable, size=2, step=1, fillvalue=None):
    if size < 0 or step < 1:
        raise ValueError
    it = iter(iterable)
    q = deque(islice(it, size), maxlen=size)
    if not q:
        return  # empty iterable or size == 0
    q.extend(fillvalue for _ in range(size - len(q)))  # pad to size
    while True:
        yield iter(q)  # iter() to avoid accidental outside modifications
        try:
            q.append(next(it))
        except StopIteration: # Python 3.5 pep 479 support
            return
        q.extend(next(it, fillvalue) for _ in range(step - 1))

Это приводит к тому, что sizeэлементы чанков за раз перемещаются stepна каждую итерацию, дополняя каждый чанк, fillvalueесли это необходимо. Пример для size=4, step=3, fillvalue='*':

 [a b c d]e f g h i j k l m n o p q r s t u v w x y z
  a b c[d e f g]h i j k l m n o p q r s t u v w x y z
  a b c d e f[g h i j]k l m n o p q r s t u v w x y z
  a b c d e f g h i[j k l m]n o p q r s t u v w x y z
  a b c d e f g h i j k l[m n o p]q r s t u v w x y z
  a b c d e f g h i j k l m n o[p q r s]t u v w x y z
  a b c d e f g h i j k l m n o p q r[s t u v]w x y z
  a b c d e f g h i j k l m n o p q r s t u[v w x y]z
  a b c d e f g h i j k l m n o p q r s t u v w x[y z * *]

Пример использования этого stepпараметра см. В разделе Эффективная обработка большого файла .txt в python .

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

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 не имеют «окна» в примерах itertool (т. Е. В нижней части http://docs.python.org/library/itertools.html ), вот фрагмент кода, основанный на коде для grouper, который один из приведенных примеров:

import itertools as it
def window(iterable, size):
    shiftedStarts = [it.islice(iterable, s, None) for s in xrange(size)]
    return it.izip(*shiftedStarts)

По сути, мы создаем серию нарезанных итераторов, каждый с отправной точкой на одну точку дальше. Затем мы соединяем их вместе. Обратите внимание, что эта функция возвращает генератор (это не сам генератор).

Подобно версиям appending-element и advising-iterator, приведенным выше, производительность (т. Е. Лучшая) зависит от размера списка и размера окна. Мне нравится этот, потому что это двухстрочный (он может быть однострочным, но я предпочитаю концепции именования).

Оказывается, приведенный выше код неверен . Это работает, если параметр, переданный в iterable, является последовательностью, но не если это итератор. Если это итератор, один и тот же итератор разделяется (но не tee'd) между вызовами islice, и это сильно нарушает работу.

Вот некоторый фиксированный код:

import itertools as it
def window(iterable, size):
    itrs = it.tee(iterable, size)
    shiftedStarts = [it.islice(anItr, s, None) for s, anItr in enumerate(itrs)]
    return it.izip(*shiftedStarts)

Также еще одна версия для книг. Вместо того, чтобы копировать итератор и затем многократно продвигать копии, эта версия делает попарные копии каждого итератора, когда мы перемещаем начальную позицию вперед. Таким образом, итератор t обеспечивает как «полный» итератор начальной точкой в ​​t, так и основой для создания итератора t + 1:

import itertools as it
def window4(iterable, size):
    complete_itr, incomplete_itr = it.tee(iterable, 2)
    iters = [complete_itr]
    for i in xrange(1, size):
        incomplete_itr.next()
        complete_itr, incomplete_itr = it.tee(incomplete_itr, 2)
        iters.append(complete_itr)
    return it.izip(*iters)

Просто чтобы показать, как вы можете комбинировать itertoolsрецепты , я расширяю pairwiseрецепт как можно напрямую обратно в windowрецепт, используя consumeрецепт:

def consume(iterator, n):
    "Advance the iterator n-steps ahead. If n is none, consume entirely."
    # Use functions that consume iterators at C speed.
    if n is None:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(islice(iterator, n, n), None)

def window(iterable, n=2):
    "s -> (s0, ...,s(n-1)), (s1, ...,sn), (s2, ..., s(n+1)), ..."
    iters = tee(iterable, n)
    # Could use enumerate(islice(iters, 1, None), 1) to avoid consume(it, 0), but that's
    # slower for larger window sizes, while saving only small fixed "noop" cost
    for i, it in enumerate(iters):
        consume(it, i)
    return zip(*iters)

windowРецепт такой же , как для pairwise, он просто заменяет один элемент «потребить» на втором tee-ED итератора с прогрессивно возрастающей потребляет на n - 1итераторы. Использование consumeвместо переноса каждого итератора isliceпроисходит немного быстрее (для достаточно больших итераций), поскольку вы платите только isliceиздержки переноса во время consumeфазы, а не во время извлечения каждого значения, редактируемого в окне (поэтому оно ограничено n, а не количеством элементов в iterable).

С точки зрения производительности, по сравнению с некоторыми другими решениями, это довольно хорошо (и лучше, чем любое другое решение, которое я тестировал по мере масштабирования). Протестировано на Python 3.5.0, Linux x86-64, с использованием ipython %timeitмагии.

Kindall это на dequeрешение , оптимальное для производительности / корректности, используя isliceвместо выражения генератора домашнего проката и тестирования полученной длины , так что не дают результаты , когда итерируемое короче , чем окно, а также прохождениям maxlenиз dequeпозиционно вместо по ключевому слову (имеет удивительное значение для небольших входных данных):

>>> %timeit -r5 deque(windowkindall(range(10), 3), 0)
100000 loops, best of 5: 1.87 μs per loop
>>> %timeit -r5 deque(windowkindall(range(1000), 3), 0)
10000 loops, best of 5: 72.6 μs per loop
>>> %timeit -r5 deque(windowkindall(range(1000), 30), 0)
1000 loops, best of 5: 71.6 μs per loop

То же, что и предыдущее адаптированное решение kindall, но с каждым yield winизменением на yield tuple(win)так, что сохранение результатов из генератора работает без того, чтобы все сохраненные результаты действительно являлись просмотром самого последнего результата (все другие разумные решения безопасны в этом сценарии), и добавление tuple=tupleв определение функции для перемещения использовать tupleот Bв LEGBк L:

>>> %timeit -r5 deque(windowkindalltupled(range(10), 3), 0)
100000 loops, best of 5: 3.05 μs per loop
>>> %timeit -r5 deque(windowkindalltupled(range(1000), 3), 0)
10000 loops, best of 5: 207 μs per loop
>>> %timeit -r5 deque(windowkindalltupled(range(1000), 30), 0)
1000 loops, best of 5: 348 μs per loop

consumeрешение, показанное выше:

>>> %timeit -r5 deque(windowconsume(range(10), 3), 0)
100000 loops, best of 5: 3.92 μs per loop
>>> %timeit -r5 deque(windowconsume(range(1000), 3), 0)
10000 loops, best of 5: 42.8 μs per loop
>>> %timeit -r5 deque(windowconsume(range(1000), 30), 0)
1000 loops, best of 5: 232 μs per loop

То же, что consumeи во встроенном elseслучае, consumeчтобы избежать вызова функции и n is Noneтестирования для сокращения времени выполнения, особенно для небольших входов, где накладные расходы на установку являются значимой частью работы:

>>> %timeit -r5 deque(windowinlineconsume(range(10), 3), 0)
100000 loops, best of 5: 3.57 μs per loop
>>> %timeit -r5 deque(windowinlineconsume(range(1000), 3), 0)
10000 loops, best of 5: 40.9 μs per loop
>>> %timeit -r5 deque(windowinlineconsume(range(1000), 30), 0)
1000 loops, best of 5: 211 μs per loop

(Примечание: вариант для pairwiseэтого, использующий teeаргумент по умолчанию 2 для создания вложенных teeобъектов несколько раз, поэтому любой данный итератор продвигается только один раз, а не потребляется независимо увеличивающееся количество раз, аналогично ответу MrDrFenner, аналогичному не встроенному consumeи медленнее, чем встроенные consumeво всех тестах, поэтому я опускаю эти результаты для краткости).

Как вы можете видеть, если вы не заботитесь о том, что вызывающей стороне нужно сохранять результаты, моя оптимизированная версия решения kindall выигрывает большую часть времени, за исключением «случая большого итерируемого малого размера окна» (где встроенные consumeвыигрыши ); он быстро ухудшается при увеличении итеративного размера, но не уменьшается вообще при увеличении размера окна (любое другое решение ухудшается медленнее при увеличении повторяемого размера, но также ухудшается при увеличении размера окна). Его можно даже адаптировать к случаю map(tuple, ...)«нужных кортежей», заключив его в оболочку, которая работает немного медленнее, чем добавление кортежей в функцию, но она тривиальна (занимает на 1-5% больше) и позволяет сохранить гибкость работы быстрее когда вы можете терпеть неоднократно возвращая одно и то же значение.

Если вам нужна защита от возврата возвратов, встроенные consumeвыигрыши будут у всех, кроме самых маленьких входных размеров (при не встроенном consumeнемного медленнее, но с одинаковым масштабированием). deque& Кортежи выигрывает решение , основанное только для самых маленьких входов, из - за меньшие затраты установки, и коэффициент усиление мало; это ухудшается плохо, поскольку повторяемое становится длиннее.

Для записи, адаптированной версии решения Kindall, что yieldS tupleS я использовал:

def windowkindalltupled(iterable, n=2, tuple=tuple):
    it = iter(iterable)
    win = deque(islice(it, n), n)
    if len(win) < n:
        return
    append = win.append
    yield tuple(win)
    for e in it:
        append(e)
        yield tuple(win)

Отбросьте кеширование tupleв строке определения функции и использование tupleв каждой, yieldчтобы получить более быструю, но менее безопасную версию.

Я использую следующий код в качестве простого скользящего окна, которое использует генераторы для значительного повышения читабельности. По моему опыту, его скорость была достаточной для использования в анализе последовательности биоинформатики.

Я включил его сюда, потому что я еще не видел этот метод. Опять же, я не претендую на его сравнительную производительность.

def slidingWindow(sequence,winSize,step=1):
"""Returns a generator that will iterate through
the defined chunks of input sequence. Input sequence
must be sliceable."""

    # Verify the inputs
    if not ((type(winSize) == type(0)) and (type(step) == type(0))):
        raise Exception("**ERROR** type(winSize) and type(step) must be int.")
    if step > winSize:
        raise Exception("**ERROR** step must not be larger than winSize.")
    if winSize > len(sequence):
        raise Exception("**ERROR** winSize must not be larger than sequence length.")

    # Pre-compute number of chunks to emit
    numOfChunks = ((len(sequence)-winSize)/step)+1

    # Do the work
    for i in range(0,numOfChunks*step,step):
        yield sequence[i:i+winSize]

def GetShiftingWindows(thelist, size):
    return [ thelist[x:x+size] for x in range( len(thelist) - size + 1 ) ]

>> a = [1, 2, 3, 4, 5]
>> GetShiftingWindows(a, 3)
[ [1, 2, 3], [2, 3, 4], [3, 4, 5] ]

немного измененная версия окна deque, чтобы сделать его действительно скользящим окном. Так что он начинает заполняться только одним элементом, затем увеличивается до максимального размера окна, а затем сжимается, когда его левый край приближается к концу:

from collections import deque
def window(seq, n=2):
    it = iter(seq)
    win = deque((next(it, None) for _ in xrange(1)), maxlen=n)
    yield win
    append = win.append
    for e in it:
        append(e)
        yield win
    for _ in xrange(len(win)-1):
        win.popleft()
        yield win

for wnd in window(range(5), n=3):
    print(list(wnd))

это дает

[0]
[0, 1]
[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4]
[4]

def rolling_window(list, degree):
    for i in range(len(list)-degree+1):
        yield [list[i+o] for o in range(degree)]

Сделано это для функции скользящего среднего

почему нет

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

Это задокументировано в Python doc . Вы можете легко расширить его до более широкого окна.

Несколько итераторов!

def window(seq, size, step=1):
    # initialize iterators
    iters = [iter(seq) for i in range(size)]
    # stagger iterators (without yielding)
    [next(iters[i]) for j in range(size) for i in range(-1, -j-1, -1)]
    while(True):
        yield [next(i) for i in iters]
        # next line does nothing for step = 1 (skips iterations for step > 1)
        [next(i) for i in iters for j in range(step-1)]

next(it)Возникает, StopIterationкогда последовательность завершена, и по какой-то классной причине, которая мне не подходит, оператор yield здесь исключает ее, и функция возвращает значение, игнорируя оставшиеся значения, которые не образуют полное окно.

В любом случае, это решение с наименьшим количеством строк, единственное требование которого заключается в том, чтобы seqреализовывать __iter__или __getitem__не полагаться на решение @ dansalmo itertoolsили, collectionsкроме него, :)

Давайте сделаем это ленивым!

from itertools import islice, tee

def window(iterable, size): 
    iterators = tee(iterable, size) 
    iterators = [islice(iterator, i, None) for i, iterator in enumerate(iterators)]  
    yield from zip(*iterators)

list(window(range(5), 3))
# [(0, 1, 2), (1, 2, 3), (2, 3, 4)]

#Importing the numpy library
import numpy as np
arr = np.arange(6) #Sequence
window_size = 3
np.lib.stride_tricks.as_strided(arr, shape= (len(arr) - window_size +1, window_size), 
strides = arr.strides*2)

"""Example output:

  [0, 1, 2]
  [1, 2, 3]
  [2, 3, 4]
  [3, 4, 5]

«»»

Я протестировал несколько решений, один из которых я нашел, и нашел тот, который я нашел, как самый быстрый, поэтому я решил поделиться им.

import itertools
import sys

def windowed(l, stride):
    return zip(*[itertools.islice(l, i, sys.maxsize) for i in range(stride)])

>>> n, m = 6, 3
>>> k = n - m+1
>>> print ('{}\n'*(k)).format(*[range(i, i+m) for i in xrange(k)])
[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]

Как насчет использования следующего:

mylist = [1, 2, 3, 4, 5, 6, 7]

def sliding_window(l, window_size=2):
    if window_size > len(l):
        raise ValueError("Window size must be smaller or equal to the number of elements in the list.")

    t = []
    for i in xrange(0, window_size):
        t.append(l[i:])

    return zip(*t)

print sliding_window(mylist, 3)

Вывод:

[(1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6), (5, 6, 7)]

Это старый вопрос, но для тех, кто все еще заинтересован, на этой странице есть отличная реализация ползунка с использованием генераторов (Адриан Роузброк).

Это реализация для OpenCV, однако вы можете легко использовать ее для любых других целей. Для желающих я вставлю сюда код, но для лучшего понимания рекомендую посетить исходную страницу.

def sliding_window(image, stepSize, windowSize):
    # slide a window across the image
    for y in xrange(0, image.shape[0], stepSize):
        for x in xrange(0, image.shape[1], stepSize):
            # yield the current window
            yield (x, y, image[y:y + windowSize[1], x:x + windowSize[0]])

Совет: Вы можете проверить .shapeокно при итерации генератора, чтобы отменить те, которые не соответствуют вашим требованиям

ура

Модифицированный ответ DiPaolo в разрешить произвольную заливку и переменный размер шага

import itertools
def window(seq, n=2,step=1,fill=None,keep=0):
    "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(itertools.islice(it, n))    
    if len(result) == n:
        yield result
    while True:        
#         for elem in it:        
        elem = tuple( next(it, fill) for _ in range(step))
        result = result[step:] + elem        
        if elem[-1] is fill:
            if keep:
                yield result
            break
        yield result

здесь один лайнер. Я рассчитал время, и это сравнимо с показателями топового ответа и постепенно улучшается с увеличением seq от 20% медленнее с len (seq) = 20 и на 7% медленнее с len (seq) = 10000

zip(*[seq[i:(len(seq) - n - 1 + i)] for i in range(n)])

Пытаюсь со своей стороны, простым, одним вкладышем, питоническим способом с использованием islice. Но не может быть оптимально эффективным.

from itertools import islice
array = range(0, 10)
window_size = 4
map(lambda i: list(islice(array, i, i + window_size)), range(0, len(array) - window_size + 1))
# output = [[0, 1, 2, 3], [1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8], [6, 7, 8, 9]]

Объяснение: Создайте окно с помощью islice из window_size и повторите эту операцию, используя map по всему массиву.

Оптимизированная функция для скользящего окна данных в глубоком обучении

def SlidingWindow(X, window_length, stride):
    indexer = np.arange(window_length)[None, :] + stride*np.arange(int(len(X)/stride)-window_length+4)[:, None]
    return X.take(indexer)