Python 中的 deque?是一個低階的、高度最佳化的雙端佇列，對於實現(xiàn)優(yōu)雅、高效的Pythonic 佇列和堆疊很有用，它們是計算中最常見的列表式資料類型。

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

• 開始使用deque
• 有效地彈出和追加元素
• 訪問deque中的任意元素
• 用deque建立高效能佇列

開始使用Deque

向Python 清單的右端追加元素和彈出元素的操作，一般非常有效率。如果用大 O 表示時間複雜性，那麼可以說它們是?O(1)。而當(dāng) Python 需要重新分配記憶體來增加底層列表以接受新的元素時，這些操作就會變慢，時間複雜度可能變成?O(n)。

此外，在 Python 清單的左端追加和彈出元素的操作，也是非常低效的，時間複雜度為O(n)。

由於清單提供了?.append()?和?.pop()?這兩個操作，它們可以作為堆疊和佇列使用。而清單的左右端追加和彈出操作的效能問題會大大影響應(yīng)用程式的整體效能。

Python 的 deque 是早在 Python 2.4 中加入到 collections 模組的第一個資料類型。這個資料型別是專門為克服 Python list 中的?.append()和?.pop()?的效率問題而設(shè)計的。

Deques是類似序列的資料類型，被設(shè)計為堆疊和佇列的一般化，它們在資料結(jié)構(gòu)的兩端支援高效的記憶體和快速的追加和彈出操作。

在 deque 物件兩端的追加和彈出操作是穩(wěn)定的，而且同樣有效，因為 deque 是作為雙連結(jié)列表實現(xiàn)。此外，deque 上的追加和彈出操作也是線程安全的和記憶體高效的。這些特性使得 deque 在Python中建立自訂堆疊和佇列時特別有用。

如果需要儲存最後看到的元素列表，也可以使用 deque，因為可以限制 deque 的最大長度。如果我們這樣做了，那麼一旦 deque 滿了，當(dāng)我們在另一端添加新的元素時，它會自動丟棄一端的元素。

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

• 儲存任何資料類型的元素
• 是可變資料類型
• 支援帶in運(yùn)算子的成員運(yùn)算
• 支援索引，例如a_deque[i]
• 不支援切片，例如a_deque[0:2]
• 支援對序列和可迭代物件進(jìn)行操作的內(nèi)建函數(shù)，如?len() ，sorted() ，reversed()?等
• 不支援inplace?排序
• 支援正常迭代和反向迭代
• #支援使用pickle
• 確保在兩端快速、記憶體高效和線程安全的彈出和追加操作

#建立deque 實例比較簡單。只需要從 collection 匯入 deque，然後用一個可選的迭代器作為參數(shù)來呼叫它。

>>> from collections import deque

>>> # 創(chuàng)建一個空的 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)])

如果實例化 deque 時沒有提供 iterable 作為參數(shù)，那麼就會得到一個空的 deque。如果提供並輸入 iterable ，那麼 deque 會用它的資料初始化新實例。初始化使用?deque.append()?由左至右進(jìn)行。

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

• iterable一個提供初始化資料的迭代器。
• maxlen一個整數(shù)，指定deque的最大長度。

如前所述，如果不提供一個 iterable ，那麼你會得到一個空的 deque。如果提供 maxlen 一個值，那麼你的 deque 只會儲存最多的 maxlen 項。

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

有效地彈出和追加元素

Deque 和 List 之間最重要的區(qū)別是，前者可以在序列的兩端進(jìn)行有效的追加和彈出操作。 Deque 類別實作了專門的?.popleft()?和?.appendleft()?方法，直接對序列的左端進(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的左端值。這些方法是針對deque的設(shè)計的，而 list 沒有這樣的方法。

Deque也提供了像list一樣的?.append()?和?.pop()?方法來操作序列的右端。然而，.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 容器中的最後一個元素。此方法不接受索引作為參數(shù)，因此不能使用它從 deque 中刪除任意項。只能使用它來刪除並傳回最右邊的項目。

我們認(rèn)為 deque 是一個雙鍊錶。因此，給定 deque 容器中的每一項都保存著序列中上下一項的引用(指標(biāo))。

雙鍊錶使得從兩端添加和彈出元素的操作變得簡單而高效，因為只有指針需要更新，因此，這兩個操作具有相似的性能，均為O(1)。它們在效能方面也是可預(yù)測的，因為不需要重新分配記憶體和移動現(xiàn)有項來接受新項。

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

考慮以下關(guān)于在序列左端添加項的性能測試，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)")

在這個腳本中，average_time() 計算了執(zhí)行一個給定次數(shù)的函數(shù)（func）的平均時間。如果我們在命令行中運(yùn)行該腳本，那么我們會得到以下輸出。

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

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

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

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

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

Solution：測試 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的值，看看會發(fā)生什么

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

訪問Deque中的任意元素

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

選項	描述
.insert(i, value)	在索引為i的deque容器中插入一個名為value的元素。
.remove (value)	刪除第一個出現(xiàn)的 value ，如果 value 不存在則引發(fā)ValueError
a_deque[i]	從一個deque容器中檢索索引為 i 的項。
del a_deque[i]	#從deque容器移除索引為 i 的項目。

#

我們可以使用這些方法和技術(shù)來處理 deque 對象內(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 中刪除任何存在的項。請注意， .remove() 允許按值刪除項，而del則按索引刪除項。

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

>>> 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支持索引，卻不支持分片。通常來說在一個鏈表上執(zhí)行切片非常低效。

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

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

下面演示了在處理任意元素時 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")

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

$ 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 對序列兩端的操作進(jìn)行了優(yōu)化，所以它們在這方面一直比 list 好。另一方面，列表更適合于隨機(jī)訪問和固定長度的操作。下面是 deque 和 list 在性能上的一些區(qū)別。

運(yùn)作	??deque??	??list??
通過索引訪問任意的元素	O(n)	O(1)
在左端彈出和追加元素	O(1)	O(n)
#在右端彈出和追加元素	##O (1)	O(1) 重新指派

############### #######O(n)############O(n)################

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

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

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

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

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

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

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

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

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

下面演示了使用一個原始的deque對象來模擬這個過程。

>>> 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)建一個空的 deque 對象來表示到達(dá)餐廳的人的隊列。person排隊放入隊列，可以使用.append()，將單個條目添加到右端。要從隊列中取出一個person，可以使用.popleft() ，刪除并返回deque容器左側(cè)的各個條目。

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

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

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

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

此時可以寫一個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 是一個 deque 對象，可以存儲和操作隊列中的元素。Queue使用 deque.append() 實現(xiàn)了 .enqueue()，將元素添加到隊列的末端。還用 deque.popleft() 實現(xiàn)了 .dequeue()，以有效地從隊列的開頭刪除元素。

支持以下特殊方法

##常規(guī)迭代#反向迭代字串表示形式

Method	Support
??.__len__ ()??	長度的?#len()
#.__contains__( )	帶有in的成員測試
##常規(guī)迭代
.__reversed__()
	# .__repr__()

############

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

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

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

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

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

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

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

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

以上是Python中的Deque: 實作高效的佇列與堆疊的詳細(xì)內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！