滑动窗口迭代器还是滚动窗口？

Question

我需要一个可以在一个序列、迭代器或生成器上进行滑动窗口（也叫滚动窗口）操作的可迭代对象。默认的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的特定情况（也就是在一个序列中迭代相邻的、重叠的成对元素），可以参考如何从列表中迭代重叠的（当前，下一）成对值？。}

Answer 1

我喜欢使用 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)

它的输出是：

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

Answer 2

这个情况很适合用 collections.deque，因为你基本上是在做一个先进先出（FIFO）的操作，也就是一头添加，另一头移除。不过，即使你用 list，也不应该切片两次；你应该直接用 pop(0) 从列表中移除元素，然后用 append() 添加新项。

这里有一个基于 deque 的优化实现，参考了你的原始代码：

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

在我的测试中，它大多数时候都比这里其他的实现快，虽然 pillmuncher 的 tee 版本在处理大数据和小窗口时更快。在处理大窗口时，deque 又在速度上领先了。

在 deque 中访问单个项目的速度可能比列表或元组快，也可能慢。（如果你用负索引，靠近末尾的项目会更快；如果是靠近开头的项目则会更快。）我在循环中放了一个 sum(w)；这利用了 deque 的优势（从一个项目迭代到下一个项目很快，所以这个循环比下一个最快的方法，pillmuncher 的方法快了整整 20%）。当我改成逐个查找并添加十个项目时，情况就反转了，tee 方法快了 20%。我通过对最后五个项使用负索引恢复了一些速度，但 tee 还是稍微快一点。总体来说，我估计这两种方法对于大多数用途来说都足够快，如果你需要更高的性能，可以进行性能分析，选择最适合你的那种。

Answer 3

在旧版的Python文档中，有一些关于 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

文档中的例子更简洁，而且我想它更有效地利用了 itertools。

---

如果你的迭代器是一个简单的列表或元组，那么用指定的窗口大小来滑动遍历它的一个简单方法是：

seq = [0, 1, 2, 3, 4, 5]
window_size = 3

for i in range(len(seq) - window_size + 1):
    print(seq[i: i + window_size])

输出：

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