webentwicklung-frage-antwort-db.com.de

Rollender oder gleitender Fensteriterator?

Ich brauche ein rollendes Fenster (aka Schiebefenster), das über einen Sequenz/Iterator/Generator iterierbar ist. Die Standard-Python-Iteration kann als Sonderfall betrachtet werden, bei dem die Fensterlänge 1 ist. Derzeit verwende ich den folgenden Code. Hat jemand eine Pythonic-Methode, eine 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]
"""
121
David B.

Es gibt einen in einer alten Version der Python-Dokumente mit itertools Beispielen :

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

Das Dokument aus den Dokumenten ist etwas prägnanter und nutzt itertools, um die Wirkung besser zu stellen.

101
Daniel DiPaolo

Dies scheint für einen collections.deque maßgeschneidert zu sein, da Sie im Wesentlichen ein FIFO haben (zu einem Ende hinzufügen, vom anderen entfernen). Selbst wenn Sie eine list verwenden, sollten Sie nicht zweimal schneiden. Stattdessen sollten Sie wahrscheinlich nur pop(0) aus der Liste und append() das neue Element verwenden.

Hier ist eine optimierte Deque-basierte Implementierung nach dem Original:

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 übertrifft er alles andere, was meistens hier veröffentlicht wird, obwohl die Version tee von Pillmuncher es für große iterable und kleine Fenster schlägt. Bei größeren Fenstern zieht die deque wieder mit roher Geschwindigkeit voran.

Der Zugriff auf einzelne Elemente in der deque kann 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 füge eine sum(w) in den Hauptteil meiner Schleife ein. Dies spielt die Stärke des Deques (das Iterieren von einem Element zum nächsten ist schnell, daher lief diese Schleife um 20% schneller als die nächstbeste Methode, die von Pillmuncher). Wenn ich es geändert habe, um Elemente in einem Fenster mit zehn Elementen einzeln zu suchen und hinzuzufügen, wurden die Tabellen gedreht und die tee-Methode war 20% schneller. Durch die Verwendung negativer Indizes für die letzten fünf Terme in der Addition konnte ich etwas Geschwindigkeit gewinnen, aber tee war immer noch etwas schneller. Insgesamt würde ich schätzen, dass beide für die meisten Anwendungen sehr schnell sind und wenn Sie etwas mehr Leistung, Profil und Auswahl benötigen, die am besten funktioniert.

44
kindall

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

Hier eine Verallgemeinerung, die Unterstützung für step, fillvalue-Parameter hinzufügt:

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 ergibt in Abschnitten size-Elemente zu einem Zeitpunkt, an dem step-Positionen pro Iteration gerollt werden, wobei jeder Abschnitt mit fillvalue 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 Anwendungsbeispiel für den Parameter step finden Sie unter Eine große TXT-Datei effizient in Python bearbeiten .

16
jfs

Nur ein kurzer Beitrag.

Da die aktuellen Python-Dokumente kein "Fenster" in den itertool-Beispielen haben (dh am Ende von http://docs.python.org/library/itertools.html ), finden Sie hier einen Ausschnitt aus dem Code für Grouper, der eines der folgenden Beispiele ist:

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 aufgeschnittenen Iteratoren, von denen jeder einen Punkt weiter vorne liegt. Dann machen wir diese zusammen. Beachten Sie, dass diese Funktion einen Generator zurückgibt (es ist nicht direkt ein Generator selbst).

Ähnlich wie bei den Anhängeelement- und Vorlauf-Iterator-Versionen oben variiert die Leistung (d. H. Die beste) mit der Listengröße und der Fenstergröße. Ich mag dieses, weil es ein Zwei-Liner ist (es könnte ein Ein-Liner 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, aber nicht, wenn es sich um einen Iterator handelt. Wenn es sich um einen Iterator handelt, wird derselbe Iterator unter den islice-Aufrufen geteilt (aber nicht abgehackt), und dies bricht die Dinge schwer. 

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 eine weitere Version für die Bücher. Anstatt einen Iterator zu kopieren und dann viele Male zu kopieren, erstellt diese Version paarweise Kopien jedes Iterators, während wir die Startposition nach vorne verschieben. Somit liefert der Iterator t sowohl den "vollständigen" Iterator mit dem Startpunkt bei t als auch die Basis für die Erstellung 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)
9
MrDrFenner

Um zu zeigen, wie Sie itertools - Rezepte kombinieren können, erweitere ich das pairwise - Rezept mit dem so direkt wie möglich in das window - Rezept consume Rezept:

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 Rezept window ist dasselbe wie für pairwise, es ersetzt nur das einzelne Element "consume" auf dem zweiten tee - Iterator, wobei die Consumes auf n - 1 Iteratoren. Die Verwendung von consume anstelle des Wrappings jedes Iterators in islice ist geringfügig schneller (für ausreichend große Iterables), da Sie den Wrapping-Overhead von islice nur während der Phase consume bezahlen , nicht während des Extrahierens der einzelnen Fenstered-Werte (also begrenzt durch n, nicht durch die Anzahl der Elemente in iterable).

In Bezug auf die Leistung ist dies im Vergleich zu einigen anderen Lösungen ziemlich gut (und besser als jede andere Lösung, die ich bei der Skalierung getestet habe). Getestet auf Python 3.5.0, Linux x86-64, mit ipython%timeit - Magie.

irgendwie ist es die deque - Lösung , optimiert auf Leistung/Korrektheit, indem islice anstelle eines hausgemachten Generatorausdrucks verwendet und die resultierende Länge getestet wird, sodass keine Ergebnisse erzielt werden Wenn die Iterationsrate kürzer als das Fenster ist, und die maxlen der deque -Position anstelle des Schlüsselworts übergeben wird (dies ist ein überraschender Unterschied für kleinere 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 vorherige angepasste Artall-Lösung, jedoch mit jedem yield win In yield Tuple(win) geändert, sodass das Speichern der Ergebnisse vom Generator funktioniert, ohne dass alle gespeicherten Ergebnisse wirklich eine Ansicht des neuesten Ergebnisses sind (alle anderen sinnvollen Lösungen) sind in diesem Szenario sicher) und fügen der Funktionsdefinition Tuple=tuple hinzu, um die Verwendung von Tuple von B in LEGB in 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

Wie consume, jedoch inline else für consume, um Funktionsaufrufe zu vermeiden, und n is None - Test, um die Laufzeit zu verringern, insbesondere für kleine Eingaben, bei denen der Einrichtungsaufwand hoch ist ein bedeutungsvoller Teil der Arbeit:

>>> %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 von pairwise, die tee mit dem Standardargument 2 wiederholt verwendet, um verschachtelte tee - Objekte zu erstellen, sodass ein gegebener Iterator nur einmal erweitert wird, nicht unabhängig immer häufiger konsumiert, ähnlich wie MrDrFenners Antwort bei allen Tests nicht inliniert consume und langsamer als inliniert consume Aus Gründen der Kürze wurden diese Ergebnisse weggelassen.

Wie Sie sehen , wenn Sie sich nicht für die Möglichkeit interessieren, dass der Anrufer Ergebnisse speichern muss, gewinnt meine optimierte Version der kindall-Lösung die meiste Zeit, außer in der "großen Iterationsdatei". kleine Fenstergröße case " (wobei inline consume gewinnt); Es verschlechtert sich schnell, wenn die iterative Größe zunimmt, während es sich mit zunehmender Fenstergröße überhaupt nicht verschlechtert (jede andere Lösung verschlechtert sich langsamer, wenn die iterative Größe zunimmt, aber auch, wenn die Fenstergröße zunimmt). Es kann sogar für den Fall "need tuples" angepasst werden, indem map(Tuple, ...) eingebunden wird, was etwas langsamer abläuft als das Einfügen der Tupel in die Funktion, aber es ist trivial (dauert 1-5% länger) und lässt Sie behalten die Flexibilität, schneller zu laufen, wenn Sie es tolerieren können, wiederholt denselben Wert zurückzugeben.

Wenn Sie die Sicherheit gegen das Einlagern von Retouren benötigen, gewinnt inline consume mit Ausnahme der kleinsten Eingabegrößen (mit nicht inline consume ist etwas langsamer, skaliert aber ähnlich). 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 das Protokoll lautete die angepasste Version von kindalls Lösung, die ich für yieldTuple verwendet habe:

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 von Tuple in der Funktionsdefinitionszeile und die Verwendung von Tuple in jedem yield, um die schnellere, aber weniger sichere Version zu erhalten.

8
ShadowRanger

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

Ich füge es hier ein, weil ich diese Methode noch nicht gesehen habe. Ich mache auch hier keine Angaben zu der verglichenen 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]
6
Gus

eine etwas modifizierte Version des Deque-Fensters, um ein echtes Rollfenster zu schaffen. Damit beginnt es, mit nur einem Element gefüllt zu werden, wächst dann auf die maximale Fenstergröße und verkleinert sich, wenn der linke Rand zu Ende geht:

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]
5
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] ]
4
heyyou482

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)]
3
Nikolay Frick

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) erhöht StopIteration, wenn die Sequenz beendet ist, und aus irgendeinem coolen Grund, der über mir hinausgeht, wird die Ertragsanweisung hier nicht angegeben und die Funktion kehrt zurück, wobei die verbleibenden Werte ignoriert werden, die kein vollständiges Fenster bilden.

Jedenfalls ist dies die Lösung mit den wenigsten Zeilen, deren einzige Anforderung ist, dass seq entweder __iter__ oder __getitem__ implementiert und nicht auf itertools oder collections neben der Lösung von dansalmo angewiesen ist :)

2
jameh

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. 

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

Machte dies für eine rollende Durchschnittsfunktion

2
yazdmich

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)]
1
Gram
#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]

"" "

1
FAYAZ

Wie wende ich folgendes an:

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)]
0
keocra
>>> 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]
0
dansalmo

Modifizierte DiPaolo-Antwort ermöglicht willkürliches Füllen und variable Schrittweite

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
0
shouldsee

Dies ist eine alte Frage, aber für die noch Interessierten gibt es eine großartige Implementierung eines Fensterschiebereglers, der Generatoren in this page (von Adrian Rosebrock) verwendet. 

Es ist eine Implementierung für OpenCV, die Sie jedoch problemlos für andere Zwecke verwenden können. Für die eifrigen werde ich den Code hier einfügen, aber um das 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 den .shape des Fensters überprüfen, wenn Sie den Generator durchlaufen, um diejenigen zu verwerfen, die Ihren Anforderungen nicht entsprechen

Prost

0
DarkCygnus