Python3 中关于队列的一波风骚操作

关于队列的一波风骚操作

如何创建一个固定长度的队列

比如，我需要创建一个列表，无论我怎么往里面添加元素，但是列表内的元素终止保留 5 个

看 collections.deque 如何大显身手

In [1]: from collections import deque

In [2]: five_list = deque(maxlen=5)

In [3]: [five_list.append(n) for n in range(20)]
Out[3]:
[None,
 None,
 ...
 
In [4]: five_list
Out[4]: deque([15, 16, 17, 18, 19])

当然，你可以使用普通列表来实现，比如

In [11]: li = []

In [11]: for n in range(12):
    ...:     li.append(n)
    ...:     if len(li) > 5:
    ...:         li.pop(0)
    ...:

In [12]: li
Out[12]: [7, 8, 9, 10, 11]

但是普通列表中元素都是有自己对应的索引号的，特别是当从一个列表的起始位置或者中间位置去添加或者删除元素时，其他元素的位置都要进行移动，以对应合适的索引号。这样效率是很低的。

deque(maxlen=N) 构造函数会新建一个固定大小的队列。当新的元素加入并 且这个队列已满的时候，最老的元素会自动被移除掉。他是 c 实现的，运行效率更快一些。

可以利用这个特点来对某些记录只保留最后 N 条。比如在一个文件中搜索一个关键字，但是我只想要保留最后的 5 条数据。

可以这么写:

from collections import deque


# 定义一个搜索关键字的函数
def search_keyword(lines, pattern, history=5):
    """
    搜索关键字的生成器函数
    :param lines: 含有多行内容的可迭代对象
    :param pattern: 要搜索的关键字
    :param history: 保留的含有关键字的条目数
    :return:
    """
    # 创建只能容纳 5 个元素的队列
    previous_lines = deque(maxlen=history)

    for line in lines:

        # 判断每行是否含有目标关键字
        if pattern in line:
            # 当每次匹配成后就把此行添加到队列中，
            # 并且返回这个队列，以便稍后打印里面的
            # 元素时可以看到其中数量的变化
            previous_lines.append(line)
            yield previous_lines


if __name__ == '__main__':
    with open(r'./some_file.txt') as f:
        for prevlines in search_keyword(f, '千锋云计算', 5):
            for pline in prevlines:
                print(pline, end='')
            print('\n', '-' * 20)

示例文件内容：

1 pakljsdf lkjlkjdf
2  西瓜甜
3  西瓜甜
4 pakljsdf lkjlkjdf
5  西瓜甜 千锋云计算
6  西瓜甜 千锋云计算pakljsdf lkjlkjdf
7  西瓜甜 千锋
8  西瓜甜 千锋pakljsdf lkjlkjdf
9  西瓜甜 千锋云计算
10  西瓜甜 千锋pakljsdf lkjlkjdf
12  西瓜甜 千锋云计算
13  杨哥团队 千锋pakljsdf lkjlkjdf
14  杨哥团队 千锋
15  杨哥团队 千锋pakljsdf lkjlkjdf
16  西瓜甜 千锋云计算
17  西瓜甜 千锋pakljsdf lkjlkjdf
18  西瓜甜 千锋云计算
19  杨哥团队 千锋pakljsdf lkjlkjdf
20  杨哥团队 千锋
21  杨哥团队 千锋pakljsdf lkjlkjdf

假如不给 deque() 传递参数，会创建一个无限大小的队列，你可以在队列的两端执行添 加和弹出元素的操作。

In [13]: q = deque()

In [14]: q.append(1)

In [15]: q.append(2)

In [16]: q
Out[16]: deque([1, 2])

In [17]: q.appendleft(3)

In [18]: q
Out[18]: deque([3, 1, 2])

In [19]: q.pop()
Out[19]: 2

In [20]: q.popleft()
Out[20]: 3

In [21]: q
Out[21]: deque([1])

它有个响当当的名字哦 双端队列, 在队列两端插入或删除元素时间复杂度都是 O(1) ，而在列表的开头插入或删除元 素的时间复杂度为 O(N) 。

---

查找最大或最小的 N 个元素

我改如何从一个集合中获得最大或者最小的 N 个元素呢?

其实， heapq 模块有两个函数: nlargest() 和 nsmallest() 可以完美解决这个问题。

In [22]: import heapq

In [23]: nums = [0, 6, 2, 25, 9, -4, 16, 20, 82, 76, 20]

In [24]: heapq.nlargest(3, nums)
Out[24]: [82, 76, 25]

In [25]: heapq.nsmallest(3, nums)
Out[25]: [-4, 0, 2]

这两方法，还可以接收一个关键字参数:key, 它的值应该是一个可调用对象，可调用对象一个值，对每个元素进行对比的时候，会以这个值进行比较

user_info = [
    {'name': 'shark', 'age': 18, 'deposit': 33},
    {'name': 'xiguatian', 'age': 19, 'deposit': 33.3},
    {'name': 'QF', 'age': 8, 'deposit': 109000000.00},
    {'name': 'Yangge', ' age': 35, 'deposit': 1000555},
    {'name': 'Yaoge', ' age': 45, 'deposit': 900555.31},
    {'name': 'Chaoge', ' age': 75, 'deposit': 990555.14}
]

# 按照 `deposit` 字段的值进行比较，取出屌丝的 `2` 个
silk = heapq.nsmallest(2, user_info, key=lambda item: item['deposit'])

# 按照 `deposit` 字段的值进行比较，取出最土豪的 `2` 个
local_tycoonheapq.nlargest(2, user_info, key=lambda item: item['deposit'])

关于排序的几点建议:

1. 当要查找的元素个数相对比较小的时候，函数 nlargest() 和 nsmallest() 是很 合适的。
2. 如果你仅仅想查找唯一的最小或最大(N=1)的元素的话，那么使用 min() 和 max() 函数会更快些。
3. 类似的，如果 N 的大小和集合大小接近的时候，通常先排序这个 集合然后再使用切片操作会更快点(sorted(items)[:N] 或者是 sorted(items)[-N:] )。

需要在正确场合使用函数 nlargest() 和 nsmallest() 才能发挥它们的优势(如果 N 快接近集合大小了，那么使用排序操作会更好些)。

未完，待更新...