1.3.留住最后N个元素.md

1.3.留住最后N个元素

问题

在某些迭代或者其他一些执行操作的时候，如何保留限制个数的历史记录？

解决方法

使用collection.deque是解决保留限制历史记录个数的完美解决方案，比如，下面这段代码就是查找一个简单文本中特定的字符串并保留前N句的示例：

from collections import deque
def search(lines, pattern, history=5):
    previous_lines = deque(maxlen=history)
    for line in lines:
        if pattern in line:
            yield line, previous_lines
        previous_lines.append(line)
# Example use on a file
if __name__ == '__main__':
    with open('somefile.txt') as f:
        for line, prevlines in search(f, 'python', 5):
            for pline in prevlines:
                print(pline, end='')
            print(line, end='')
            print('-'*20)

讨论

在编写搜索元素的代码时，通常都使用包含yield的Generators函数，这可以降低搜索过程。

使用deque(maxlen=N)创建一个固定大小的队列。当新元素加入后并且队列满了，最先加入的元素自动移除，举例：

>>> q = deque(maxlen=3)
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q
deque([1, 2, 3], maxlen=3)
>>> q.append(4)
>>> q
deque([2, 3, 4], maxlen=3)
>>> q.append(5)
>>> q
deque([3, 4, 5], maxlen=3)

同样，你也可以对list手动执行这些操作（e.g. appending，deleting，etc），使用queue的解决方法更加简介和高效。

一般的说，只要你需要一个简单队列结构都可以使用deque。如果你不想给定大小，你将得到一个可以让你append和pop元素的无界deque。例如：

>>> q = deque()
>>> q.append(1)
>>> q.append(2)
>>> q.append(3)
>>> q
deque([1, 2, 3])
>>> q.appendleft(4)
>>> q
deque([4, 1, 2, 3])
>>> q.pop()
3
>>> q
deque([4, 1, 2])>>> q.popleft()
4

从deque的开始或结尾add或者pop元素的圈复杂度是O(1)，然而list做同样操作的复杂度是O(N)。