Itérateur à fenêtre glissante ou roulante en Python

Question

J'ai besoin d'une fenêtre roulante (ou fenêtre coulissante) itérable sur une séquence/un itérateur/un générateur. L'itération Python par défaut peut être considérée comme un cas particulier, où la longueur de la fenêtre est de 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]
"""

Answer 1

Il y en a un dans une ancienne version de la documentation Python avec itertools exemples :

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

Celle de la documentation est un peu plus succincte et utilise itertools avec plus d'effet, j'imagine.

Answer 2

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

Voici une implémentation optimisée basée sur deque et inspirée de l'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 de loin tout ce qui a été posté ici la plupart du temps, bien que la version de pillmuncher tee l'emporte sur la version pour les grands itérables et les petites fenêtres. Sur les grands Windows, la version deque est de nouveau en tête en vitesse brute.

L'accès aux éléments individuels de la deque peut être plus rapide ou plus lente 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). Je mets un sum(w) dans le corps de ma boucle ; cela joue sur la force de la deque (itérer d'un élément à l'autre est rapide, donc cette boucle a fonctionné 20% plus vite que la méthode la plus rapide suivante, celle de pillmuncher). Lorsque je l'ai modifié pour rechercher et ajouter des éléments individuellement dans une fenêtre de dix, les choses se sont inversées et la méthode de deque s'est exécutée plus rapidement que celle de pillmuncher. tee était 20% plus rapide. J'ai pu récupérer un peu de vitesse en utilisant des index négatifs pour les cinq derniers termes de l'addition, mais tee était toujours un peu plus rapide. Dans l'ensemble, je dirais que l'un ou l'autre est suffisamment rapide pour la plupart des utilisations et si vous avez besoin d'un peu plus de performances, profilez et choisissez celui qui vous convient le mieux.

Answer 3

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]

Answer 4

Juste une petite contribution.

Étant donné que la documentation actuelle de Python ne mentionne pas le mot "window" dans les exemples d'itertool (c.-à-d. au bas de la page d'accueil d'itertool), nous avons décidé de ne pas utiliser le mot "window". http://docs.python.org/library/itertools.html ), voici un extrait basé sur le code de pour grouper 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)

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

Comme pour les versions appending-element et advancing-iterator ci-dessus, les performances (c'est-à-dire ce qui est le mieux) varient avec la taille de la liste et de la fenêtre. J'aime bien cette version parce qu'elle est en deux lignes (elle pourrait être en une ligne, mais je préfère nommer les concepts).

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

Voici un code corrigé :

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 d'avancer les copies plusieurs fois, cette version fait des copies par paire de chaque itérateur au fur et à mesure que nous avançons la position de départ. Ainsi, l'itérateur t fournit à la fois l'itérateur "complet" avec un point de départ à 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)

Answer 5

J'utilise le code suivant comme une simple fenêtre coulissante qui utilise des générateurs pour augmenter drastiquement la lisibilité. D'après mon expérience, sa vitesse est jusqu'à présent suffisante pour une utilisation en analyse de séquence bioinformatique.

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