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