關(guān)于隊列的一波風騷操作

如何創(chuàng)建一個固定長度的隊列

比如，我需要創(chuàng)建一個列表，無論我怎么往里面添加元素，但是列表內(nèi)的元素終止保留 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])

當然，你可以使用普通列表來實現(xiàn)，比如

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]

但是普通列表中元素都是有自己對應(yīng)的索引號的，特別是當從一個列表的起始位置或者中間位置去添加或者刪除元素時，其他元素的位置都要進行移動，以對應(yīng)合適的索引號。這樣效率是很低的。

deque(maxlen=N) 構(gòu)造函數(shù)會新建一個固定大小的隊列。當新的元素加入并 且這個隊列已滿的時候，最老的元素會自動被移除掉。他是 c 實現(xiàn)的，運行效率更快一些。

可以利用這個特點來對某些記錄只保留最后 N 條。比如在一個文件中搜索一個關(guān)鍵字，但是我只想要保留最后的 5 條數(shù)據(jù)。

可以這么寫:

from collections import deque


# 定義一個搜索關(guān)鍵字的函數(shù)
def search_keyword(lines, pattern, history=5):
    """
    搜索關(guān)鍵字的生成器函數(shù)
    :param lines: 含有多行內(nèi)容的可迭代對象
    :param pattern: 要搜索的關(guān)鍵字
    :param history: 保留的含有關(guān)鍵字的條目數(shù)
    :return:
    """
    # 創(chuàng)建只能容納 5 個元素的隊列
    previous_lines = deque(maxlen=history)

    for line in lines:

        # 判斷每行是否含有目標關(guān)鍵字
        if pattern in line:
            # 當每次匹配成后就把此行添加到隊列中，
            # 并且返回這個隊列，以便稍后打印里面的
            # 元素時可以看到其中數(shù)量的變化
            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)

示例文件內(nèi)容：

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() 傳遞參數(shù)，會創(chuàng)建一個無限大小的隊列，你可以在隊列的兩端執(zhí)行添 加和彈出元素的操作。

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])

它有個響當當?shù)拿峙?雙端隊列, 在隊列兩端插入或刪除元素時間復(fù)雜度都是 O(1) ，而在列表的開頭插入或刪除元 素的時間復(fù)雜度為 O(N) 。

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

我改如何從一個集合中獲得最大或者最小的 N 個元素呢?

其實， heapq 模塊有兩個函數(shù): 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]

這兩方法，還可以接收一個關(guān)鍵字參數(shù):key, 它的值應(yīng)該是一個可調(diào)用對象，可調(diào)用對象一個值，對每個元素進行對比的時候，會以這個值進行比較

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'])

關(guān)于排序的幾點建議:

1. 當要查找的元素個數(shù)相對比較小的時候，函數(shù) nlargest() 和 nsmallest() 是很 合適的。
2. 如果你僅僅想查找唯一的最小或最大(N=1)的元素的話，那么使用 min() 和 max() 函數(shù)會更快些。
3. 類似的，如果 N 的大小和集合大小接近的時候，通常先排序這個 集合然后再使用切片操作會更快點(sorted(items)[:N] 或者是 sorted(items)[-N:] )。

需要在正確場合使用函數(shù) nlargest() 和 nsmallest() 才能發(fā)揮它們的優(yōu)勢(如果 N 快接近集合大小了，那么使用排序操作會更好些)。

未完，待更新...