Deque in Python: Implementing efficient queues and stacks
Apr 12, 2023 pm 09:46 PM
Deque in Python is a low-level, highly optimized double-ended queue, useful for implementing elegant and efficient Pythonic queues and stacks, which are the most common list-based data types in computing.
In this article, Mr. Yun Duo will learn the following together with you:
- Start using deque
- Effectively pop up and append elements
- Access deque Any element in
- Use deque to build an efficient queue
Start using Deque
The operation of appending elements to the right end of the Python list and popping elements is generally very efficient. If time complexity is expressed in Big O, then we can say that they are O(1). When Python needs to reallocate memory to increase the underlying list to accept new elements, these operations will slow down and the time complexity may become O(n).
In addition, the operations of appending and popping elements to the left end of the Python list are also very inefficient, with a time complexity of O(n).
Since lists provide .append() and .pop() operations, they can be used as stacks and queues. The performance issues of appending and popping operations on the left and right ends of the list will greatly affect the overall performance of the application.
Python’s deque was the first data type added to the collections module as early as Python 2.4. This data type is specifically designed to overcome the efficiency issues of .append() and .pop() in Python lists.
Deques are sequence-like data types designed as a generalization of stacks and queues. They support memory-efficient and fast append and pop operations on both ends of the data structure.
Append and pop operations on both ends of a deque object are stable and equally efficient because the deque is implemented as a doubly linked list. Additionally, append and pop operations on deque are also thread-safe and memory-efficient. These features make deque particularly useful for creating custom stacks and queues in Python.
If you need to save the last seen element list, you can also use deque, because the maximum length of deque can be limited. If we do this, then once the deque is full, it will automatically discard the elements at one end when we add new elements at the other end.
The following is a summary of the main features of deque:
- Stores elements of any data type
- Is a variable data type
- Supports in The member operations of the operator
- support indexing, such as a_deque[i]
- does not support slicing, such as a_deque[0:2]
- supports sequences and iterable objects. Built-in functions for operations, such as len(), sorted(), reversed(), etc.
- Does not support inplace sorting
- Supports normal iteration and reverse iteration
- Supports the use of pickle
- Ensure fast, memory efficient, and thread-safe pop and append operations on both ends
Creating a deque instance is relatively simple. Just import deque from the collection and call it with an optional iterator as argument.
>>> from collections import deque
>>> # 創(chuàng)建一個(gè)空的 deque
>>> deque()
deque([])
>>> # 使用不同的迭代器來(lái)創(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)])If you instantiate deque without providing iterable as a parameter, you will get an empty deque. If an iterable is provided and entered, the deque initializes a new instance with its data. Initialization proceeds from left to right using deque.append().
Deque initializer requires the following two optional parameters.
- iterable An iterator that provides initialization data.
- maxlen is an integer specifying the maximum length of deque.
As mentioned before, if you don't provide an iterable, then you will get an empty deque. If you provide a value for maxlen, then your deque will only store the items up to maxlen.
Finally, you can also use unordered iterable objects, such as collections, to initialize deque. In these cases, there will be no predefined order of elements in the final deque.
Efficiently popping and appending elements
The most important difference between Deque and List is that the former can perform efficient appending and popping operations at both ends of the sequence. The Deque class implements specialized .popleft() and .appendleft() methods to directly operate on the left end of the sequence.
>>> 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])
Here, use .popleft() and .appendleft() to pop up and increase the left end value of numbers respectively. These methods are designed for deque, and list has no such method.
Deque also provides .append() and .pop() methods like list to operate on the right end of the sequence. However, the behavior of .pop() is different.
>>> 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)
Here, .pop() removes and returns the last element in the deque container. This method does not accept an index as a parameter, so it cannot be used to remove arbitrary items from the deque. You can only use it to remove and return the rightmost item.
We think deque is a doubly linked list. Therefore, each item in a given deque container holds a reference (pointer) to the previous and next item in the sequence.
Double linked lists make the operation of adding and popping elements from both ends simple and efficient, because only the pointers need to be updated, therefore, the two operations have similar performance, both are O(1). They are also predictable in terms of performance because there is no need to reallocate memory and move existing items to accept new items.
從常規(guī) Python 列表的左端追加和彈出元素需要移動(dòng)所有元素，這最終是一個(gè) O(n) 操作。此外，將元素添加到列表的右端通常需要Python重新分配內(nèi)存，并將當(dāng)前項(xiàng)復(fù)制到新的內(nèi)存位置，之后，它可以添加新項(xiàng)。這個(gè)過(guò)程需要更長(zhǎng)的時(shí)間來(lái)完成，并且追加操作從 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)行類(lèi)似的性能測(cè)試，那么可以展開(kāi)下面的練習(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ù)類(lèi)型的設(shè)計(jì)是為了保證在序列的兩端進(jìn)行有效的追加和彈出操作。它是處理需要在 Python 中實(shí)現(xiàn)隊(duì)列和堆棧數(shù)據(jù)結(jié)構(gòu)的問(wèn)題的理想選擇。
訪問(wèn)Deque中的任意元素
Python 的 deque 返回可變的序列，其工作方式與列表相當(dāng)類(lèi)似。除了可以有效地從其末端追加和彈出元素外，deque 還提供了一組類(lèi)似列表的方法和其他類(lèi)似序列的操作，以處理任意位置的元素。下面是其中的一些。
選項(xiàng) | 描述 |
.insert(i, value) | 在索引為i的deque容器中插入一個(gè)名為value的元素。 |
.remove (value) | 刪除第一個(gè)出現(xiàn)的 value ，如果 value 不存在則引發(fā)ValueError |
a_deque[i] | 從一個(gè)deque容器中檢索索引為 i 的項(xiàng)。 |
del a_deque[i] | Removes the item with index i from the deque container. |
我們可以使用這些方法和技術(shù)來(lái)處理 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 還允許索引來(lái)訪問(wèn)元素，在這里使用它來(lái)訪問(wèn)索引1處的b。最后，你可以使用 del 關(guān)鍵字從 deque 中刪除任何存在的項(xiàng)。請(qǐng)注意， .remove() 允許按值刪除項(xiàng)，而del則按索引刪除項(xiàng)。
盡管 deque 對(duì)象支持索引，但它們不支持切片，即不能像常規(guī)列表一樣使用切片語(yǔ)法， [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支持索引，卻不支持分片。通常來(lái)說(shuō)在一個(gè)鏈表上執(zhí)行切片非常低效。
雖然 deque 與 list 非常相似，但 list 是基于數(shù)組的，而 deque 是基于雙鏈表的。
Deque 基于雙鏈表，在訪問(wèn)、插入和刪除任意元素都是無(wú)效操作。如果需要執(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ì)插入、刪除和訪問(wèn)一個(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ī)訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。因此，從 deque 的中間訪問(wèn)元素的效率要比在列表上做同樣的事情低。這說(shuō)明 deque 并不總是比列表更有效率。
Python 的 deque 對(duì)序列兩端的操作進(jìn)行了優(yōu)化，所以它們?cè)谶@方面一直比 list 好。另一方面，列表更適合于隨機(jī)訪問(wèn)和固定長(zhǎng)度的操作。下面是 deque 和 list 在性能上的一些區(qū)別。
運(yùn)作 | ? | ? |
通過(guò)索引訪問(wèn)任意的元素 | O(n) | O(1) |
在左端彈出和追加元素 | O(1) | O(n) |
Pop and append elements at the right end | O (1) | ##O(1) Redistribute |
| Insert and delete elements in the middle | O(n) | O(n) |
Method | Support |
? | length of ? |
| ##? ?.__contains__( )? | Member test with? ?in? |
| ? ?.__iter__()? | Regular iteration |
| ? ?.__reversed__()? | Reverse iteration |
| ? ? .__repr__()? | String representation |
