Potrzebuję ruchomego okna (znanego również jako przesuwne okno), które można iterować po sekwencji / iteratorze / generatorze. Domyślną iterację Pythona można uznać za przypadek specjalny, w którym długość okna wynosi 1. Obecnie używam następującego kodu. Czy ktoś ma bardziej Pythonic, mniej rozwlekłą lub bardziej wydajną metodę robienia tego?

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

Jest jeden w starej wersji dokumentacji Pythona z itertoolsprzykładami :

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

Ten z dokumentacji jest trochę bardziej zwięzły i wykorzystuje go itertoolsdo większego efektu, jaki sobie wyobrażam.

Wydaje się, że jest to dostosowane do potrzeb, collections.dequeponieważ zasadniczo masz FIFO (dodaj na jednym końcu, usuń z drugiego). Jednak nawet jeśli używasz a list, nie powinieneś kroić dwa razy; zamiast tego prawdopodobnie powinieneś po prostu pop(0)z listy i append()nowej pozycji.

Oto zoptymalizowana implementacja oparta na deque wzorowana na oryginale:

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

W moich testach z łatwością pokonuje wszystko inne zamieszczone tutaj przez większość czasu, chociaż teewersja pillmunchera pokonuje go w przypadku dużych iteracji i małych okien. W większych oknachdeque znowu rusza do przodu z surową prędkością.

Dostęp do poszczególnych elementów dequemoże być szybszy lub wolniejszy niż w przypadku list lub krotek. (Elementy blisko początku są szybsze lub elementy zbliżone do końca, jeśli używasz indeksu ujemnego). Umieściłem sum(w)w treści mojej pętli; to działa na siłę deque (iteracja od jednego przedmiotu do drugiego jest szybka, więc ta pętla działała o pełne 20% szybciej niż następna najszybsza metoda, pillmuncher). Kiedy zmieniłem to, aby indywidualnie wyszukiwać i dodawać elementy w oknie dziesięciu, tabele się odwróciły i teemetoda była o 20% szybsza. Byłem w stanie odzyskać trochę szybkości, używając ujemnych indeksów dla ostatnich pięciu terminów w dodatku, ale teenadal byłem trochę szybszy. Ogólnie oceniam, że każdy z nich jest wystarczająco szybki dla większości zastosowań, a jeśli potrzebujesz trochę większej wydajności, profil i wybierz ten, który działa najlepiej.

Lubię 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)

daje:

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

Oto uogólnienie, które dodaje obsługę step, fillvalueparametrami:

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

Daje w kawałkach sizeelementy na raz, przesuwając steppozycje na iterację, wypełniając każdy fragment, fillvaluejeśli to konieczne. Przykład dla 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 * *]

Na przykład przypadku użycia dla step zapoznać parametru, zobacz wydajne przetwarzanie dużego pliku .txt w języku Python .

Istnieje biblioteka, która robi dokładnie to, czego potrzebujesz:

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

Tylko szybki wkład.

Ponieważ obecne dokumenty Pythona nie mają „okna” w przykładach narzędzi itertool (tj. Na dole strony http://docs.python.org/library/itertools.html ), oto fragment oparty na kodzie grupy, który to jeden z podanych przykładów:

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

Zasadniczo tworzymy serię podzielonych na plasterki iteratorów, z których każdy ma punkt początkowy o jedno miejsce dalej. Następnie łączymy je razem. Uwaga, ta funkcja zwraca generator (sam w sobie nie jest bezpośrednio generatorem).

Podobnie jak w powyższych wersjach elementu dołączającego i iteratora zaawansowanego, wydajność (tj. Która jest najlepsza) różni się w zależności od rozmiaru listy i rozmiaru okna. Podoba mi się ten, ponieważ jest dwuwierszowy (mógłby to być jeden wiersz, ale wolę koncepcje nazewnictwa).

Okazuje się, że powyższy kod jest błędny . Działa, jeśli parametr przekazany do iterowalnego jest sekwencją, ale nie, jeśli jest iteratorem. Jeśli jest to iterator, ten sam iterator jest współdzielony (ale nie trójnikowy) między wywołaniami islice, co źle wszystko psuje.

Oto trochę poprawionego kodu:

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)

Jeszcze jedna wersja książek. Zamiast kopiować iterator, a następnie wielokrotnie przesuwać kopie do przodu, ta wersja tworzy kopie parami każdego iteratora, gdy przesuwamy pozycję początkową do przodu. Zatem iterator t zapewnia zarówno „kompletny” iterator z punktem początkowym w t, jak i podstawę do utworzenia iteratora 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)

Aby pokazać, jak można łączyć itertoolsprzepisy , rozszerzam pairwiseprzepis tak bezpośrednio, jak to możliwe, z powrotem do windowprzepisu, korzystając z consumeprzepisu:

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)

windowRecepta jest taka sama, jak w przypadku pairwise, to po prostu zastępuje pojedynczy element „konsumować” na drugim tee-ED iterator ze stopniowo zwiększając zużywa na n - 1iteratory. Używanie consumezamiast zawijania każdego iteratora islicejest marginalnie szybsze (dla wystarczająco dużych iterable), ponieważ płacisz za islicezawijanie tylko podczas consumefazy, a nie podczas procesu wyodrębniania każdej wartości w oknie (więc jest ograniczona n, a nie liczbą elementów w iterable).

Pod względem wydajności, w porównaniu z niektórymi innymi rozwiązaniami, jest to całkiem niezłe (i lepsze niż jakiekolwiek inne rozwiązanie, które testowałem w miarę skalowania). Testowane w Pythonie 3.5.0, Linux x86-64, przy użyciuipython %timeit magii.

kindall znajduje się dequerozwiązanie , grunt pod wydajności / brytyjski stosując islicezamiast generatora ekspresji domowego walcowane i testowanie powstałych długość tak, że nie daje wyniki, gdy iterowalny jest krótszy niż okno, jak przepuszczanie maxlenz dequepozycyjnie zamiast według słów kluczowych (robi zaskakującą różnicę w przypadku mniejszych danych wejściowych):

>>> %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

Tak samo jak w poprzednim dostosowanym rozwiązaniu kindall, ale po każdej yield winzmianie na yield tuple(win)tak zapisywanie wyników z generatora działa bez wszystkich zapisanych wyników, które są w rzeczywistości widokiem najnowszego wyniku (wszystkie inne rozsądne rozwiązania są bezpieczne w tym scenariuszu) i dodają tuple=tupledo definicji funkcji przenieść wykorzystania tuplez Bsię LEGBdo 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

consumerozwiązanie bazowe pokazane powyżej:

>>> %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

To samo co consume, ale z wbudowanym elseprzypadkiem, consumeaby uniknąć wywoływania funkcji i n is Nonetestowania w celu skrócenia czasu działania, szczególnie w przypadku małych danych wejściowych, w których narzut konfiguracji jest znaczącą częścią pracy:

>>> %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

(Na marginesie: wariant pairwisetego używa teez domyślnym argumentem 2 wielokrotnie do tworzenia teeobiektów zagnieżdżonych , więc każdy podany iterator jest przesuwany tylko raz, a nie niezależnie konsumowany rosnącą liczbę razy, podobnie jak odpowiedź MrDrFennera jest podobna do odpowiedzi niewymienionej consumei wolniej niż inlineconsume we wszystkich testach, więc pominąłem te wyniki dla zwięzłości).

Jak widać, jeśli nie przejmujesz się możliwością przechowywania przez dzwoniącego wyników, moja zoptymalizowana wersja rozwiązania kindall wygrywa przez większość czasu, z wyjątkiem „dużego iterowalnego, małego rozmiaru okna” (gdzie inline consumewygrywa ); degraduje się szybko wraz ze wzrostem iterowalnego rozmiaru, ale w ogóle nie ulega degradacji wraz ze wzrostem rozmiaru okna (każde inne rozwiązanie degraduje się wolniej przy zwiększaniu iterowalnego rozmiaru, ale także degraduje się przy wzroście rozmiaru okna). Można go nawet dostosować do przypadku „potrzeby krotek” przez zawijaniemap(tuple, ...) , które działa nieco wolniej niż umieszczenie krotki w funkcji, ale jest trywialne (trwa 1-5% dłużej) i pozwala zachować elastyczność działania szybciej kiedy możesz tolerować wielokrotne zwracanie tej samej wartości.

Jeśli potrzebujesz bezpieczeństwa przed przechowywaniem zwrotów, inline consumewygrywa dla wszystkich oprócz najmniejszych rozmiarów wejściowych (gdzie nie-inline consumejest nieco wolniejszy, ale skaluje się podobnie). Plikdeque& Tupling wygrywa rozwiązanie oparte tylko dla najmniejszych nakładów, z powodu mniejszych kosztów instalacyjnych, a zysk jest niewielki; degraduje się źle, gdy iteracja staje się dłuższa.

Dla przypomnienia, dostosowanej wersji rozwiązania kindall że yieldS tupleS I użyto:

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)

Porzuć buforowanie tuplew linii definicji funkcji i użyj tuplew każdym yieldz nich, aby uzyskać szybszą, ale mniej bezpieczną wersję.

Używam poniższego kodu jako prostego przesuwanego okna, które wykorzystuje generatory, aby drastycznie zwiększyć czytelność. Z mojego doświadczenia wynika, że ​​do tej pory jego szybkość była wystarczająca do wykorzystania w bioinformatycznej analizie sekwencji.

Umieszczam to tutaj, ponieważ nie widziałem jeszcze tej metody. Ponownie, nie twierdzę, że jest porównywalny z wydajnością.

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

nieco zmodyfikowana wersja okna deque, aby było to prawdziwe okno toczące się. Tak więc zaczyna być wypełniany tylko jednym elementem, a następnie rośnie do maksymalnego rozmiaru okna, a następnie kurczy się, gdy jego lewa krawędź zbliża się do końca:

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

to daje

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

Wykonano to dla funkcji średniej kroczącej

Dlaczego nie

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

Jest to udokumentowane w Pythonie doc . Możesz go łatwo rozszerzyć na szersze okno.

Wiele iteratorów!

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)podnosi się, StopIterationgdy sekwencja jest zakończona iz jakiegoś fajnego powodu, który jest poza mną, instrukcja yield tutaj wyłącza ją i funkcja zwraca, ignorując pozostałe wartości, które nie tworzą pełnego okna.

W każdym razie, jest to jednak rozwiązanie najmniejszych linie którego jedynym wymaganiem jest to, że seqwdrożenie albo __iter__albo __getitem__i nie opiera się na itertoolslub collectionspoza użytkownika @ dansalmo rozwiązanie :)

Zróbmy to leniwie!

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]

„”

Przetestowałem kilka rozwiązań i jeden wymyśliłem i stwierdziłem, że ten, który wymyśliłem, jest najszybszy, więc pomyślałem, że się nim podzielę.

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]

Co powiesz na użycie następujących:

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)

Wynik:

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

To stare pytanie, ale dla tych, którzy nadal są zainteresowani, jest świetna implementacja suwaka okna przy użyciu generatorów na tej stronie (autor: Adrian Rosebrock).

Jest to implementacja dla OpenCV, jednak można ją łatwo wykorzystać do innych celów. Dla chętnych wkleję kod tutaj, ale aby lepiej go zrozumieć, polecam odwiedzenie oryginalnej strony.

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

Wskazówka: możesz sprawdzić .shapeokno podczas iteracji generatora, aby odrzucić te, które nie spełniają Twoich wymagań

Twoje zdrowie

Zmodyfikowano odpowiedź DiPaolo, aby umożliwić dowolne wypełnienie i zmienną wielkość kroku

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

tutaj jest jedna wkładka. Zmierzyłem czas i jest to porównywalne z wydajnością górnej odpowiedzi i staje się stopniowo lepsze przy większej sekwencji od 20% wolniej z len (seq) = 20 i 7% wolniej z len (seq) = 10000

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

Próbuję mojej części, prosty, jeden linijkowy, pythonowy sposób przy użyciu islice. Ale może nie być optymalnie wydajne.

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

Objaśnienie: Utwórz okno za pomocą islice o rozmiarze window_size i wykonaj iterację tej operacji, używając map over all array.

Zoptymalizowana funkcja dla danych przesuwanego okna w uczeniu głębokim

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)