Итератор с подвижным или скользящим окном?
Мне нужно скользящее окно (иначе скользящее окно), повторяемое через последовательность / итератор / генератор. По умолчанию итерацию 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]
"""
31 ответ
В старой версии документации по 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
В моих тестах он ловко побеждает все остальное, что выкладывают здесь большую часть времени, хотя Pillmuncher's tee Версия превосходит его для больших итерируемых и маленьких окон. На больших окнах 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]
Есть библиотека, которая делает именно то, что вам нужно:
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)]
Вот обобщение, которое добавляет поддержку 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.
Просто быстрый вклад.
Поскольку текущие документы по 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)
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] ]
Просто чтобы показать, как вы можете комбинировать 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 итератор с постепенным увеличением потребления n - 1 итераторы. С помощью consume вместо того, чтобы обернуть каждый итератор в islice немного быстрее (для достаточно больших итераций), так как вы платите только islice обертывание во время consume фаза, а не в процессе извлечения каждого значения окна (так что оно ограничено n, а не количество предметов в iterable).
С точки зрения производительности, по сравнению с некоторыми другими решениями, это довольно хорошо (и лучше, чем любое другое решение, которое я тестировал по мере масштабирования). Протестировано на Python 3.5.0, Linux x86-64, с использованием ipython%timeit магия.
добрый 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, которое yield s tuple s я использовал был:
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]
Немного измененная версия окна 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]
Давайте сделаем это ленивым!
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)]
Почему бы и нет
def pairwise(iterable):
"s -> (s0,s1), (s1,s2), (s2, s3), ..."
a, b = tee(iterable)
next(b, None)
return zip(a, b)
Это задокументировано в Python doc. Вы можете легко расширить его до более широкого окна.
Я протестировал несколько решений и одно, которое придумал, и обнаружил, что придуманное мной самое быстрое, поэтому я подумал, что поделюсь им.
import itertools
import sys
def windowed(l, stride):
return zip(*[itertools.islice(l, i, sys.maxsize) for i in range(stride)])
def rolling_window(list, degree):
for i in range(len(list)-degree+1):
yield [list[i+o] for o in range(degree)]
Сделано это для функции скользящего среднего
В Python 3.10 у нас естьitertools.pairwise(iterable)функция для скольжения окна с двумя элементами:
Вот документ :
Вернуть последовательные перекрывающиеся пары, взятые из входного итерируемого объекта.
Количество двойных кортежей в выходном итераторе будет на единицу меньше, чем количество входов. Он будет пустым, если входная итерация имеет менее двух значений.
Примерно эквивалентно:
def pairwise(iterable): # pairwise('ABCDEFG') --> AB BC CD DE EF FG a, b = tee(iterable) next(b, None) return zip(a, b)
Несколько итераторов!
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__ и не полагается на itertools или же collections кроме решения @dansalmo:)
#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]
"""
Оптимизированная функция для данных скользящего окна в глубоком обучении
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)
Это старый вопрос, но для тех, кто по-прежнему заинтересован, на этой странице есть отличная реализация ползунка с использованием генераторов (Адриан Роузброк).
Это реализация для 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 окна при выполнении итерации генератора, чтобы отменить те, которые не соответствуют вашим требованиям
ура
Для не-итераторов я нахожу это решение более элегантным, чем использование встроенных функций.
words = ["this", "is", "an", "example"]
def get_sliding_windows(doc, sliding_window, padded=False):
all_windows = []
for i in range(sliding_window):
front = sliding_window-i
all_windows.append(front*['']+doc+i*[''])
if padded:
return np.array(all_windows).transpose()[1:]
else:
return np.array(all_windows).transpose()[sliding_window:-1]
>>> get_sliding_windows(words,3)
>>> array([['this', 'is', 'an'],
['is', 'an', 'example'],
['an', 'example', '']], dtype='<U7')
>>> get_padded_sliding_windows(words,3, True)
>>> array([['', '', 'this'],
['', 'this', 'is'],
['this', 'is', 'an'],
['is', 'an', 'example'],
['an', 'example', ''],
['example', '', '']], dtype='<U7')
Мое (пусть и простое) решение, которое я в итоге использовал:
def sliding_window(items, size):
return [items[start:end] for start, end
in zip(range(0, len(items) - size + 1), range(size, len(items) + 1))]
Излишне говорить, что
itemsпоследовательность должна быть нарезанной. Работа с индексами не идеальна, но, по-видимому, это наименее плохой вариант, учитывая альтернативы ... Его также можно легко изменить на генератор: просто замените
[...] с участием
(...).
>>> 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]
Изменен ответ 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
Пробую свою часть, простой, один лайнер, питонический способ с использованием 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 по всему массиву.
Как насчет использования следующего:
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)]
мои две версии
window выполнение
from typing import Sized, Iterable
def window(seq: Sized, n: int, strid: int = 1, drop_last: bool = False):
for i in range(0, len(seq), strid):
res = seq[i:i + n]
if drop_last and len(res) < n:
break
yield res
def window2(seq: Iterable, n: int, strid: int = 1, drop_last: bool = False):
it = iter(seq)
result = []
step = 0
for i, ele in enumerate(it):
result.append(ele)
result = result[-n:]
if len(result) == n:
if step % strid == 0:
yield result
step += 1
if not drop_last:
yield result
Еще один простой способ сгенерировать окно фиксированной длины из списка
from collections import deque
def window(ls,window_size=3):
window = deque(maxlen=window_size)
for element in ls:
if len(window)==window_size:
yield list(window)
window.append(element)
ls = [0,1,2,3,4,5]
for w in window(ls):
print(w)
Вот один лайнер. Я рассчитал его время, и он сопоставим с производительностью верхнего ответа и постепенно улучшается с увеличением seq с 20% медленнее с len(seq) = 20 и на 7% медленнее с len(seq) = 10000
zip(*[seq[i:(len(seq) - n - 1 + i)] for i in range(n)])