建站
咨詢
售后
建站咨詢
新聞中心
Python 中的 deque 是一個低級別的、高度優(yōu)化的雙端隊(duì)列，對于實(shí)現(xiàn)優(yōu)雅、高效的Pythonic 隊(duì)列和堆棧很有用，它們是計(jì)算中最常見的列表式數(shù)據(jù)類型。
創(chuàng)新互聯(lián)建站專業(yè)為企業(yè)提供江州網(wǎng)站建設(shè)、江州做網(wǎng)站、江州網(wǎng)站設(shè)計(jì)、江州網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、江州企業(yè)網(wǎng)站模板建站服務(wù)，十余年江州做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。
本文中，云朵君將和大家一起學(xué)習(xí)如下：
- 開始使用deque
- 有效地彈出和追加元素
- 訪問deque中的任意元素
- 用deque構(gòu)建高效隊(duì)列
開始使用Deque
向 Python 列表的右端追加元素和彈出元素的操作，一般非常高效。如果用大 O 表示時(shí)間復(fù)雜性，那么可以說它們是 O(1)。而當(dāng) Python 需要重新分配內(nèi)存來增加底層列表以接受新的元素時(shí)，這些操作就會變慢，時(shí)間復(fù)雜度可能變成 O(n)。
此外，在 Python 列表的左端追加和彈出元素的操作，也是非常低效的，時(shí)間復(fù)雜度為O(n)。
由于列表提供了 .append() 和 .pop() 這兩種操作，它們可以作為堆棧和隊(duì)列使用。而列表的左右端追加和彈出操作的性能問題會大大影響應(yīng)用程序的整體性能。
Python 的 deque 是早在 Python 2.4 中添加到 collections 模塊的第一個數(shù)據(jù)類型。這個數(shù)據(jù)類型是專門為克服 Python list 中的 .append()和 .pop() 的效率問題而設(shè)計(jì)的。
Deques是類似于序列的數(shù)據(jù)類型，被設(shè)計(jì)為堆棧和隊(duì)列的一般化，它們在數(shù)據(jù)結(jié)構(gòu)的兩端支持高效的內(nèi)存和快速的追加和彈出操作。
在 deque 對象兩端的追加和彈出操作是穩(wěn)定的，而且同樣有效，因?yàn)?deque 是作為雙鏈接列表實(shí)現(xiàn)。此外，deque 上的追加和彈出操作也是線程安全的和內(nèi)存高效的。這些特性使得 deque 在Python中創(chuàng)建自定義棧和隊(duì)列時(shí)特別有用。
如果需要保存最后看到的元素列表，也可以使用 deque，因?yàn)榭梢韵拗?deque 的最大長度。如果我們這樣做了，那么一旦 deque 滿了，當(dāng)我們在另一端添加新的元素時(shí)，它會自動丟棄一端的元素。
下面是 deque 的主要特點(diǎn)的總結(jié)：
- 存儲任何數(shù)據(jù)類型的元素
- 是可變數(shù)據(jù)類型
- 支持帶in操作符的成員操作
- 支持索引，比如a_deque[i]
- 不支持切片，比如a_deque[0:2]
- 支持對序列和可迭代對象進(jìn)行操作的內(nèi)置函數(shù)，如 len() ，sorted() ，reversed() 等
- 不支持inplace 排序
- 支持正常迭代和反向迭代
- 支持使用pickle
- 確保在兩端快速、內(nèi)存高效和線程安全的彈出和追加操作
創(chuàng)建 deque 實(shí)例比較簡單。只需要從 collection 中導(dǎo)入 deque，然后用一個可選的迭代器作為參數(shù)來調(diào)用它。
>>> 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)])
如果實(shí)例化 deque 時(shí)沒有提供 iterable 作為參數(shù)，那么會得到一個空的 deque。如果提供并輸入 iterable ，那么 deque 會用它的數(shù)據(jù)初始化新實(shí)例。初始化使用 deque.append() 從左到右進(jìn)行。
Deque 初始化器需要以下兩個可選參數(shù)。
- iterable一個提供初始化數(shù)據(jù)的迭代器。
- maxlen一個整數(shù)，指定deque的最大長度。
如前所述，如果不提供一個 iterable ，那么你會得到一個空的 deque。如果給 maxlen 提供一個值，那么你的 deque 只會存儲最多的 maxlen 項(xiàng)。
最后，還可以使用無序的可迭代對象，如 collections 來初始化 deque。在這些情況下，不會有最終 deque 中元素的預(yù)定義順序。
有效地彈出和追加元素
Deque 和 List 之間最重要的區(qū)別是，前者可以在序列的兩端進(jìn)行有效的追加和彈出操作。Deque 類實(shí)現(xiàn)了專門的 .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è)計(jì)的，而 list 沒有這樣的方法。
Deque也提供了像list一樣的 .append() 和 .pop() 方法來對序列的右端進(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 "", line 1, in
TypeError: pop() takes no arguments (1 given)
在這里，.pop() 刪除并返回 deque 容器中的最后一個元素。該方法不接受索引作為參數(shù)，因此不能使用它從 deque 中刪除任意項(xiàng)。只能使用它來刪除并返回最右邊的項(xiàng)。
我們認(rèn)為 deque 是一個雙鏈表。因此，給定 deque 容器中的每一項(xiàng)都保存著序列中上下一項(xiàng)的引用(指針)。
雙鏈表使得從兩端添加和彈出元素的操作變得簡單而高效，因?yàn)橹挥兄羔樞枰?，因此，這兩個操作具有相似的性能，均為O(1)。它們在性能方面也是可預(yù)測的，因?yàn)椴恍枰匦路峙鋬?nèi)存和移動現(xiàn)有項(xiàng)來接受新項(xiàng)。
從常規(guī) Python 列表的左端追加和彈出元素需要移動所有元素，這最終是一個 O(n) 操作。此外，將元素添加到列表的右端通常需要Python重新分配內(nèi)存，并將當(dāng)前項(xiàng)復(fù)制到新的內(nèi)存位置，之后，它可以添加新項(xiàng)。這個過程需要更長的時(shí)間來完成，并且追加操作從 O(1)傳遞到 O(n)。
考慮以下關(guān)于在序列左端添加項(xiàng)的性能測試，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() 計(jì)算了執(zhí)行一個給定次數(shù)的函數(shù)（func）的平均時(shí)間。如果我們在命令行中運(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í)行時(shí)間是常量O(1)。但列表左端的 list.insert() 執(zhí)行時(shí)間取決于要處理的項(xiàng)的數(shù)量O(n)。
在這個例子中，如果增加 TIMES 的值，那么 list.insert() 會有更高的時(shí)間測量值，而 deque.appendleft() 會得到穩(wěn)定(常數(shù))的結(jié)果。如果對 deque 和 list 的 pop 操作進(jìn)行類似的性能測試，那么可以展開下面的練習(xí)塊。
Exercise：測試 deque.popleft() 與 list.pop(0) 的性能
可以將上面的腳本修改為時(shí)間deque.popleft()與list.pop(0)操作并估計(jì)它們的性能。
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ì)是為了保證在序列的兩端進(jìn)行有效的追加和彈出操作。它是處理需要在 Python 中實(shí)現(xiàn)隊(duì)列和堆棧數(shù)據(jù)結(jié)構(gòu)的問題的理想選擇。
訪問Deque中的任意元素
Python 的 deque 返回可變的序列，其工作方式與列表相當(dāng)類似。除了可以有效地從其末端追加和彈出元素外，deque 還提供了一組類似列表的方法和其他類似序列的操作，以處理任意位置的元素。下面是其中的一些。
|
選項(xiàng) |
描述 |
|
.insert(i, value) |
在索引為i的deque容器中插入一個名為value的元素。 |
|
.remove (value) |
刪除第一個出現(xiàn)的 value ，如果 value 不存在則引發(fā)ValueError |
|
a_deque[i] |
從一個deque容器中檢索索引為 i 的項(xiàng)。 |
|
del a_deque[i] |
從deque容器中移除索引為 i 的項(xiàng)。 |
我們可以使用這些方法和技術(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 中刪除任何存在的項(xiàng)。請注意， .remove() 允許按值刪除項(xiàng)，而del則按索引刪除項(xiàng)。
盡管 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 "", line 1, in
TypeError: sequence index must be integer, not 'slice'
Deque支持索引，卻不支持分片。通常來說在一個鏈表上執(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")
這個腳本對插入、刪除和訪問一個 deque 和一個 list 中間的元素進(jìn)行計(jì)時(shí)。如果運(yùn)行這個腳本，得到如下所示的輸出:
$ python time_random_access.py
list 63.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)作 |
? |
? |
|
通過索引訪問任意的元素 |
O(n) |
O(1) |
|
在左端彈出和追加元素 |
O(1) |
O(n) |
|
在右端彈出和追加元素 |
O(1) |
O(1) + 重新分配 |
|
在中間插入和刪除元素 |
O(n) |
O(n) |
對于列表，當(dāng)解釋器需要擴(kuò)大列表以接受新項(xiàng)時(shí)，.append()的性能優(yōu)勢受到內(nèi)存重新分配的影響而被降低。此操作需要將所有當(dāng)前項(xiàng)復(fù)制到新的內(nèi)存位置，這將極大地影響性能。
此總結(jié)可以幫助我們?yōu)槭诸^的問題選擇適當(dāng)?shù)臄?shù)據(jù)類型。但是，在從列表切換到 deque 之前，一定要對代碼進(jìn)行剖析，它們都有各自的性能優(yōu)勢。
用Deque構(gòu)建高效隊(duì)列
Deque 是一個雙端隊(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ì)列，可以在多個線程之間安全地交換信息。
如果你正在處理隊(duì)列，那么最好使用那些高級抽象而不是 deque ，除非你正在實(shí)現(xiàn)自己的數(shù)據(jù)結(jié)構(gòu)。
隊(duì)列是元素的collections，可以通過在一端添加元素和從另一端刪除元素來修改隊(duì)列。
隊(duì)列 以先入先出（FIFO）的方式管理元素，像一個管道一樣工作，在管道的一端推入新元素，并從另一端彈出舊元素。向隊(duì)列的一端添加一個元素稱為 enqueue 操作；從另一端刪除一個元素稱為 dequeue。
為了更好地理解隊(duì)列，以餐廳為例，餐館里有很多人在排隊(duì)等著點(diǎn)餐。通常情況下，后來的人將排在隊(duì)列的末端。一旦有了空桌子，排在隊(duì)伍開頭的人就會離開隊(duì)伍進(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 "", line 1, in
IndexError: pop from an empty deque
首先創(chuàng)建一個空的 deque 對象來表示到達(dá)餐廳的人的隊(duì)列。person排隊(duì)放入隊(duì)列，可以使用.append()，將單個條目添加到右端。要從隊(duì)列中取出一個person，可以使用.popleft() ，刪除并返回deque容器左側(cè)的各個條目。
用隊(duì)列模擬工作，然而，由于deque是一個泛化，它的API]不匹配常規(guī)的隊(duì)列API。例如，不是.enqueue()，而是.append()。還有.popleft() 而不是.dequeue()。此外，deque 還提供了其他一些可能不符合特定需求的操作。
我們可以創(chuàng)建具有特定功能的自定義隊(duì)列類。可以在內(nèi)部使用 deque 來存儲數(shù)據(jù)，并在自定義隊(duì)列中提供所需的功能。我們可以把它看作是適配器設(shè)計(jì)模式的一個實(shí)現(xiàn)，在這個模式中，把 deque 的接口轉(zhuǎn)換成看起來更像隊(duì)列接口的東西。
例如，需要一個自定義的隊(duì)列抽象數(shù)據(jù)類型，提供以下功能。
- 排列元素
- 去排隊(duì)的元素
- 返回隊(duì)列的長度
- 支持成員資格測試
- 支持正常和反向迭代
- 提供一個方便用戶的字符串表示法
此時(shí)可以寫一個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 對象，可以存儲和操作隊(duì)列中的元素。Queue使用 deque.append() 實(shí)現(xiàn)了 .enqueue()，將元素添加到隊(duì)列的末端。還用 deque.popleft() 實(shí)現(xiàn)了 .dequeue()，以有效地從隊(duì)列的開頭刪除元素。
支持以下特殊方法
|
Method |
Support |
|
? |
長度的 ? |
|
? |
帶有? |
|
? |
常規(guī)迭代 |
|
? |
反向迭代 |
|
? |
字符串表示形式 |
理想情況下，.__repr__()返回一個字符串，代表一個有效的 Python 表達(dá)式?？梢杂眠@個表達(dá)式以相同的值重新創(chuàng)建這個對象。
然而，在上面的例子中，目的是使用方法的返回值在 interactive shell 上優(yōu)雅地顯示對象?？梢酝ㄟ^接受初始化可迭代對象作為.__init__() 的參數(shù)并從中構(gòu)建實(shí)例，從而從這個特定的字符串表示形式構(gòu)建 Queue 實(shí)例。
有了這些補(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é)
隊(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ì)列和堆棧
鏈接地址：http://www.dlmjj.cn/article/ccidjcj.html
