Necesito una ventana móvil (también conocida como ventana deslizante) iterable sobre una secuencia / iterador / generador. La iteración predeterminada de Python puede considerarse un caso especial, donde la longitud de la ventana es 1. Actualmente estoy usando el siguiente código. ¿Alguien tiene un método más pitónico, menos detallado o más eficiente para hacer esto?

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

Hay uno en una versión antigua de los documentos de Python con itertoolsejemplos :

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

El de los documentos es un poco más sucinto y se usa itertoolscon mayor efecto, imagino.

Esto parece hecho a medida para un, collections.dequeya que esencialmente tiene un FIFO (agregar a un extremo, eliminar del otro). Sin embargo, incluso si usa un listno debería cortar dos veces; en su lugar, probablemente debería solo pop(0)de la lista y append()el nuevo elemento.

Aquí hay una implementación optimizada basada en deque modelada después de su 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

En mis pruebas, supera fácilmente todo lo demás publicado aquí la mayor parte del tiempo, aunque la teeversión de Pillmuncher lo supera para iterables grandes y ventanas pequeñas. En ventanas más grandes, la dequefuerza se adelanta nuevamente a toda velocidad.

El acceso a elementos individuales en el dequepuede ser más rápido o más lento que con listas o tuplas. (Los elementos cerca del principio son más rápidos, o los elementos cerca del final si usa un índice negativo). Puse un sum(w)en el cuerpo de mi bucle; esto juega con la fuerza de la deque (la iteración de un elemento al siguiente es rápida, por lo que este ciclo se ejecutó un 20% más rápido que el siguiente método más rápido, pillmuncher's). Cuando lo cambié para buscar individualmente y agregar elementos en una ventana de diez, las tablas cambiaron y el teemétodo fue un 20% más rápido. Pude recuperar algo de velocidad usando índices negativos para los últimos cinco términos en la adición, pero teeaún así fue un poco más rápido. En general, estimaría que cualquiera de los dos es bastante rápido para la mayoría de los usos y si necesita un poco más de rendimiento, perfile y elija el que mejor funcione.

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

da:

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

Aquí está una generalización que añade soporte para step, fillvalueparámetros:

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

Produce en trozos sizeelementos a la vez, stepcolocando posiciones por iteración rellenando cada trozo con fillvaluesi es necesario. Ejemplo para 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 * *]

Para ver un ejemplo de caso de uso para el stepparámetro, vea Procesar un archivo .txt grande en python de manera eficiente .

Hay una biblioteca que hace exactamente lo que necesita:

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

Solo una contribución rápida.

Dado que los documentos actuales de Python no tienen "ventana" en los ejemplos de itertool (es decir, en la parte inferior de http://docs.python.org/library/itertools.html ), aquí hay un fragmento basado en el código para el agrupador que Es uno de los ejemplos dados:

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

Básicamente, creamos una serie de iteradores en rodajas, cada uno con un punto de partida un punto más adelante. Luego, los juntamos. Tenga en cuenta que esta función devuelve un generador (no es directamente un generador en sí).

Al igual que las versiones anteriores de elemento anexador e iterador avanzado, el rendimiento (es decir, el mejor) varía según el tamaño de la lista y el tamaño de la ventana. Me gusta este porque es de dos líneas (podría ser de una línea, pero prefiero nombrar conceptos).

Resulta que el código anterior está mal . Funciona si el parámetro pasó a iterable es una secuencia pero no si es un iterador. Si se trata de un iterador, el mismo iterador se comparte (pero no está en tee) entre las llamadas de islice y esto rompe las cosas mal.

Aquí hay un código fijo:

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)

Además, una versión más para los libros. En lugar de copiar un iterador y luego avanzar copias muchas veces, esta versión hace copias en pares de cada iterador a medida que avanzamos la posición inicial. Por lo tanto, el iterador t proporciona tanto el iterador "completo" con un punto de partida en t como también la base para crear el iterador 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)

Solo para mostrar cómo puede combinar itertoolsrecetas , estoy extendiendo la pairwisereceta lo más directamente posible a la windowreceta usando la consumereceta:

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 windowreceta es la misma que para pairwise, simplemente reemplaza el elemento individual "consumo" en el teeiterador de segunda capa con consumos progresivamente crecientes en los n - 1iteradores. Usar en consumelugar de ajustar cada iterador islicees marginalmente más rápido (para iterables lo suficientemente grandes) ya que solo paga la islicesobrecarga de ajuste durante la consumefase, no durante el proceso de extracción de cada valor editado en ventana (por lo que está limitado n, no por el número de elementos en iterable)

En cuanto al rendimiento, en comparación con algunas otras soluciones, esto es bastante bueno (y mejor que cualquiera de las otras soluciones que probé a medida que se escala). Probado en Python 3.5.0, Linux x86-64, usandoipython %timeit magia.

es la dequesolución , ajustada para el rendimiento / corrección mediante el uso islicede una expresión generadora en casa y probando la longitud resultante para que no produzca resultados cuando el iterable es más corto que la ventana, así como pasar el maxlende la dequeposición en lugar de por palabra clave (hace una diferencia sorprendente para entradas más pequeñas):

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

Igual que la solución adaptada adaptada anterior, pero con cada yield wincambio para yield tuple(win)que los resultados de almacenamiento del generador funcionen sin que todos los resultados almacenados sean realmente una vista del resultado más reciente (todas las otras soluciones razonables son seguras en este escenario) y se agregan tuple=tuplea la definición de la función para mover el uso de tuplede la Ben LEGBla 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

consumebasada en la solución que se muestra arriba:

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

Igual que consume, pero en el elsecaso de consumeevitar llamadas a funciones y n is Nonepruebas para reducir el tiempo de ejecución, particularmente para entradas pequeñas donde la sobrecarga de configuración es una parte significativa del trabajo:

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

(Nota al margen: una variante pairwiseque se usa teecon el argumento predeterminado de 2 repetidamente para hacer teeobjetos anidados , por lo que cualquier iterador dado solo se avanza una vez, no se consume independientemente un número creciente de veces, similar a la respuesta de MrDrFenner es similar a no en línea consumey más lento que el en líneaconsume en todas las pruebas, por lo que he omitido esos resultados por brevedad).

Como puede ver, si no le importa la posibilidad de que la persona que llama necesite almacenar resultados, mi versión optimizada de la solución de kindall gana la mayor parte del tiempo, excepto en el "caso de tamaño de ventana pequeño iterativo grande" (donde en línea consumegana ); se degrada rápidamente a medida que aumenta el tamaño iterable, mientras que no se degrada en absoluto a medida que aumenta el tamaño de la ventana (cualquier otra solución se degrada más lentamente cuando aumenta el tamaño iterable, pero también se degrada cuando aumenta el tamaño de la ventana). Incluso se puede adaptar para el caso de "necesidad de tuplas" envolviéndolo map(tuple, ...), que funciona un poco más lento que poner la tupla en la función, pero es trivial (toma 1-5% más tiempo) y le permite mantener la flexibilidad de correr más rápido cuando puede tolerar que se devuelva repetidamente el mismo valor.

Si necesita seguridad contra el retorno de las devoluciones almacenadas, las consumeganancias en línea se obtienen en todos los tamaños de entrada, excepto en los más pequeños (el no en línea consumees ligeramente más lento pero se escala de manera similar). La dequesolución basada en tupling gana solo para las entradas más pequeñas, debido a los menores costos de configuración, y la ganancia es pequeña; se degrada mucho a medida que el iterable se alarga.

Para el registro, la versión adaptada de la solución de kindall que yields tupleusé fue:

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)

Suelte el almacenamiento tupleen caché de la línea de definición de funciones y el uso de tupleen cada una yieldpara obtener la versión más rápida pero menos segura.

Utilizo el siguiente código como una simple ventana deslizante que usa generadores para aumentar drásticamente la legibilidad. Su velocidad hasta ahora ha sido suficiente para su uso en el análisis de secuencias de bioinformática en mi experiencia.

Lo incluyo aquí porque todavía no veía este método utilizado. Una vez más, no hago afirmaciones sobre su rendimiento comparado.

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

Una versión ligeramente modificada de la ventana de deque, para convertirla en una verdadera ventana móvil. Para que comience a llenarse con un solo elemento, luego crezca hasta su tamaño máximo de ventana y luego se encoja a medida que su borde izquierdo se acerca al final:

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

esto da

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

Hecho esto para una función promedio móvil

Por qué no

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

Está documentado en Python doc . Puede extenderlo fácilmente a una ventana más amplia.

Múltiples iteradores!

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)surge StopIterationcuando finaliza la secuencia, y por alguna razón genial que está más allá de mí, la declaración de rendimiento aquí la exceptúa y la función regresa, ignorando los valores sobrantes que no forman una ventana completa.

De todos modos, esta es la solución de líneas mínimas aún cuyo único requisito es seqimplementar __iter__o __getitem__no y no se basa en itertoolso collectionsademás de la solución de @ dansalmo :)

¡Hagámoslo perezoso!

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]

"" "

Probé algunas soluciones y encontré una que encontré como la más rápida, así que pensé en compartirla.

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]

¿Qué tal usar lo siguiente:

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)

Salida:

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

Esta es una vieja pregunta, pero para aquellos que todavía están interesados, hay una gran implementación de un control deslizante de ventana que utiliza generadores en este página (por Adrian Rosebrock).

Es una implementación para OpenCV, sin embargo, puede usarla fácilmente para cualquier otro propósito. Para los ansiosos, pegaré el código aquí, pero para entenderlo mejor, recomiendo visitar la página original.

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

Consejo: Puede verificar la .shapeventana al iterar el generador para descartar aquellos que no cumplan con sus requisitos

Salud

Se modificó la respuesta de DiPaolo para permitir un relleno arbitrario y un tamaño de paso 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

Aquí hay un trazador de líneas. Lo cronometré y es comparable al rendimiento de la respuesta principal y mejora progresivamente con una secuencia mayor de 20% más lento con len (seq) = 20 y 7% más lento con len (seq) = 10000

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

Intentando mi parte, simple, un trazador de líneas, forma pitónica usando islice. Pero, puede no ser óptimamente eficiente.

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

Explicación: Cree una ventana usando islice de window_size e itere esta operación usando map over all array.

Función optimizada para datos de ventana deslizante en aprendizaje profundo

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)