python - patron - Rueda o ventana deslizante iterador?

patron de diseño iterator c++

Question

Necesito una ventana móvil (también conocida como ventana deslizante) iterable sobre una secuencia / iterador / generador. La iteración predeterminada de Python se puede considerar 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]
"""

Answer 1

¡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) provoca StopIteration cuando la secuencia ha finalizado, y por alguna razón interesante que me supera, la declaración de rendimiento aquí lo exceptúa y la función vuelve, ignorando los valores sobrantes que no forman una ventana completa.

De todos modos, esta es la solución de menos líneas cuyo único requisito es que seq implemente __iter__ o __getitem__ y no confíe en itertools o collections además de la solución de @ dansalmo :)

Answer 2

¿Qué tal si usas 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)]

Answer 3

Aquí hay una generalización que agrega soporte para los parámetros step , fillvalue :

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

Obtiene en elementos de size trozos a la vez posiciones de step por iteración para fillvalue cada fragmento con valor de fillvalue si 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 obtener un ejemplo de caso de uso para el parámetro de step , consulte Procesamiento de un archivo .txt grande en python de manera eficiente .

Answer 4

El paquete de toolz tiene una función sliding_window .

Answer 5

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 usando generadores en this 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 .shape de la ventana al iterar el generador para descartar aquellos que no cumplen con sus requisitos.

Aclamaciones

Answer 6

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

Aquí hay una implementación optimizada basada en deque con el patrón 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, prácticamente supera a todo lo demás publicado aquí la mayor parte del tiempo, aunque la versión de tee de pillmuncher supera a los grandes iterables y las ventanas pequeñas. En ventanas más grandes, el deque se adelanta nuevamente en velocidad bruta.

El acceso a elementos individuales en el deque puede ser más rápido o más lento que con listas o tuplas. (Los elementos que están cerca del comienzo son más rápidos, o los elementos cerca del final si usa un índice negativo.) Puse una sum(w) en el cuerpo de mi ciclo; esto juega con la fuerza del deque (iterar de un elemento al siguiente es rápido, por lo que este bucle se ejecutó un 20% más rápido que el siguiente método más rápido, el de pillmuncher). Cuando lo cambié para buscar individualmente y agregar elementos en una ventana de diez, las tablas cambiaban y el método de tee era 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 el tee aún era un poco más rápido. En general, estimo 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.

Answer 7

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

Answer 8

Hay uno en una versión anterior de los documentos de Python con ejemplos de itertools :

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 usa itertools para un mayor efecto, imagino.

Answer 9

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]

Answer 10

Para mostrar cómo se pueden combinar itertools recetas de itertools , extiendo la receta por pairwise más directamente posible a la receta de la window con la receta de consume :

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 receta de la window es la misma que para el pairwise , simplemente reemplaza el elemento único "consumir" en el segundo iterador tee -ed con el consumo progresivamente creciente en n - 1 iteradores. Usar consume lugar de envolver cada iterador en islice es marginalmente más rápido (para iterables suficientemente grandes) ya que solo pagas el islice envoltura de islice durante la fase de consume , no durante el proceso de extracción de cada valor de ventana (por lo que está limitado por n , no la cantidad de elementos en iterable ).

En lo que respecta 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 escala). Probado en Python 3.5.0, Linux x86-64, usando ipython %timeit magic.

kindall es la solución de deque , ajustada para rendimiento / corrección mediante el uso de islice lugar de una expresión de generador laminados en el hogar y prueba la longitud resultante para que no arroje resultados cuando el iterable es más corto que la ventana, así como para pasar el maxlen de deque posicionalmente en lugar de por palabra clave (hace una diferencia sorprendente para las 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 kindall adaptada anterior, pero con cada yield win cambiada para yield tuple(win) almacenando los resultados del generador sin que todos los resultados almacenados sean realmente una vista del resultado más reciente (todas las demás soluciones razonables son seguras en este escenario) y agregando tuple=tuple a la definición de la función para mover el uso de la tuple desde B en LEGB a 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

solución basada en el consume 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

Lo mismo que consume , pero incluir else caso de consume para evitar la llamada a la función y n is None prueba para reducir el tiempo de ejecución, especialmente para las 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: una variante en pairwise que usa tee con el argumento predeterminado de 2 repetidamente para hacer objetos en tee anidados, por lo que cualquier iterador dado solo avanza una vez, no se consume independientemente un número creciente de veces, similar a la respuesta de MrDrFenner es similar a Consumo no en línea y más lento que el consume en línea en todas las pruebas, por lo que he omitido los resultados por brevedad.

Como puede ver, si no le importa la posibilidad de que la persona que llama necesite almacenar los resultados, mi versión optimizada de la solución de kindall gana la mayor parte del tiempo, excepto en el "caso grande e iterable de tamaño de ventana pequeña" (donde el consume línea gana); 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 (todas las demás soluciones se degradan más lentamente para incrementos de tamaño iterables, pero también se degradan por el tamaño de la ventana). Incluso se puede adaptar para el caso de "necesitar tuplas" envolviéndolo en el map(tuple, ...) , que se ejecuta un poco más lento que poner el tupling en la función, pero es trivial (tarda 1-5% más) y le permite mantener la flexibilidad de correr más rápido cuando puede tolerar repetidamente el mismo valor.

Si necesita seguridad para evitar que se registren devoluciones, los consumos dentro de línea ganan en todos excepto en los tamaños de entrada más pequeños (con el consume no en línea siendo un poco más lento pero escalando de manera similar). La solución basada en deque y 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 mal a medida que el iterable se alarga.

Para el registro, la versión adaptada de la solución de Kindall que yield las tuple que utilicé 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)

Elimine el almacenamiento en caché de la tuple en la línea de definición de función y el uso de tuple en cada yield para obtener la versión más rápida pero menos segura.

Answer 11

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.

Answer 12

Solo una contribución rápida.

Dado que los documentos de python actuales no tienen "ventana" en los ejemplos de la herramienta de iteración (es decir, en la parte inferior de http://docs.python.org/library/itertools.html ), aquí hay un fragmento basado en el código de mero 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 corte, cada uno con un punto de inicio un punto más adelante. Luego, creamos todos juntos. Tenga en cuenta que esta función devuelve un generador (no es directamente un generador).

Al igual que las versiones del elemento anexo y del iterador avanzado, el rendimiento (es decir, cuál es el mejor) varía con el tamaño de la lista y el tamaño de la ventana. Me gusta este porque es un juego de dos líneas (podría ser de una sola línea, pero prefiero los conceptos de nomenclatura).

Resulta que el código anterior es incorrecto . Funciona si el parámetro pasado a iterable es una secuencia, pero no si es un iterador. Si es un iterador, se comparte el mismo iterador (pero no el 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 varias veces, esta versión hace copias en pares de cada iterador a medida que movemos la posición de inicio hacia adelante. Por lo tanto, el iterador t proporciona el iterador "completo" con el punto de inicio en t y 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)

Answer 13

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

Lo incluyo aquí porque aún no veo este método utilizado. Nuevamente, no afirmo nada sobre su desempeño 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]

Answer 14

una versión ligeramente modificada de la ventana de deque, para que sea una verdadera ventana móvil. Para que comience a poblarse con un solo elemento, luego crece hasta su tamaño de ventana máximo, y luego se reduce a medida que el 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]

Answer 15

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

Answer 16

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

Answer 17

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 media móvil