【Python 秘籍】保存最后 N 个元素

问题

我们希望在迭代或是其他形式的处理过程中对最后几项记录做一个有限的历史记录统计。

解决方案

保存有限的历史记录可以采用定长队列来解决。我们在之前已经介绍过如何使用 Python 创建一个简单队列:用 Python 实现队列
现在只要对这个队列类进行修改,新增一个指定长度的功能即可,修改后的类如下:

class Queue():
    def __init__(self, maxlen):
        self.items = []
        self.maxlen = maxlen
		
    def enqueue(self, item):
        if self.size() < self.maxlen:
            self.items.append(item)
        else:
            del(self.items[0])
            self.items.append(item)
			
    def dequeue(self):
        return self.items.pop(0)
		
    def isempty(self):
        return self.size() == 0
		
    def size(self):
        return len(self.items)

以下面的场景为例,对一系列文本行做简单的文本匹配操作,当发现有匹配时就输出当前的匹配行以及最后检查过的 N 行文本。

def search(lines, pattern, history=5):
    previous_lines = Queue(maxlen=history)
    for line in lines:
        if pattern in line:
            yield line, previous_lines
        previous_lines.enqueue(line)
		
if __name__ == '__main__':
    with open('somefile.txt') as f:
        for line, prevlines in search(f, 'python', 5):
            for pline in prevlines.items:
                print(pline, end='')
            print(line, end='')
            print('-'*20)

对于一个如下所示的 txt 文件:

1 hdhdhdvevjzj
2 jfjcidosbebshz
3 kjfbdbsjzjz
4 kkcjfbrohdbsjs
5 pdjdnsnajzj
6 jfjchfbrbsjzj
7 kkcjfnfbsjzk
8 dzhdhsbsjjz
9 jcjbdpythondhshzh
10 jcjpythonbdhdhxh
11 bbdbdhahz
12 pxjbdns

运行结果如下:

4 kkcjfbrohdbsjs
5 pdjdnsnajzj
6 jfjchfbrbsjzj
7 kkcjfnfbsjzk
8 dzhdhsbsjjz
9 jcjbdpythondhshzh
--------------------
5 pdjdnsnajzj
6 jfjchfbrbsjzj
7 kkcjfnfbsjzk
8 dzhdhsbsjjz
9 jcjbdpythondhshzh
10 jcjpythonbdhdhxh
--------------------

另外,如果要图方便,也可将上述自己实现的简单队列改用 collections.deque 来代替,只需导入模块 collections 中的 deque 类from collections import deque,并将previous_lines = Queue(maxlen=history)改为previous_lines = deque(maxlen=history),以及替换一下入队方法名(previous_lines.append(line))和获取队列元素(for pline in prevlines)即可。

高级用法

当需要实现双端队列,即可以在两端执行添加和弹出操作时,虽然也可以继续对自己实现的简单队列进行修改,但还是更提倡直接使用 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 的设计是基于 c 编写的,从 deque 两端添加或弹出元素的复杂度都是 O(1)。这和我们刚才基于列表构建的简单队列 Queue 不同,当从列表的头部插入或移除元素时,列表的复杂度为 O(N)。

其他用法请参考 Python 官方文档:https://docs.python.org/zh-cn/3/library/collections.html?highlight=deque#collections.deque