Pythonのスタックとキューには何を使えばいいのか（各データ構造の速度比較）

18069 ワード
データ構造 Python3 AtCoder Python 競技プログラミング Python テキストリンク

はじめに

本記事は、主に競技プログラミングにおける話です。

Python において、スタックとキューを実装するには複数の方法があります。

  • スタック(stack)
    • list を使う（append(), pop()）
    • collections.deque を使う（append(), pop()）
  • キュー(queue)
    • list を使う（append(), pop(0)）
    • collections.deque を使う(append(), popleft())
    • queue.Queue を使う（put(), get()）

さて、この中で一体どれを使うのが最適でしょうか。
今回はそれを速度面に注目して調べます。

計測方法

各データ構造に対して、要素の追加と取り出しを10回、100回、1000回、10000回、100000回行います。

どのコードも、以下の import 部分は省略しています。

import部分
from collections import deque
from queue import Queue
import time

スタック

listを使用
# stack(list)
stack_list_append = []
stack_list_pop = []
for i in range(1, 6):
    start = time.time()

    stack_list = []
    for j in range(10 ** i):
        stack_list.append(j)

    stack_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_list.pop()

    stack_list_pop.append(time.time() - start)
dequeを使用
# stack(deque)
stack_deque_append = []
stack_deque_pop = []
for i in range(1, 6):
    start = time.time()

    stack_deque = deque([])
    for j in range(10 ** i):
        stack_deque.append(j)

    stack_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        stack_deque.pop()

    stack_deque_pop.append(time.time() - start)

キュー

listを使用
# queue(list)
queue_list_append = []
queue_list_pop = []
for i in range(1, 6):
    start = time.time()

    queue_list = []
    for j in range(10 ** i):
        queue_list.append(j)

    queue_list_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_list.pop(0)

    queue_list_pop.append(time.time() - start)
dequeを使用
# queue(deque)
queue_deque_append = []
queue_deque_pop = []
for i in range(1, 6):
    start = time.time()

    queue_deque = deque([])
    for j in range(10 ** i):
        queue_deque.append(j)

    queue_deque_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_deque.popleft()

    queue_deque_pop.append(time.time() - start)
Queueを使用
# queue(Queue)
queue_Queue_append = []
queue_Queue_pop = []

for i in range(1, 6):
    start = time.time()

    queue_Queue = Queue()
    for j in range(10 ** i):
        queue_Queue.put(j)

    queue_Queue_append.append(time.time() - start)

    start = time.time()

    for j in range(10 ** i):
        queue_Queue.get()

    queue_Queue_pop.append(time.time() - start)

計測結果

計測結果をグラフにしたところ、次のようになりました。

左上から順に見ていきましょう。

スタックの結果

要素の追加

左上のグラフです。

若干 deque の方が速いですが、ほぼ同じです。

要素の取り出し

右上のグラフです。

こちらも若干 deque の方が速いですが、ほぼ同じです。

キューの結果

要素の追加

左下のグラフです。

要素数が多くなると、 Queue が他に比べて10倍以上遅いです。

要素の取り出し

右下のグラフです。

Queue は要素の追加の時と同じですが、list が明らかにやばいです。最速の deque と比べると100倍以上遅くなっています。

結論

スタックもキューも、collections.deque を使うのが最適です。

せっかくなので、簡単な使い方も書いておきます。

スタック

from collections import deque

s = deque([])
s.append(1)  # [1]
s.append(2)  # [1, 2]
s.append(3)  # [1, 2, 3]
s.pop()      # 一番上から取り除く [1, 2, 3] -> [1, 2]
s.pop()      # [1, 2] -> [1]
s.pop()      # [1] -> []

キュー

スタックでは取り除くときに pop だったのが、キューだと popleft になっているだけです。

from collections import deque

q = deque([])
q.append(1)  # [1]
q.append(2)  # [1, 2]
q.append(3)  # [1, 2, 3]
q.popleft()  # 一番下から取り除く [1, 2, 3] -> [2, 3]
q.popleft()  # [2, 3] -> [3]
q.popleft()  # [3] -> []