Ich brauche ein rollendes Fenster (auch bekannt als Schiebefenster), das über eine Sequenz / Iterator / Generator iteriert werden kann. Die Standard-Python-Iteration kann als Sonderfall betrachtet werden, bei dem die Fensterlänge 1 beträgt. Ich verwende derzeit den folgenden Code. Hat jemand eine pythonischere, weniger ausführliche oder effizientere Methode, um dies zu tun?

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

Es gibt eine in einer alten Version der Python-Dokumente mit itertoolsBeispielen :

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

Der aus den Dokumenten ist etwas prägnanter und verwendet, itertoolswie ich mir vorstellen kann, eine größere Wirkung.

Dies scheint maßgeschneidert für a zu sein, collections.dequeda Sie im Wesentlichen ein FIFO haben (an einem Ende hinzufügen, vom anderen entfernen). Selbst wenn Sie a verwenden list, sollten Sie nicht zweimal in Scheiben schneiden. Stattdessen sollten Sie wahrscheinlich nur pop(0)aus der Liste und append()dem neuen Element.

Hier ist eine optimierte Deque-basierte Implementierung, die Ihrem Original nachempfunden ist:

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

In meinen Tests schlägt es die meiste Zeit handlich alles andere, was hier gepostet wurde, obwohl die Pillmuncher- teeVersion es für große Iterables und kleine Fenster schlägt. Bei größeren Fenstern dequefährt der in rauer Geschwindigkeit wieder vorwärts.

Der Zugriff auf einzelne Elemente in dequekann schneller oder langsamer sein als bei Listen oder Tupeln. (Elemente am Anfang sind schneller oder Elemente am Ende, wenn Sie einen negativen Index verwenden.) Ich habe ein Element sum(w)in den Körper meiner Schleife eingefügt. Dies spielt mit der Stärke der Deque (die Iteration von einem Gegenstand zum nächsten ist schnell, so dass diese Schleife 20% schneller lief als die nächstschnellste Methode, die Pillmuncher). Als ich es änderte, um Elemente in einem Zehnerfenster einzeln nachzuschlagen und hinzuzufügen, drehte sich der Spieß um und die teeMethode war 20% schneller. Ich konnte etwas Geschwindigkeit wiederherstellen, indem ich negative Indizes für die letzten fünf Begriffe in der Addition verwendete, war aber teeimmer noch etwas schneller. Insgesamt würde ich schätzen, dass beide für die meisten Anwendungen schnell genug sind. Wenn Sie etwas mehr Leistung benötigen, profilieren Sie und wählen Sie diejenige aus, die am besten funktioniert.

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

gibt:

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

Hier ist eine Verallgemeinerung , die Unterstützung für fügt hinzu step, fillvalueParameter:

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

Es liefert in Blöcken sizeElemente zu einem Zeitpunkt, in dem die stepPositionen pro Iteration rollt, wobei fillvaluebei Bedarf jeder Block aufgefüllt wird. Beispiel für 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 * *]

Ein Beispiel für einen Anwendungsfall für den stepParameter finden Sie unter Effizientes Verarbeiten einer großen TXT-Datei in Python .

Es gibt eine Bibliothek, die genau das tut, was Sie brauchen:

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

Nur ein kurzer Beitrag.

Da die aktuellen Python-Dokumente in den itertool-Beispielen (dh am Ende von http://docs.python.org/library/itertools.html ) kein "Fenster" haben , ist hier ein Ausschnitt, der auf dem Code für grouper basiert ist eines der angegebenen Beispiele:

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

Grundsätzlich erstellen wir eine Reihe von in Scheiben geschnittenen Iteratoren, von denen jeder einen Startpunkt einen Punkt weiter vorne hat. Dann reißen wir diese zusammen. Beachten Sie, dass diese Funktion einen Generator zurückgibt (es ist nicht direkt ein Generator selbst).

Ähnlich wie bei den obigen Versionen für Anhängeelemente und fortschreitende Iteratoren variiert die Leistung (dh die beste) je nach Listengröße und Fenstergröße. Ich mag dieses, weil es ein Zweiliner ist (es könnte ein Einzeiler sein, aber ich bevorzuge Namenskonzepte).

Es stellt sich heraus, dass der obige Code falsch ist . Es funktioniert, wenn der an iterable übergebene Parameter eine Sequenz ist, nicht jedoch, wenn es sich um einen Iterator handelt. Wenn es sich um einen Iterator handelt, wird derselbe Iterator von den islice-Aufrufen gemeinsam genutzt (aber nicht abgeschlagen), und dies führt zu einer schlechten Funktionsweise.

Hier ist ein fester Code:

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)

Auch noch eine Version für die Bücher. Anstatt einen Iterator zu kopieren und dann viele Male vorzurücken, erstellt diese Version paarweise Kopien jedes Iterators, während wir die Startposition vorwärts bewegen. Somit liefert der Iterator t sowohl den "vollständigen" Iterator mit dem Startpunkt bei t als auch die Basis zum Erstellen des Iterators 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)

Um zu zeigen, wie Sie itertoolsRezepte kombinieren können , erweitere ich das pairwiseRezept mit dem Rezept so direkt wie möglich wieder in windowdas consumeRezept:

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)

Das windowRezept ist das gleiche wie für pairwise, es ersetzt nur das einzelne Element "verbrauchen" auf dem zweiten teeIterator durch progressiv steigende Verzehr auf n - 1Iteratoren. Die Verwendung, consumeanstatt jeden Iterator einzuschließen, isliceist geringfügig schneller (für ausreichend große Iterables), da Sie den isliceUmbruchaufwand nur während der consumePhase zahlen , nicht während des Extrahierens jedes Fensters (also wird er durch ndie Anzahl der Elemente begrenzt) iterable).

In Bezug auf die Leistung ist dies im Vergleich zu einigen anderen Lösungen ziemlich gut (und besser als alle anderen Lösungen, die ich im Maßstab getestet habe). Getestet unter Python 3.5.0, Linux x86-64, mit ipython %timeitMagie.

Kindall ist die dequeLösung , gezwickt für die Leistung / Korrektheit durch die Verwendung isliceanstelle eines selbstgerollter Generator Expression und Testen der resultierenden Länge , so dass es keine Ergebnisse liefern , wenn die iterable kürzer als das Fenster ist, sowie die Weitergabe der maxlenvon der dequepositions anstelle von nach Schlüsselwort (macht einen überraschenden Unterschied bei kleineren Eingaben):

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

Wie die zuvor angepasste Kindall-Lösung, jedoch mit jeder yield winÄnderung, yield tuple(win)sodass das Speichern der Ergebnisse vom Generator funktioniert, ohne dass alle gespeicherten Ergebnisse wirklich eine Ansicht des neuesten Ergebnisses sind (alle anderen vernünftigen Lösungen sind in diesem Szenario sicher) und tuple=tuplezur Funktionsdefinition hinzugefügt werden um die Nutzung von tuplevon Bin LEGBnach zu verschieben 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-basierte Lösung wie oben gezeigt:

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

Gleich wie consume, aber inlining elseFall consume, um Funktionsaufruf und n is NoneTest zu vermeiden , um die Laufzeit zu reduzieren, insbesondere für kleine Eingaben, bei denen der Einrichtungsaufwand ein bedeutender Teil der Arbeit ist:

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

(Randnotiz: Eine Variante pairwise, die teemit dem Standardargument 2 wiederholt verschachtelte teeObjekte erstellt, sodass jeder Iterator nur einmal vorgerückt und nicht immer häufiger unabhängig verwendet wird, ähnlich wie die Antwort von MrDrFenner, ähnelt der von nicht inline consumeund langsamer als consumebei allen Tests angegeben, daher habe ich diese Ergebnisse der Kürze halber weggelassen.

Wie Sie sehen können, gewinnt meine optimierte Version der kindall-Lösung die meiste Zeit , wenn Sie sich nicht für die Möglichkeit interessieren, dass der Anrufer Ergebnisse speichern muss, außer im Fall "großer iterierbarer kleiner Fenstergröße" (wo Inline consumegewinnt ); es verschlechtert sich schnell, wenn die iterierbare Größe zunimmt, während es sich mit zunehmender Fenstergröße überhaupt nicht verschlechtert (jede andere Lösung verschlechtert sich langsamer, wenn die iterierbare Größe zunimmt, verschlechtert sich jedoch auch, wenn die Fenstergröße zunimmt). Es kann sogar durch Einwickeln an den Fall "Bedarfstupel" angepasst werden map(tuple, ...), der etwas langsamer läuft als das Einfügen des Tupels in die Funktion, aber es ist trivial (dauert 1-5% länger) und ermöglicht es Ihnen, die Flexibilität des schnelleren Laufens beizubehalten wenn Sie es tolerieren können, wiederholt denselben Wert zurückzugeben.

Wenn Sie Sicherheit gegen das Speichern von Retouren benötigen, consumegewinnt Inline bei allen bis auf die kleinsten Eingabegrößen (wobei Nicht-Inline consumeetwas langsamer ist, aber ähnlich skaliert). Die auf deque& tupling basierende Lösung gewinnt aufgrund geringerer Einrichtungskosten nur für die kleinsten Eingaben, und der Gewinn ist gering. es verschlechtert sich stark, wenn das iterable länger wird.

Für die Aufzeichnung der angepassten Version der Lösung des Kindall dass yields tuples ich verwendet wurde:

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)

Löschen Sie das Caching tuplein der Funktionsdefinitionszeile und die Verwendung von tuplein jedem yield, um die schnellere, aber weniger sichere Version zu erhalten.

Ich verwende den folgenden Code als einfaches Schiebefenster, das Generatoren verwendet, um die Lesbarkeit drastisch zu verbessern. Nach meiner Erfahrung war seine Geschwindigkeit bisher ausreichend für die Verwendung in der Bioinformatik-Sequenzanalyse.

Ich füge es hier ein, weil ich diese Methode noch nicht gesehen habe. Auch hier mache ich keinen Anspruch auf die verglichene Leistung.

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

Eine leicht modifizierte Version des Deque-Fensters, um es zu einem echten Rolling Window zu machen. Damit es mit nur einem Element gefüllt wird, dann auf die maximale Fenstergröße anwächst und dann schrumpft, wenn der linke Rand sich dem Ende nähert:

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

das gibt

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

Gemacht für eine gleitende Durchschnittsfunktion

warum nicht

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

Es ist in Python doc dokumentiert . Sie können es leicht auf ein breiteres Fenster erweitern.

Mehrere Iteratoren!

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)Raises , StopIterationwenn die Sequenz beendet, und aus irgendeinem kühlen Grunde , dass das über mich, die Ausbeute Aussage hier excepts es und die Funktion zurück, die übrig gebliebenen Werte ignorieren , die nicht mit einem vollen Fenster bilden.

Wie auch immer, dies ist die bisher kleinste Lösung, deren einzige Anforderung darin besteht, seqentweder die Lösung von @ dansalmo zu implementieren __iter__oder __getitem__nicht itertoolsoder nicht collections:)

Lass es uns faul machen!

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]

"" "

Ich habe ein paar Lösungen getestet und eine, die ich mir ausgedacht habe, und festgestellt, dass die, die ich mir ausgedacht habe, die schnellste ist, also dachte ich, ich würde sie teilen.

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]

Wie wäre es mit folgendem:

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)

Ausgabe:

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

Dies ist eine alte Frage, aber für diejenigen, die noch interessiert sind, gibt es auf dieser Seite eine großartige Implementierung eines Fensterschiebers mit Generatoren (von Adrian Rosebrock).

Es ist eine Implementierung für OpenCV, Sie können es jedoch problemlos für jeden anderen Zweck verwenden. Für die Eifrigen werde ich den Code hier einfügen, aber um ihn besser zu verstehen, empfehle ich, die Originalseite zu besuchen.

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

Tipp: Sie können .shapedas Fenster beim Iterieren des Generators überprüfen , um diejenigen zu verwerfen, die Ihren Anforderungen nicht entsprechen

Prost

Die Antwort von DiPaolo wurde geändert , um eine beliebige Füllung und eine variable Schrittgröße zu ermöglichen

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

Hier ist ein Einzeiler. Ich habe es zeitlich festgelegt und es ist kompatibel mit der Leistung der Top-Antwort und wird mit größerer Sequenz von 20% langsamer mit len ​​(seq) = 20 und 7% langsamer mit len ​​(seq) = 10000 zunehmend besser

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

Ich versuche meinen Teil, einfach, einzeilig, pythonisch mit islice. Ist aber möglicherweise nicht optimal effizient.

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

Erläuterung: Erstellen Sie ein Fenster mit islice von window_size und wiederholen Sie diese Operation mithilfe von map over all array.

Optimierte Funktion zum Schieben von Fensterdaten in Deep Learning

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)