LoginSignup
191
161

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-03-02

はじめに

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

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)

計測結果

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

スクリーンショット 2020-03-01 16.35.38.png

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

スタックの結果

要素の追加

左上のグラフです。
スクリーンショット 2020-03-01 16.39.29.png
若干 deque の方が速いですが、ほぼ同じです。

要素の取り出し

右上のグラフです。
スクリーンショット 2020-03-01 16.40.06.png
こちらも若干 deque の方が速いですが、ほぼ同じです。

キューの結果

要素の追加

左下のグラフです。
スクリーンショット 2020-03-01 16.40.40.png
要素数が多くなると、 Queue が他に比べて10倍以上遅いです。

要素の取り出し

右下のグラフです。
スクリーンショット 2020-03-01 16.40.48.png
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] -> []
191
161
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
191
161