我需要一个滚动窗口(又名滑动窗口)可迭代的序列/迭代器/生成器。(默认的Python迭代可以被认为是一种特殊情况,其中窗口长度为1。)我目前正在使用以下代码。我怎样才能做得更优雅和/或更有效?

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

对于window_size == 2的特定情况(即,在序列中迭代相邻的重叠对),请参见如何从列表中迭代重叠(当前,下一个)值对?


当前回答

deque窗口的一个轻微修改版本,使其成为一个真正的滚动窗口。因此,它开始只填充一个元素,然后增长到它的最大窗口大小,然后缩小,因为它的左边缘接近结束:

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

这给了

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

其他回答

多个迭代器!

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)在序列结束时引发StopIteration,出于一些我无法理解的很酷的原因,yield语句在这里除外它,函数返回,忽略没有形成完整窗口的剩余值。

无论如何,这是目前为止行数最少的解决方案,它唯一的要求是seq实现__iter__或__getitem__,并且除了@dansalmo的解决方案之外,不依赖于itertools或集合:)

我最终使用的解决方案(保持简单):

def sliding_window(items, size):
    return [items[start:end] for start, end
            in zip(range(0, len(items) - size + 1), range(size, len(items) + 1))]

不用说,项目序列需要是可切片的。使用索引并不理想,但考虑到其他选项,这似乎是最不坏的选择……这也可以很容易地更改为生成器:只需替换[…]和……

我喜欢t ():

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)

给:

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

toolz/cytoolz包有一个sliding_window函数。

>>> from cytoolz import sliding_window
>>> list(sliding_window(3, range(6))) # returns [(0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 5)]

只是一个简短的贡献。

由于当前的python文档在itertool示例中没有“window”(即,在http://docs.python.org/library/itertools.html的底部),这里有一个基于 石斑鱼的代码,这是给出的例子之一:

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

基本上,我们创建了一系列切片迭代器,每个迭代器的起点都在前面一个位置。然后,我们把它们拉在一起。注意,这个函数返回一个生成器(它本身不是直接的生成器)。

就像上面的appendingelement和advingiterator版本一样,性能(即,哪个是最好的)随列表大小和窗口大小而变化。我喜欢这个,因为它是一个两行代码(它也可以是一行代码,但我更喜欢命名概念)。

事实证明上面的代码是错误的。如果传递给iterable的参数是一个序列则有效,但如果它是一个迭代器则无效。如果它是一个迭代器,那么在islice调用之间共享相同的迭代器(但不是tee - d),这将严重破坏事情。

下面是一些固定的代码:

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)

另外,书里还有一个版本。这个版本不是复制一个迭代器,然后多次向前复制,而是在开始位置向前移动时成对复制每个迭代器。因此,迭代器t既提供了起点为t的“完整”迭代器,也提供了创建迭代器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)