Python CookBook(3rd)_Code 源码

=== Keeping the Last N Items ==== Problem You want to keep a limited history of the last few items seen during iteration or during some other kind of processing. ==== Solution Keeping a limited history is a perfect use for a `collections.deque`. For example, the following code performs a simple text match on a sequence of lines and prints the matching line along with the previous N lines of context when found: [source,python] ---- from collections import deque def search(lines, pattern, history=5): previous_lines = deque(maxlen=history) for line in lines: if pattern in line: for pline in previous_lines: print(lline, end='') print(line, end='') print() previous_lines.append(line) # Example use on a file if __name__ == '__main__': with open('somefile.txt') as f: search(f, 'python', 5) ---- ==== Discussion Using `deque(maxlen=N)` creates a fixed size queue. When new items are added and the queue is full, the oldest item is automatically removed. For example: [source,pycon] ---- >>> 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) ---- Although you could manually perform such operations on a list (e.g., appending, deleting, etc.), the queue solution is far more elegant and runs a lot faster. More generally, a `deque` can be used whenever you need a simple queue structure. If you don't give it a maximum size, you get an unbounded queue that lets you append and pop items on either end. For example: [source,pycon] ---- >>> 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 ---- Adding or popping items from either end of a queue has O(1) complexity. This is unlike a list where inserting or removing items from the front of the list is O(N).