Preciso de uma janela rotativa (também conhecida como janela deslizante) iterável em uma sequência / iterador / gerador. A iteração padrão do Python pode ser considerada um caso especial, onde o comprimento da janela é 1. Atualmente, estou usando o código a seguir. Alguém tem um método mais pitonico, menos detalhado ou mais eficiente para fazer isso?

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

Há um em uma versão antiga dos documentos Python com itertoolsexemplos :

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

O dos documentos é um pouco mais sucinto e usa itertoolscom maior efeito, imagino.

Isso parece feito sob medida para uma collections.dequevez que você basicamente possui um FIFO (adicione a uma extremidade, remova da outra). No entanto, mesmo se você usar um list, não deve fatiar duas vezes; em vez disso, você deve provavelmente apenas a pop(0)partir da lista e append()do novo item.

Aqui está uma implementação otimizada baseada em deque padronizada após o seu 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

Nos meus testes, ele supera facilmente tudo o que foi postado aqui a maior parte do tempo, embora a teeversão do pillmuncher o supere para iterables grandes e janelas pequenas. Em janelas maiores, a dequeforça avança novamente em velocidade bruta.

O acesso a itens individuais no dequepode ser mais rápido ou mais lento do que com listas ou tuplas. (Os itens próximos ao início são mais rápidos ou os itens próximos ao final, se você usar um índice negativo.) Coloquei um sum(w)no corpo do meu loop; isso é compatível com a força do deque (a iteração de um item para o próximo é rápida, portanto, esse loop é executado 20% mais rápido que o método mais rápido, o pillmuncher). Quando mudei para procurar individualmente e adicionar itens em uma janela de dez, as tabelas giraram e o teemétodo foi 20% mais rápido. Consegui recuperar alguma velocidade usando índices negativos nos últimos cinco termos da adição, mas teeainda era um pouco mais rápido. No geral, eu estimaria que qualquer um deles seja bastante rápido para a maioria dos usos e, se você precisar de um pouco mais de desempenho, crie um perfil e escolha o que funciona melhor.

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

dá:

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

Aqui está uma generalização que adiciona suporte 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))

Ele gera sizeitens em pedaços de cada vez, rolando stepposições por iteração preenchendo cada pedaço, fillvaluese necessário. Exemplo 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 um exemplo de caso de uso para o stepparâmetro, consulte Processando um arquivo .txt grande em python com eficiência .

Existe uma biblioteca que faz exatamente o que você precisa:

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

Apenas uma contribuição rápida.

Como os documentos python atuais não têm "janela" nos exemplos de itertool (por exemplo, na parte inferior de http://docs.python.org/library/itertools.html ), aqui está um trecho baseado no código do agrupador que é um dos exemplos dados:

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

Basicamente, criamos uma série de iteradores fatiados, cada um com um ponto de partida um ponto à frente. Depois, fechamos juntos. Observe que essa função retorna um gerador (não é diretamente um gerador em si).

Assim como as versões de elemento anexador e iterador avançado acima, o desempenho (ou seja, o melhor) varia com o tamanho da lista e o tamanho da janela. Gosto desta porque é uma linha dupla (pode ser uma linha única, mas prefiro nomear conceitos).

Acontece que o código acima está errado . Funciona se o parâmetro passado para iterável for uma sequência, mas não se for um iterador. Se for um iterador, o mesmo iterador é compartilhado (mas não é tee'd) entre as chamadas islice e isso interrompe muito as coisas.

Aqui está um código fixo:

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)

Além disso, mais uma versão para os livros. Em vez de copiar um iterador e avançar cópias várias vezes, esta versão faz cópias em pares de cada iterador à medida que avançamos a posição inicial. Portanto, o iterador t fornece ao iterador "completo" o ponto inicial em te também a base para a criação do 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)

Apenas para mostrar como você pode combinar itertoolsreceitas , estendo a pairwisereceita o mais diretamente possível de volta à windowreceita usando a consumereceita:

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)

A windowreceita é a mesma que para pairwise, apenas substitui o elemento único "consumir" no teeiterador secundário por um aumento progressivo do consumo nos n - 1iteradores. Usar em consumevez de agrupar cada iterador isliceé marginalmente mais rápido (para iteráveis ​​suficientemente grandes), pois você paga apenas a islicesobrecarga do agrupamento durante a consumefase, não durante o processo de extração de cada valor da janela (portanto, é limitado por n, não pelo número de itens em iterable)

Em termos de desempenho, comparado a outras soluções, isso é muito bom (e melhor do que qualquer outra solução que eu testei à medida). Testado em Python 3.5.0, Linux x86-64, usando ipython %timeitmagia.

kindall é a dequesolução , aprimorada em termos de desempenho / correção usando em islicevez de uma expressão de gerador rolada em casa e testando o comprimento resultante para que não produza resultados quando o iterável for mais curto que a janela, além de passar o maxlenda dequeposição em vez de por palavra-chave (faz uma diferença surpreendente para entradas menores):

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

O mesmo que a solução padrão adaptada anterior, mas com cada yield winalteração alterada para yield tuple(win)que o armazenamento de resultados do gerador funcione sem que todos os resultados armazenados sejam realmente uma visão do resultado mais recente (todas as outras soluções razoáveis ​​são seguras nesse cenário) e adicionando tuple=tupleà definição da função para mover uso de tupledo Bem LEGBao 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à base de água mostrada acima:

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

Mesmo que consume, mas inlining elsecaso consumeda chamada de função evitar e n is Noneteste para reduzir tempo de execução, especialmente para as pequenas entradas onde a sobrecarga de configuração é uma parte significativa do trabalho:

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

(Observação: uma variante pairwiseusada teecom o argumento padrão 2 repetidamente para criar teeobjetos aninhados , portanto, qualquer iterador específico é avançado apenas uma vez, não consumido independentemente um número crescente de vezes, semelhante à resposta de MrDrFenner é semelhante a não alinhado consumee mais lento que o descrito consumeem todos os testes, por isso omiti esses resultados por questões de brevidade).

Como você pode ver, se você não se importa com a possibilidade de o chamador precisar armazenar resultados, minha versão otimizada da solução da kindall ganha na maioria das vezes, exceto no "caso grande iterável e pequeno do tamanho da janela" (onde o inline consumevence ); é degradado rapidamente à medida que o tamanho iterável aumenta, sem degradar à medida que o tamanho da janela aumenta (todas as outras soluções degradam mais lentamente para o aumento do tamanho iterável, mas também degradam para o aumento do tamanho da janela). Pode até ser adaptado para o caso "precisar de tuplas", envolvendo map(tuple, ...), que é um pouco mais lento do que colocar a tupla na função, mas é trivial (leva 1-5% a mais) e permite manter a flexibilidade de executar mais rapidamente quando você pode tolerar retornar repetidamente o mesmo valor.

Se você precisar de segurança contra o armazenamento de retornos, o inline consumevence em todos os tamanhos de entrada, exceto os menores (com o não inline consumesendo um pouco mais lento, mas com escala semelhante). A dequesolução baseada em & tupling ganha apenas nos menores insumos, devido aos menores custos de instalação, e o ganho é pequeno; ele se degrada muito à medida que o iterável fica mais longo.

Para o registro, a versão adaptada da solução da Kindall que yields tuples que usei foi:

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)

Abandone o armazenamento tupleem cache na linha de definição de função e o uso de tupleem cada um yieldpara obter a versão mais rápida, mas menos segura.

Eu uso o código a seguir como uma simples janela deslizante que usa geradores para aumentar drasticamente a legibilidade. Até agora, sua velocidade tem sido suficiente para uso em análises de sequências de bioinformática.

Eu o incluo aqui porque ainda não vi esse método. Novamente, não faço reivindicações sobre seu desempenho 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] ]

uma versão ligeiramente modificada da janela deque, para torná-la uma verdadeira janela rolante. Para que ele comece a ser preenchido com apenas um elemento, aumente para o tamanho máximo da janela e diminua conforme a borda esquerda se aproxima do fim:

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

isto dá

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

Feito isso para uma função de média móvel

Por que não

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

Ele é documentado em Python doc . Você pode facilmente estendê-lo para uma janela maior.

Vários 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)aumenta StopIterationquando a sequência é concluída e, por algum motivo interessante que está além de mim, a instrução yield aqui a excede e a função retorna, ignorando os valores restantes que não formam uma janela completa.

Enfim, esta é a solução de menor número de linhas, mas cujo único requisito é que seqimplemente um __iter__ou outro __getitem__e não dependa da solução da @ dansalmo itertoolsou collectionsalém dela :)

Vamos torná-lo preguiçoso!

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]

"" "

Testei algumas soluções e uma que eu achei e achei a que eu achei mais rápida, então pensei em compartilhar.

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 tal usar o seguinte:

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)

Resultado:

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

Esta é uma pergunta antiga, mas para aqueles que ainda estão interessados, há uma ótima implementação de um controle deslizante de janela usando geradores nesta página (por Adrian Rosebrock).

É uma implementação para o OpenCV, mas você pode usá-lo facilmente para qualquer outro propósito. Para os mais ansiosos, colarei o código aqui, mas para entendê-lo melhor, recomendo visitar a 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]])

Dica: Você pode verificar a .shapejanela ao iterar o gerador para descartar aqueles que não atendem aos seus requisitos

Felicidades

Resposta do DiPaolo modificada para permitir preenchimento arbitrário e tamanho de etapa variável

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

aqui está um forro. Eu cronometrei e é compatível com o desempenho da resposta principal e melhora progressivamente com seq maior de 20% mais lento com len (seq) = 20 e 7% mais lento com len (seq) = 10000

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

Tentando a minha parte, de maneira simples, simples e python usando o islice. Mas, pode não ser idealmente 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]]

Explicação: Crie uma janela usando islice of window_size e itere esta operação usando o mapa em toda a matriz.

Função otimizada para deslizar dados da janela no 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)