Python의 Deque: 효율적인 큐 및 스택 구현-파이썬 튜토리얼-php.cn

Python의 deque는 컴퓨팅에서 가장 일반적인 목록 기반 데이터 유형인 우아하고 효율적인 Python 대기열 및 스택을 구현하는 데 유용한 저수준의 고도로 최적화된 deque입니다.

이 기사에서 윤 듀오 선생님은 다음 내용을 함께 배울 것입니다.

deque 사용 시작
효과적인 팝업 및 요소 추가
deque의 모든 요소에 액세스
deque를 사용하여 효율적인 대기열 구축

deque를 사용해 보세요

파이썬 목록의 오른쪽 끝에 요소를 추가하고 요소를 터뜨리는 작업은 일반적으로 매우 효율적입니다. 시간 복잡도를 Big O로 표현하면 O(1)이라고 말할 수 있습니다. Python이 새 요소를 허용하기 위해 기본 목록을 늘리기 위해 메모리를 재할당해야 하는 경우 이러한 작업이 느려지고 시간 복잡도가 O(n)이 될 수 있습니다.

또한 Python 목록의 왼쪽 끝에 요소를 추가하고 팝하는 작업도 시간 복잡도가 O(n)로 매우 비효율적입니다.

목록은 .append() 및 .pop() 작업을 제공하므로 스택 및 대기열로 사용할 수 있습니다. 목록의 왼쪽과 오른쪽 끝에서 추가 및 팝핑 작업의 성능 문제는 애플리케이션의 전체 성능에 큰 영향을 미칩니다.

Python의 deque는 Python 2.4에서 컬렉션 모듈에 추가된 최초의 데이터 유형이었습니다. 이 데이터 유형은 Python 목록에서 .append() 및 .pop()의 효율성 문제를 극복하기 위해 특별히 설계되었습니다.

Deques는 스택과 큐의 일반화로 설계된 시퀀스와 유사한 데이터 유형으로, 데이터 구조의 양쪽 끝에서 메모리 효율적이고 빠른 추가 및 팝 작업을 지원합니다.

deque 개체의 양쪽 끝에서 추가 및 팝 작업은 deque가 이중 연결 목록으로 구현되므로 안정적이고 효율적입니다. 또한 deque의 추가 및 팝 작업은 스레드로부터 안전하고 메모리 효율적입니다. 이러한 기능을 통해 Deque는 Python에서 사용자 정의 스택 및 큐를 생성하는 데 특히 유용합니다.

마지막으로 본 요소 목록을 저장해야 하는 경우 deque를 사용할 수도 있습니다. deque의 최대 길이가 제한될 수 있기 때문입니다. 이렇게 하면 deque가 가득 차면 다른 쪽 끝에 새 요소를 추가할 때 한쪽 끝에 있는 요소가 자동으로 삭제됩니다.

다음은 deque의 주요 기능에 대한 요약입니다.

모든 데이터 유형의 요소를 저장합니다.
은 변경 가능한 데이터 유형입니다.
in 연산자를 사용한 멤버 작업 지원
a_deque[i]와 같은 인덱스 지원
No a_deque[0:2]와 같은 슬라이싱을 지원합니다.
len(), sorted(), reversed() 등과 같은 시퀀스 및 반복 가능한 객체에서 작동하는 내장 함수를 지원합니다.
지원하지 않습니다 내부 정렬
일반 반복 및 역방향 반복 지원
피클 사용 지원
양쪽 끝에서 빠르고 메모리 효율적이며 스레드로부터 안전한 팝 및 추가 작업 보장

deque 인스턴스 생성은 비교적 간단합니다. 컬렉션에서 deque를 가져오고 선택적 반복자를 인수로 사용하여 호출하세요.

>>> from collections import deque

>>> # 创建一个空的 deque
>>> deque()
deque([])

>>> # 使用不同的迭代器来创建 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)])

로그인 후 복사

iterable을 매개변수로 제공하지 않고 deque를 인스턴스화하면 빈 deque를 얻게 됩니다. iterable이 제공되고 입력되면 deque는 해당 데이터로 새 인스턴스를 초기화합니다. 초기화는 deque.append()를 사용하여 왼쪽에서 오른쪽으로 진행됩니다.

Deque 초기화에는 다음 두 가지 선택적 매개변수가 필요합니다.

iterable은 초기화 데이터를 제공하는 반복자입니다.
maxlen은 deque의 최대 길이를 지정하는 정수입니다.

앞서 언급했듯이 iterable을 제공하지 않으면 빈 deque를 얻게 됩니다. maxlen에 값을 제공하면 deque는 최대 maxlen까지만 항목을 저장합니다.

마지막으로 컬렉션과 같이 순서가 지정되지 않은 반복 가능한 개체를 사용하여 deque를 초기화할 수도 있습니다. 이러한 경우 최종 deque에는 미리 정의된 요소 순서가 없습니다.

요소를 효율적으로 팝하고 추가합니다

Deque와 List의 가장 중요한 차이점은 전자가 시퀀스의 양쪽 끝에서 효율적인 추가 및 팝 작업을 수행할 수 있다는 것입니다. Deque 클래스는 특수한 .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()를 사용하여 각각 숫자의 왼쪽 끝 값을 팝업하고 추가합니다. 이러한 메소드는 deque용으로 설계되었으며 목록에는 그러한 메소드가 없습니다.

Deque는 시퀀스의 오른쪽 끝에서 작동하는 목록과 같은 .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 컨테이너의 마지막 요소를 제거하고 반환합니다. 이 메서드는 인덱스를 매개변수로 허용하지 않으므로 데크에서 임의의 항목을 제거하는 데 사용할 수 없습니다. 가장 오른쪽 항목을 제거하고 반환하는 데만 사용할 수 있습니다.

deque는 이중 연결 리스트라고 생각합니다. 따라서 지정된 deque 컨테이너의 각 항목은 시퀀스의 이전 항목과 다음 항목에 대한 참조(포인터)를 보유합니다.

이중 연결 목록은 포인터만 업데이트하면 되므로 양쪽 끝에서 요소를 추가하고 팝하는 작업을 간단하고 효율적으로 만듭니다. 따라서 두 작업의 성능은 비슷하며 둘 다 O(1)입니다. 또한 새 항목을 수용하기 위해 메모리를 재할당하거나 기존 항목을 이동할 필요가 없기 때문에 성능 측면에서도 예측 가능합니다.

从常规 Python 列表的左端追加和弹出元素需要移动所有元素，这最终是一个 O(n) 操作。此外，将元素添加到列表的右端通常需要Python重新分配内存，并将当前项复制到新的内存位置，之后，它可以添加新项。这个过程需要更长的时间来完成，并且追加操作从 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() 计算了执行一个给定次数的函数（func）的平均时间。如果我们在命令行中运行该脚本，那么我们会得到以下输出。

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

로그인 후 복사

在这个例子中，deque 上的 .appendleft() 要比 list 上的 .insert() 快几倍。注意 deque.appendleft() 执行时间是常量O(1)。但列表左端的 list.insert() 执行时间取决于要处理的项的数量O(n)。

在这个例子中，如果增加 TIMES 的值，那么 list.insert() 会有更高的时间测量值，而 deque.appendleft() 会得到稳定(常数)的结果。如果对 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的值，看看会发生什么

로그인 후 복사

Deque 数据类型的设计是为了保证在序列的两端进行有效的追加和弹出操作。它是处理需要在 Python 中实现队列和堆栈数据结构的问题的理想选择。

访问Deque中的任意元素

Python 的 deque 返回可变的序列，其工作方式与列表相当类似。除了可以有效地从其末端追加和弹出元素外，deque 还提供了一组类似列表的方法和其他类似序列的操作，以处理任意位置的元素。下面是其中的一些。

选项	描述
.insert(i, value)	在索引为i的deque容器中插入一个名为value的元素。
.remove (value)	删除第一个出现的 value ，如果 value 不存在则引发ValueError
a_deque[i]	从一个deque容器中检索索引为 i 的项。
del a_deque[i]	deque 컨테이너에서 인덱스가 i인 항목을 제거합니다.

我们可以使用这些方法和技术来处理 deque 对象内部任何位置的元素。下面是如何做到这一点的。

>>> 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 对象支持索引，但它们不支持切片，即不能像常规列表一样使用切片语法， [start:stop:step] 从现有的 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支持索引，却不支持分片。通常来说在一个链表上执行切片非常低效。

虽然 deque 与 list 非常相似，但 list 是基于数组的，而 deque 是基于双链表的。

Deque 基于双链表，在访问、插入和删除任意元素都是无效操作。如果需要执行这些操作，则解释器必须在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
list63.8658 μs (1.44517x faster)
deque 92.2968 μs

로그인 후 복사

Deque并不像列表那样是随机访问的数据结构。因此，从 deque 的中间访问元素的效率要比在列表上做同样的事情低。这说明 deque 并不总是比列表更有效率。

Python 的 deque 对序列两端的操作进行了优化，所以它们在这方面一直比 list 好。另一方面，列表更适合于随机访问和固定长度的操作。下面是 deque 和 list 在性能上的一些区别。

O (n) 右 오른쪽 끝의 플러그 및 추가 요소 요소 삽입 및 삭제 가운데

对于列表，当解释器需要扩大列表以接受新项时，.append()的性能优势受到内存重新分配的影响而被降低。此操作需要将所有当前项复制到新的内存位置，这将极大地影响性能。

此总结可以帮助我们为手头的问题选择适当的数据类型。但是，在从列表切换到 deque 之前，一定要对代码进行剖析，它们都有各自的性能优势。

用Deque构建高效队列

Deque 是一个双端队列，提供了堆栈和队列的泛化。在本节中，我们将一起学习如何使用deque以优雅、高效和Pythonic的方式在底层实现我们自己的队列抽象数据类型（ADT）。

注意：在 Python 标准库中，queue 模块实现了多生产者、多消费者的队列，可以在多个线程之间安全地交换信息。

如果你正在处理队列，那么最好使用那些高级抽象而不是 deque ，除非你正在实现自己的数据结构。

队列是元素的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 "<stdin>", line 1, in <module>
IndexError: pop from an empty deque

로그인 후 복사

首先创建一个空的 deque 对象来表示到达餐厅的人的队列。person排队放入队列，可以使用.append()，将单个条目添加到右端。要从队列中取出一个person，可以使用.popleft() ，删除并返回deque容器左侧的各个条目。

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

我们可以创建具有特定功能的自定义队列类。可以在内部使用 deque 来存储数据，并在自定义队列中提供所需的功能。我们可以把它看作是适配器设计模式的一个实现，在这个模式中，把 deque 的接口转换成看起来更像队列接口的东西。

例如，需要一个自定义的队列抽象数据类型，提供以下功能。

排列元素
去排队的元素
返回队列的长度
支持成员资格测试
支持正常和反向迭代
提供一个方便用户的字符串表示法

此时可以写一个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() 实现了 .enqueue()，将元素添加到队列的末端。还用 deque.popleft() 实现了 .dequeue()，以有效地从队列的开头删除元素。

支持以下特殊方法

运作	`deque`	`list`
通过索引访问任意的元素	O(n)	O(1)
在左端弹出和追加元素	O(1)
O (1)	O (1) + 재할당
O(n)	O(n)

带유成员测试

Method	Support
`.__len__ ()`	长degree적 `len()``len()`
`.__contains__()`	带有`in`的成员测试
`.__iter__()`	常规迭代
`.__reversed__()`	反向迭代
`.__repr__()`
	`.__contains__()`

🎜.__iter__()🎜🎜🎜🎜常规迭代🎜🎜 🎜🎜.__reversed__()🎜🎜🎜反向迭代🎜🎜🎜🎜🎜.__repr__()🎜🎜🎜🎜字符串表示shape式🎜🎜🎜🎜🎜

理想情况下，.__repr__()返回一个字符串，代表一个有效的 Python 表达式。可以用这个表达式以相同的值重新创建这个对象。

然而，在上面的例子中，目的是使用方法的返回值在 interactive shell 上优雅地显示对象。可以通过接受初始化可迭代对象作为.__init__() 的参数并从中构建实例，从而从这个特定的字符串表示形式构建 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

로그인 후 복사