J'ai besoin d'une fenêtre déroulante (aka fenêtre glissante) itérable sur une séquence / itérateur / générateur. L'itération Python par défaut peut être considérée comme un cas spécial, où la longueur de la fenêtre est 1. J'utilise actuellement le code suivant. Quelqu'un a-t-il une méthode plus pythonique, moins verbeuse ou plus efficace pour faire cela?

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

Il y en a un dans une ancienne version de la documentation Python avec des itertoolsexemples :

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

Celui de la documentation est un peu plus succinct et utilise itertoolsplus efficacement j'imagine.

Cela semble fait sur mesure pour un collections.dequepuisque vous avez essentiellement un FIFO (ajouter à une extrémité, supprimer de l'autre). Cependant, même si vous utilisez un, listvous ne devriez pas trancher deux fois; au lieu de cela, vous devriez probablement juste à pop(0)partir de la liste et append()du nouvel élément.

Voici une implémentation optimisée basée sur deque calquée sur votre 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

Dans mes tests, il bat facilement tout le reste affiché ici la plupart du temps, bien que la teeversion de pillmuncher le bat pour les grandes itérables et les petites fenêtres. Sur les fenêtres plus grandes, le dequetire à nouveau en vitesse brute.

L'accès aux éléments individuels dans le dequepeut être plus rapide ou plus lent qu'avec des listes ou des tuples. (Les éléments proches du début sont plus rapides, ou les éléments proches de la fin si vous utilisez un index négatif.) J'ai mis un sum(w)dans le corps de ma boucle; cela joue à la force du deque (l'itération d'un élément à l'autre est rapide, donc cette boucle s'est déroulée 20% plus vite que la méthode la plus rapide suivante, pillmuncher). Lorsque je l'ai changé pour rechercher et ajouter des éléments individuellement dans une fenêtre de dix, les tables ont tourné et la teeméthode était 20% plus rapide. J'ai pu récupérer de la vitesse en utilisant des indices négatifs pour les cinq derniers termes de l'addition, mais j'étais teeencore un peu plus rapide. Dans l'ensemble, je dirais que l'un ou l'autre est très rapide pour la plupart des utilisations et si vous avez besoin d'un peu plus de performances, profilez et choisissez celui qui fonctionne le mieux.

J'aime 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)

donne:

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

Voici une généralisation qui ajoute le support pour step, fillvalueparamètres:

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

Il donne des sizeéléments par blocs à la fois, des steppositions de roulement par itération en complétant chaque bloc fillvaluesi nécessaire. Exemple pour 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 * *]

Pour obtenir un exemple de cas d'utilisation du stepparamètre, consultez Traitement efficace d'un fichier .txt volumineux en python .

Il existe une bibliothèque qui fait exactement ce dont vous avez besoin:

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

Juste une contribution rapide.

Étant donné que les documents python actuels n'ont pas de "fenêtre" dans les exemples d'itertool (c'est-à-dire au bas de http://docs.python.org/library/itertools.html ), voici un extrait de code basé sur le code du groupeur qui est l'un des exemples donnés:

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

Fondamentalement, nous créons une série d'itérateurs découpés, chacun avec un point de départ un point plus loin. Ensuite, nous les compressons ensemble. Notez que cette fonction renvoie un générateur (ce n'est pas directement un générateur en lui-même).

Tout comme les versions d'élément d'ajout et d'itérateur avancé ci-dessus, les performances (c'est-à-dire, ce qui est le meilleur) varient en fonction de la taille de la liste et de la taille de la fenêtre. J'aime celui-ci car il s'agit d'un bi-liner (ça pourrait être un one-liner, mais je préfère nommer les concepts).

Il s'avère que le code ci-dessus est incorrect . Cela fonctionne si le paramètre est passé à iterable est une séquence mais pas s'il s'agit d'un itérateur. S'il s'agit d'un itérateur, le même itérateur est partagé (mais pas tee'd) entre les appels islice et cela casse gravement les choses.

Voici un code fixe:

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)

Aussi, une autre version pour les livres. Au lieu de copier un itérateur puis de faire avancer les copies plusieurs fois, cette version fait des copies par paires de chaque itérateur lorsque nous avançons la position de départ. Ainsi, l'itérateur t fournit à la fois l'itérateur "complet" avec le point de départ en t et aussi la base pour créer l'itérateur 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)

Juste pour montrer comment vous pouvez combiner des itertoolsrecettes , je prolonge la pairwiserecette aussi directement que possible dans la windowrecette en utilisant la consumerecette:

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)

La windowrecette est la même que pour pairwise, elle remplace simplement l'élément unique «consommer» sur le deuxième teeitérateur avec des consommations progressivement croissantes sur les n - 1itérateurs. Utiliser consumeau lieu d'encapsuler chaque itérateur dans isliceest légèrement plus rapide (pour des itérables suffisamment volumineux) puisque vous ne payez les islicefrais généraux d'encapsulation que pendant la consumephase, pas pendant le processus d'extraction de chaque valeur fenêtrée (il est donc limité par n, pas par le nombre d'éléments dans iterable).

En termes de performances, par rapport à certaines autres solutions, c'est plutôt bon (et meilleur que toutes les autres solutions que j'ai testées à mesure qu'elle évolue). Testé sur Python 3.5.0, Linux x86-64, en utilisantipython %timeit magie.

kindall est la dequesolution , ajustée pour la performance / l'exactitude en utilisant isliceau lieu d'une expression de générateur lancée à la maison et en testant la longueur résultante afin qu'elle ne donne pas de résultats lorsque l'itérable est plus court que la fenêtre, ainsi que le passage maxlende la dequeposition au lieu de par mot-clé (fait une différence surprenante pour les entrées plus petites):

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

Identique à la solution kindall adaptée précédente, mais avec chacune des yield winmodifications apportées, le yield tuple(win)stockage des résultats du générateur fonctionne sans que tous les résultats stockés ne soient vraiment une vue du résultat le plus récent (toutes les autres solutions raisonnables sont sûres dans ce scénario), et en ajoutant tuple=tupleà la définition de la fonction pour déplacer l'utilisation de tuplede l' Bentrée LEGBvers la 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

consumesolution à base illustrée ci-dessus:

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

Identique à consume, mais dans le elsecas de consumepour éviter l'appel de fonction et de n is Nonetester pour réduire le temps d'exécution, en particulier pour les petites entrées où la surcharge de configuration est une partie significative du travail:

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

(Note latérale: une variante pairwisequi utilise teel'argument par défaut de 2 à plusieurs reprises pour créer des teeobjets imbriqués , de sorte que tout itérateur donné n'est avancé qu'une seule fois, pas consommé indépendamment un nombre croissant de fois, similaire à la réponse de MrDrFenner est similaire à non-inline consumeet plus lent que l'inline consumesur tous les tests, j'ai donc omis ces résultats par souci de concision).

Comme vous pouvez le voir, si vous ne vous souciez pas de la possibilité que l'appelant ait besoin de stocker les résultats, ma version optimisée de la solution de kindall l'emporte la plupart du temps, sauf dans le cas du "grand itérable, petite taille de fenêtre" (où l'inline consumegagne ); il se dégrade rapidement à mesure que la taille itérable augmente, sans se dégrader du tout à mesure que la taille de la fenêtre augmente (chaque solution sur deux se dégrade plus lentement lorsque la taille itérable augmente, mais se dégrade également lorsque la taille de la fenêtre augmente). Il peut même être adapté pour le cas "besoin de tuples" en enveloppant map(tuple, ...), ce qui est un peu plus lent que de mettre le tupling dans la fonction, mais c'est trivial (prend 1-5% de plus) et vous permet de garder la flexibilité de courir plus vite lorsque vous pouvez tolérer le renvoi répété de la même valeur.

Si vous avez besoin de sécurité contre le stockage des retours, les entrées en ligne l' consumeemportent sur toutes les tailles d'entrée sauf les plus petites (la non-ligne consumeétant légèrement plus lente mais mise à l'échelle de la même manière). ledeque solution basée sur le & tupling ne gagne que pour les plus petites entrées, en raison de coûts de configuration plus faibles, et le gain est faible; il se dégrade gravement à mesure que l'itérable s'allonge.

Pour mémoire, la version adaptée de la solution de Kindall qui yields tuplede j'étais:

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)

Supprimez la mise tupleen cache de dans la ligne de définition de fonction et l'utilisation de tupledans chacune yieldpour obtenir la version la plus rapide mais la moins sûre.

J'utilise le code suivant comme une simple fenêtre coulissante qui utilise des générateurs pour augmenter considérablement la lisibilité. Sa vitesse a jusqu'à présent été suffisante pour une utilisation dans l'analyse de séquence bioinformatique d'après mon expérience.

Je l'inclus ici car je n'ai pas encore vu cette méthode utilisée. Encore une fois, je ne fais aucune déclaration sur ses performances comparées.

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

une version légèrement modifiée de la fenêtre deque, pour en faire une véritable fenêtre déroulante. Pour qu'il commence à être rempli avec un seul élément, puis augmente jusqu'à sa taille de fenêtre maximale, puis se rétrécit à mesure que son bord gauche approche de la fin:

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

cela donne

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

Fait ceci pour une fonction moyenne mobile

pourquoi pas

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

Il est documenté dans la doc Python . Vous pouvez facilement l'étendre à une fenêtre plus large.

Plusieurs itérateurs!

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)déclenche StopIterationlorsque la séquence est terminée, et pour une raison intéressante qui me dépasse, l'instruction yield l'excepte et la fonction retourne, ignorant les valeurs restantes qui ne forment pas une fenêtre complète.

Quoi qu'il en soit, c'est la solution des moindres lignes dont la seule exigence est d' seqimplémenter __iter__ou __getitem__et ne repose pas sur itertoolsou en collectionsplus de la solution de @ dansalmo :)

Faisons paresseux!

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]

"" "

J'ai testé quelques solutions et celle que j'ai trouvée et j'ai trouvé celle que j'avais proposée pour être la plus rapide, alors j'ai pensé la partager.

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]

Que diriez-vous d'utiliser ce qui suit:

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)

Production:

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

C'est une vieille question, mais pour ceux qui sont toujours intéressés, il existe une excellente implémentation d'un curseur de fenêtre utilisant des générateurs dans ce page (par Adrian Rosebrock).

C'est une implémentation pour OpenCV mais vous pouvez facilement l'utiliser à d'autres fins. Pour les plus désireux, je vais coller le code ici mais pour mieux le comprendre, je recommande de visiter la page d'origine.

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

Astuce: vous pouvez vérifier la .shapede la fenêtre lors de l'itération du générateur pour éliminer ceux qui ne répondent pas à vos besoins

À votre santé

Modification de la réponse de DiPaolo pour permettre un remplissage arbitraire et une taille de pas variable

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

voici une seule ligne. Je l'ai chronométré et il est compatible avec les performances de la réponse supérieure et s'améliore progressivement avec un seq plus grand de 20% plus lent avec len (seq) = 20 et 7% plus lent avec len (seq) = 10000

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

Essayer ma part, simple, une doublure, façon pythonique en utilisant islice. Mais, peut ne pas être d'une efficacité optimale.

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

Explication: Créez une fenêtre en utilisant islice de window_size et répétez cette opération en utilisant map sur tout le tableau.

Fonction optimisée pour les données de fenêtre glissante dans le 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)