Python 中的 deque?是一個(gè)低級(jí)別的、高度優(yōu)化的雙端隊(duì)列，對(duì)于實(shí)現(xiàn)優(yōu)雅、高效的Pythonic 隊(duì)列和堆棧很有用，它們是計(jì)算中最常見的列表式數(shù)據(jù)類型。

本文中，云朵君將和大家一起學(xué)習(xí)如下：

• 開始使用deque
• 有效地彈出和追加元素
• 訪問deque中的任意元素
• 用deque構(gòu)建高效隊(duì)列

開始使用Deque

向 Python 列表的右端追加元素和彈出元素的操作，一般非常高效。如果用大 O 表示時(shí)間復(fù)雜性，那么可以說它們是?O(1)。而當(dāng) Python 需要重新分配內(nèi)存來增加底層列表以接受新的元素時(shí)，這些操作就會(huì)變慢，時(shí)間復(fù)雜度可能變成?O(n)。

此外，在 Python 列表的左端追加和彈出元素的操作，也是非常低效的，時(shí)間復(fù)雜度為O(n)。

由于列表提供了?.append()?和?.pop()?這兩種操作，它們可以作為堆棧和隊(duì)列使用。而列表的左右端追加和彈出操作的性能問題會(huì)大大影響應(yīng)用程序的整體性能。

Python 的 deque 是早在 Python 2.4 中添加到 collections 模塊的第一個(gè)數(shù)據(jù)類型。這個(gè)數(shù)據(jù)類型是專門為克服 Python list 中的?.append()和?.pop()?的效率問題而設(shè)計(jì)的。

Deques是類似于序列的數(shù)據(jù)類型，被設(shè)計(jì)為堆棧和隊(duì)列的一般化，它們?cè)跀?shù)據(jù)結(jié)構(gòu)的兩端支持高效的內(nèi)存和快速的追加和彈出操作。

在 deque 對(duì)象兩端的追加和彈出操作是穩(wěn)定的，而且同樣有效，因?yàn)?deque 是作為雙鏈接列表實(shí)現(xiàn)。此外，deque 上的追加和彈出操作也是線程安全的和內(nèi)存高效的。這些特性使得 deque 在Python中創(chuàng)建自定義棧和隊(duì)列時(shí)特別有用。

如果需要保存最后看到的元素列表，也可以使用 deque，因?yàn)榭梢韵拗?deque 的最大長(zhǎng)度。如果我們這樣做了，那么一旦 deque 滿了，當(dāng)我們?cè)诹硪欢颂砑有碌脑貢r(shí)，它會(huì)自動(dòng)丟棄一端的元素。

下面是 deque 的主要特點(diǎn)的總結(jié)：

• 存儲(chǔ)任何數(shù)據(jù)類型的元素
• 是可變數(shù)據(jù)類型
• 支持帶in操作符的成員操作
• 支持索引，比如a_deque[i]
• 不支持切片，比如a_deque[0:2]
• 支持對(duì)序列和可迭代對(duì)象進(jìn)行操作的內(nèi)置函數(shù)，如?len() ，sorted() ，reversed()?等
• 不支持inplace?排序
• 支持正常迭代和反向迭代
• 支持使用pickle
• 確保在兩端快速、內(nèi)存高效和線程安全的彈出和追加操作

創(chuàng)建 deque 實(shí)例比較簡(jiǎn)單。只需要從 collection 中導(dǎo)入 deque，然后用一個(gè)可選的迭代器作為參數(shù)來調(diào)用它。

>>> from collections import deque

>>> # 創(chuàng)建一個(gè)空的 deque
>>> deque()
deque([])

>>> # 使用不同的迭代器來創(chuàng)建 deque
>>> deque((1, 2, 3, 4))
deque([1, 2, 3, 4])

>>> deque([1, 2, 3, 4])
deque([1, 2, 3, 4])

>>> deque(range(1, 5))
deque([1, 2, 3, 4])

>>> deque("abcd")
deque(['a', 'b', 'c', 'd'])

>>> numbers = {"one": 1, "two": 2, "three": 3, "four": 4}
>>> deque(numbers.keys())
deque(['one', 'two', 'three', 'four'])

>>> deque(numbers.values())
deque([1, 2, 3, 4])

>>> deque(numbers.items())
deque([('one', 1), ('two', 2), ('three', 3), ('four', 4)])

如果實(shí)例化 deque 時(shí)沒有提供 iterable 作為參數(shù)，那么會(huì)得到一個(gè)空的 deque。如果提供并輸入 iterable ，那么 deque 會(huì)用它的數(shù)據(jù)初始化新實(shí)例。初始化使用 deque.append() 從左到右進(jìn)行。

Deque 初始化器需要以下兩個(gè)可選參數(shù)。

• iterable一個(gè)提供初始化數(shù)據(jù)的迭代器。
• maxlen一個(gè)整數(shù)，指定deque的最大長(zhǎng)度。

如前所述，如果不提供一個(gè) iterable ，那么你會(huì)得到一個(gè)空的 deque。如果給 maxlen 提供一個(gè)值，那么你的 deque 只會(huì)存儲(chǔ)最多的 maxlen 項(xiàng)。

最后，還可以使用無序的可迭代對(duì)象，如 collections 來初始化 deque。在這些情況下，不會(huì)有最終 deque 中元素的預(yù)定義順序。

有效地彈出和追加元素

Deque 和 List 之間最重要的區(qū)別是，前者可以在序列的兩端進(jìn)行有效的追加和彈出操作。Deque 類實(shí)現(xiàn)了專門的 .popleft() 和 .appendleft() 方法，直接對(duì)序列的左端進(jìn)行操作。

>>> from collections import deque

>>> numbers = deque([1, 2, 3, 4])
>>> numbers.popleft()
1
>>> numbers.popleft()
2
>>> numbers
deque([3, 4])

>>> numbers.appendleft(2)
>>> numbers.appendleft(1)
>>> numbers
deque([1, 2, 3, 4])

在這里，使用 .popleft() 和 .appendleft() 來分別彈出和增加 numbers的左端值。這些方法是針對(duì)deque的設(shè)計(jì)的，而 list 沒有這樣的方法。

Deque也提供了像list一樣的 .append() 和 .pop() 方法來對(duì)序列的右端進(jìn)行操作。然而，.pop() 的行為是不同的。

>>> from collections import deque

>>> numbers = deque([1, 2, 3, 4])
>>> numbers.pop()
4

>>> numbers.pop(0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: pop() takes no arguments (1 given)

在這里，.pop() 刪除并返回 deque 容器中的最后一個(gè)元素。該方法不接受索引作為參數(shù)，因此不能使用它從 deque 中刪除任意項(xiàng)。只能使用它來刪除并返回最右邊的項(xiàng)。

我們認(rèn)為 deque 是一個(gè)雙鏈表。因此，給定 deque 容器中的每一項(xiàng)都保存著序列中上下一項(xiàng)的引用(指針)。

雙鏈表使得從兩端添加和彈出元素的操作變得簡(jiǎn)單而高效，因?yàn)橹挥兄羔樞枰拢虼?，這兩個(gè)操作具有相似的性能，均為O(1)。它們?cè)谛阅芊矫嬉彩强深A(yù)測(cè)的，因?yàn)椴恍枰匦路峙鋬?nèi)存和移動(dòng)現(xiàn)有項(xiàng)來接受新項(xiàng)。

從常規(guī) Python 列表的左端追加和彈出元素需要移動(dòng)所有元素，這最終是一個(gè) O(n) 操作。此外，將元素添加到列表的右端通常需要Python重新分配內(nèi)存，并將當(dāng)前項(xiàng)復(fù)制到新的內(nèi)存位置，之后，它可以添加新項(xiàng)。這個(gè)過程需要更長(zhǎng)的時(shí)間來完成，并且追加操作從 O(1)傳遞到 O(n)。

考慮以下關(guān)于在序列左端添加項(xiàng)的性能測(cè)試，deque vs list。

# time_append.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = []
a_deque = deque()

def average_time(func, times):
total = 0.0
for i in range(times):
start = perf_counter()
func(i)
total += (perf_counter() - start) * 1e9
return total / times

list_time = average_time(lambda i: a_list.insert(0, i), TIMES)
deque_time = average_time(lambda i: a_deque.appendleft(i), TIMES)
gain = list_time / deque_time

print(f"list.insert(){list_time:.6} ns")
print(f"deque.appendleft() {deque_time:.6} ns({gain:.6}x faster)")

在這個(gè)腳本中，average_time() 計(jì)算了執(zhí)行一個(gè)給定次數(shù)的函數(shù)（func）的平均時(shí)間。如果我們?cè)诿钚兄羞\(yùn)行該腳本，那么我們會(huì)得到以下輸出。

$ python time_append.py
list.insert()3735.08 ns
deque.appendleft() 238.889 ns(15.6352x faster)

在這個(gè)例子中，deque 上的 .appendleft() 要比 list 上的 .insert() 快幾倍。注意 deque.appendleft() 執(zhí)行時(shí)間是常量O(1)。但列表左端的 list.insert() 執(zhí)行時(shí)間取決于要處理的項(xiàng)的數(shù)量O(n)。

在這個(gè)例子中，如果增加 TIMES 的值，那么 list.insert() 會(huì)有更高的時(shí)間測(cè)量值，而 deque.appendleft() 會(huì)得到穩(wěn)定(常數(shù))的結(jié)果。如果對(duì) deque 和 list 的 pop 操作進(jìn)行類似的性能測(cè)試，那么可以展開下面的練習(xí)塊。

Exercise：測(cè)試 deque.popleft() 與 list.pop(0) 的性能

可以將上面的腳本修改為時(shí)間deque.popleft()與list.pop(0)操作并估計(jì)它們的性能。

Solution：測(cè)試 deque.popleft() 與 list.pop(0) 的性能

# time_pop.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = [1] * TIMES
a_deque = deque(a_list)

def average_time(func, times):
total = 0.0
for _ in range(times):
start = perf_counter()
func()
total += (perf_counter() - start) * 1e9
return total / times

list_time = average_time(lambda: a_list.pop(0), TIMES)
deque_time = average_time(lambda: a_deque.popleft(), TIMES)
gain = list_time / deque_time

print(f"list.pop(0) {list_time:.6} ns")
print(f"deque.popleft() {deque_time:.6} ns({gain:.6}x faster)")

list.pop(0) 2002.08 ns
deque.popleft() 326.454 ns(6.13282x faster)

同樣，它deque比list從底層序列的左端刪除元素要快。
嘗試更改TIMES的值，看看會(huì)發(fā)生什么

Deque 數(shù)據(jù)類型的設(shè)計(jì)是為了保證在序列的兩端進(jìn)行有效的追加和彈出操作。它是處理需要在 Python 中實(shí)現(xiàn)隊(duì)列和堆棧數(shù)據(jù)結(jié)構(gòu)的問題的理想選擇。

訪問Deque中的任意元素

Python 的 deque 返回可變的序列，其工作方式與列表相當(dāng)類似。除了可以有效地從其末端追加和彈出元素外，deque 還提供了一組類似列表的方法和其他類似序列的操作，以處理任意位置的元素。下面是其中的一些。

我們可以使用這些方法和技術(shù)來處理 deque 對(duì)象內(nèi)部任何位置的元素。下面是如何做到這一點(diǎn)的。

>>> from collections import deque
>>> letters = deque("abde")
>>> letters.insert(2, "c")
>>> letters
deque(['a', 'b', 'c', 'd', 'e'])

>>> letters.remove("d")
>>> letters
deque(['a', 'b', 'c', 'e'])

>>> letters[1]
'b'

>>> del letters[2]
>>> letters
deque(['a', 'b', 'e'])

在這里，首先將"c"插入到位置 2的letters中。然后使用 .remove() 從deque容器中移除"d"。Deque 還允許索引來訪問元素，在這里使用它來訪問索引1處的b。最后，你可以使用 del 關(guān)鍵字從 deque 中刪除任何存在的項(xiàng)。請(qǐng)注意， .remove() 允許按值刪除項(xiàng)，而del則按索引刪除項(xiàng)。

盡管 deque 對(duì)象支持索引，但它們不支持切片，即不能像常規(guī)列表一樣使用切片語法， [start:stop:step] 從現(xiàn)有的 deque 中提?。?/p>

>>> from collections import deque
>>> numbers = deque([1, 2, 3, 4, 5])
>>> numbers[1:3]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: sequence index must be integer, not 'slice'

Deque支持索引，卻不支持分片。通常來說在一個(gè)鏈表上執(zhí)行切片非常低效。

雖然 deque 與 list 非常相似，但 list 是基于數(shù)組的，而 deque 是基于雙鏈表的。

Deque 基于雙鏈表，在訪問、插入和刪除任意元素都是無效操作。如果需要執(zhí)行這些操作，則解釋器必須在deque中進(jìn)行迭代，直到找到想要的元素。因而他們的時(shí)間復(fù)雜度是O(n)而不是O(1)。

下面演示了在處理任意元素時(shí) deques 和 list 的行為。

# time_random_access.py

from collections import deque
from time import perf_counter

TIMES = 10_000
a_list = [1] * TIMES
a_deque = deque(a_list)

def average_time(func, times):
total = 0.0
for _ in range(times):
start = perf_counter()
func()
total += (perf_counter() - start) * 1e6
return total / times

def time_it(sequence):
middle = len(sequence) // 2
sequence.insert(middle, "middle")
sequence[middle]
sequence.remove("middle")
del sequence[middle]

list_time = average_time(lambda: time_it(a_list), TIMES)
deque_time = average_time(lambda: time_it(a_deque), TIMES)
gain = deque_time / list_time

print(f"list{list_time:.6} μs ({gain:.6}x faster)")
print(f"deque {deque_time:.6} μs")

這個(gè)腳本對(duì)插入、刪除和訪問一個(gè) deque 和一個(gè) list 中間的元素進(jìn)行計(jì)時(shí)。如果運(yùn)行這個(gè)腳本，得到如下所示的輸出:

$ python time_random_access.py
list63.8658 μs (1.44517x faster)
deque 92.2968 μs

Deque并不像列表那樣是隨機(jī)訪問的數(shù)據(jù)結(jié)構(gòu)。因此，從 deque 的中間訪問元素的效率要比在列表上做同樣的事情低。這說明 deque 并不總是比列表更有效率。

Python 的 deque 對(duì)序列兩端的操作進(jìn)行了優(yōu)化，所以它們?cè)谶@方面一直比 list 好。另一方面，列表更適合于隨機(jī)訪問和固定長(zhǎng)度的操作。下面是 deque 和 list 在性能上的一些區(qū)別。

對(duì)于列表，當(dāng)解釋器需要擴(kuò)大列表以接受新項(xiàng)時(shí)，.append()的性能優(yōu)勢(shì)受到內(nèi)存重新分配的影響而被降低。此操作需要將所有當(dāng)前項(xiàng)復(fù)制到新的內(nèi)存位置，這將極大地影響性能。

此總結(jié)可以幫助我們?yōu)槭诸^的問題選擇適當(dāng)?shù)臄?shù)據(jù)類型。但是，在從列表切換到 deque 之前，一定要對(duì)代碼進(jìn)行剖析，它們都有各自的性能優(yōu)勢(shì)。

用Deque構(gòu)建高效隊(duì)列

Deque 是一個(gè)雙端隊(duì)列，提供了堆棧和隊(duì)列的泛化。在本節(jié)中，我們將一起學(xué)習(xí)如何使用deque以優(yōu)雅、高效和Pythonic的方式在底層實(shí)現(xiàn)我們自己的隊(duì)列抽象數(shù)據(jù)類型（ADT）。

注意： 在 Python 標(biāo)準(zhǔn)庫中，queue 模塊實(shí)現(xiàn)了多生產(chǎn)者、多消費(fèi)者的隊(duì)列，可以在多個(gè)線程之間安全地交換信息。

如果你正在處理隊(duì)列，那么最好使用那些高級(jí)抽象而不是 deque ，除非你正在實(shí)現(xiàn)自己的數(shù)據(jù)結(jié)構(gòu)。

隊(duì)列是元素的collections，可以通過在一端添加元素和從另一端刪除元素來修改隊(duì)列。

隊(duì)列 以先入先出（FIFO）的方式管理元素，像一個(gè)管道一樣工作，在管道的一端推入新元素，并從另一端彈出舊元素。向隊(duì)列的一端添加一個(gè)元素稱為 enqueue 操作；從另一端刪除一個(gè)元素稱為 dequeue。

為了更好地理解隊(duì)列，以餐廳為例，餐館里有很多人在排隊(duì)等著點(diǎn)餐。通常情況下，后來的人將排在隊(duì)列的末端。一旦有了空桌子，排在隊(duì)伍開頭的人就會(huì)離開隊(duì)伍進(jìn)去用餐。

下面演示了使用一個(gè)原始的deque對(duì)象來模擬這個(gè)過程。

>>> from collections import deque

>>> customers = deque()

>>> # People arriving
>>> customers.append("Jane")
>>> customers.append("John")
>>> customers.append("Linda")

>>> customers
deque(['Jane', 'John', 'Linda'])

>>> # People getting tables
>>> customers.popleft()
'Jane'
>>> customers.popleft()
'John'
>>> customers.popleft()
'Linda'

>>> # No people in the queue
>>> customers.popleft()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: pop from an empty deque

首先創(chuàng)建一個(gè)空的 deque 對(duì)象來表示到達(dá)餐廳的人的隊(duì)列。person排隊(duì)放入隊(duì)列，可以使用.append()，將單個(gè)條目添加到右端。要從隊(duì)列中取出一個(gè)person，可以使用.popleft() ，刪除并返回deque容器左側(cè)的各個(gè)條目。

用隊(duì)列模擬工作，然而，由于deque是一個(gè)泛化，它的API]不匹配常規(guī)的隊(duì)列API。例如，不是.enqueue()，而是.append()。還有.popleft() 而不是.dequeue()。此外，deque 還提供了其他一些可能不符合特定需求的操作。

我們可以創(chuàng)建具有特定功能的自定義隊(duì)列類。可以在內(nèi)部使用 deque 來存儲(chǔ)數(shù)據(jù)，并在自定義隊(duì)列中提供所需的功能。我們可以把它看作是適配器設(shè)計(jì)模式的一個(gè)實(shí)現(xiàn)，在這個(gè)模式中，把 deque 的接口轉(zhuǎn)換成看起來更像隊(duì)列接口的東西。

例如，需要一個(gè)自定義的隊(duì)列抽象數(shù)據(jù)類型，提供以下功能。

• 排列元素
• 去排隊(duì)的元素
• 返回隊(duì)列的長(zhǎng)度
• 支持成員資格測(cè)試
• 支持正常和反向迭代
• 提供一個(gè)方便用戶的字符串表示法

此時(shí)可以寫一個(gè)Queue類。

# custom_queue.py

from collections import deque

class Queue:
def __init__(self):
self._items = deque()

def enqueue(self, item):
self._items.append(item)

def dequeue(self):
try:
return self._items.popleft()
except IndexError:
raise IndexError("dequeue from an empty queue") from None

def __len__(self):
return len(self._items)

def __contains__(self, item):
return item in self._items

def __iter__(self):
yield from self._items

def __reversed__(self):
yield from reversed(self._items)

def __repr__(self):
return f"Queue({list(self._items)})"

._items 是一個(gè) deque 對(duì)象，可以存儲(chǔ)和操作隊(duì)列中的元素。Queue使用 deque.append() 實(shí)現(xiàn)了 .enqueue()，將元素添加到隊(duì)列的末端。還用 deque.popleft() 實(shí)現(xiàn)了 .dequeue()，以有效地從隊(duì)列的開頭刪除元素。

支持以下特殊方法

理想情況下，.__repr__()返回一個(gè)字符串，代表一個(gè)有效的 Python 表達(dá)式?？梢杂眠@個(gè)表達(dá)式以相同的值重新創(chuàng)建這個(gè)對(duì)象。

然而，在上面的例子中，目的是使用方法的返回值在 interactive shell 上優(yōu)雅地顯示對(duì)象?？梢酝ㄟ^接受初始化可迭代對(duì)象作為.__init__() 的參數(shù)并從中構(gòu)建實(shí)例，從而從這個(gè)特定的字符串表示形式構(gòu)建 Queue 實(shí)例。

有了這些補(bǔ)充，Queue 類就完成了。要在我們的代碼中使用這個(gè)類，我們可以做如下事情。

>>> from custom_queue import Queue
>>> numbers = Queue()
>>> numbers
Queue([])

>>> # Enqueue items
>>> for number in range(1, 5):
... numbers.enqueue(number)
...
>>> numbers
Queue([1, 2, 3, 4])

>>> # Support len()
>>> len(numbers)
4

>>> # Support membership tests
>>> 2 in numbers
True
>>> 10 in numbers
False

>>> # Normal iteration
>>> for number in numbers:
... print(f"Number: {number}")
...
1
2
3
4

總結(jié)

隊(duì)列和堆棧是編程中常用的?抽象數(shù)據(jù)類型。它們通常需要在底層數(shù)據(jù)結(jié)構(gòu)的兩端進(jìn)行有效的?pop?和?append?操作。Python 的 collections 模塊提供了一種叫做 deque 的數(shù)據(jù)類型，它是專門為兩端的快速和節(jié)省內(nèi)存的追加和彈出操作而設(shè)計(jì)的。

有了deque，我們可以用優(yōu)雅、高效和Pythonic的方式在低層次上編寫我們自己的隊(duì)列和堆棧。

總結(jié)下本文所學(xué)內(nèi)容：

• 如何在代碼中創(chuàng)建和使用Python的deque
• 如何有效地從deque的兩端追加和彈出項(xiàng)目
• 如何使用deque來構(gòu)建高效的隊(duì)列和堆棧
• 什么時(shí)候值得使用deque而不是list

以上是Python中的Deque: 實(shí)現(xiàn)高效的隊(duì)列和堆棧的詳細(xì)內(nèi)容。更多信息請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！