Python での Deque: 効率的なキューとスタックの実装

Python の Deque は、低レベルで高度に最適化された両端キューであり、コンピューティングにおいて最も一般的なリストベースのデータ型である、エレガントで効率的な Python のキューとスタックの実装に役立ちます。

この記事では、Yun Duo 氏があなたと一緒に次のことを学びます:

• deque の使用を開始する
• 要素を効果的にポップアップおよび追加する
• deque の任意の要素にアクセスする
• deque を使用して効率的なキューを構築する

Deque の使用を開始する

Python の右端に要素を追加する操作要素のリストとポップは一般に非常に効率的です。時間計算量を Big O で表現すると、O(1) であると言えます。新しい要素を受け入れるために基になるリストを増やすために Python がメモリを再割り当てする必要がある場合、これらの操作が遅くなり、時間計算量が O(n) になる可能性があります。

さらに、Python リストの左端に要素を追加したりポップしたりする操作も非常に非効率であり、時間計算量は O(n) です。

リストは .append() および .pop() 操作を提供するため、スタックおよびキューとして使用できます。リストの左端と右端での追加およびポップ操作のパフォーマンスの問題は、アプリケーション全体のパフォーマンスに大きな影響を与えます。

Python の両端キューは、Python 2.4 の時点でコレクション モジュールに追加された最初のデータ型でした。このデータ型は、Python リストの .append() および .pop() の効率性の問題を克服するために特別に設計されています。

Deques は、スタックとキューを一般化して設計されたシーケンスのようなデータ型で、データ構造の両端でメモリ効率が高く、高速な追加およびポップ操作をサポートします。

両端キューは二重リンク リストとして実装されているため、両端キュー オブジェクトの両端での追加およびポップ操作は安定しており、同様に効率的です。さらに、デキューでの追加およびポップ操作もスレッドセーフでメモリ効率が高くなります。これらの機能により、deque は Python でカスタム スタックとキューを作成する場合に特に便利になります。

最後に表示された要素リストを保存する必要がある場合は、deque の最大長が制限されている可能性があるため、deque を使用することもできます。これを行うと、両端キューがいっぱいになると、もう一方の端に新しい要素を追加するときに、一方の端の要素が自動的に破棄されます。

以下は、deque の主な機能の概要です。

• 任意のデータ型の要素を格納します
• 変数データ型です
• 演算子
• のメンバー操作でのサポートは、a_deque[i]
• などのインデックス作成をサポートします。a_deque[0:2]
• などのスライスはサポートしません。シーケンスをサポートします。 len()、sorted()、reversed() などの操作用の組み込み関数
• インプレース ソートはサポートされません
• 通常の反復と逆反復をサポートします
• pickle の使用をサポートします
• 両端での高速でメモリ効率が高く、スレッドセーフなポップおよび追加操作を保証します

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 を指定せずに両端キューをインスタンス化すると、空の両端キューが取得されます。 iterable が提供されて入力されると、両端キューはそのデータを使用して新しいインスタンスを初期化します。初期化は、deque.append() を使用して左から右に進みます。

Deque イニシャライザには、次の 2 つのオプションのパラメータが必要です。

• iterable 初期化データを提供するイテレータ。
• maxlen は、両端キューの最大長を指定する整数です。

前に述べたように、反復可能オブジェクトを指定しない場合は、空の両端キューが取得されます。 maxlen の値を指定すると、両端キューには maxlen までの項目のみが保存されます。

最後に、コレクションなどの順序付けされていない反復可能オブジェクトを使用して両端キューを初期化することもできます。このような場合、最終デキュー内の要素の順序は事前に定義されていません。

要素の効率的なポップと追加

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 用に設計されており、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 は二重リンクリストであると考えています。したがって、特定の両端キュー コンテナー内の各項目は、シーケンス内の前後の項目への参照 (ポインター) を保持します。

二重リンク リストを使用すると、両端からの要素の追加とポップの操作が簡単かつ効率的になります。更新する必要があるのはポインターだけであるため、2 つの操作のパフォーマンスは同等であり、どちらも 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]	インデックス i の項目を deque コンテナから削除します。

我们可以使用这些方法和技术来处理 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)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(n)
要素を右端にポップして追加します	O (1)	##O(1) 再配布

Method	Support
​​.__len__ ()​​	#len()
.__contains__( ) の長さ	で を使用したメンバー テスト
## .__iter__()	定期的な反復
.__reversed__()	逆反復
# .__repr__()	文字列表現

理想情况下，.__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

总结

队列和堆栈是编程中常用的 抽象数据类型。它们通常需要在底层数据结构的两端进行有效的 pop 和 append 操作。Python 的 collections 模块提供了一种叫做 deque 的数据类型，它是专门为两端的快速和节省内存的追加和弹出操作而设计的。

有了deque，我们可以用优雅、高效和Pythonic的方式在低层次上编写我们自己的队列和堆栈。

总结下本文所学内容：

• 如何在代码中创建和使用Python的deque
• 如何有效地从deque的两端追加和弹出项目
• 如何使用deque来构建高效的队列和堆栈
• 什么时候值得使用deque而不是list

以上がPython での Deque: 効率的なキューとスタックの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。