データ構造「スタック・キュー」を整理し、Pythonの実装を確認する。

久しぶりに使う機会があって、やっぱり度忘れしてたので、覚えてるうちに、スタックとキューについてPythonでの実装例を含めて書いておこうと思います。

今回の対象について

今回対象とするのは、以下のデータ構造です。

• 後入先出キュー（Last In First Out：LIFO　＝　スタック）
• 先入先出キュー（First In First Out：FIFO）
• 両端キュー（Double Ended Queue）
• 優先度付キュー（Priority Queue）

スタック・キューの概要

上記の４つについて、まず、概要を整理してみます。

後入先出キュー（Last In First Out：LIFO　＝　スタック）

後から入れたものから、先に取り出します。

個人的な利用イメージとしては、何かの処理時のデータの退避先として使う感じです。

昔だと、逆ポーランド記法による電卓などの実装なんかが例によくでてきましたが、今時、そんなのやる人いないですしね（笑）　

先入先出キュー（First In First Out：FIFO）

先に入ったものを先に出します。

出入りにおける順序が保存されることになるので、スレッド等で処理を協調させるためのパイプライン処理とか、何かと使いでのあるデータ構造です。

処理のイメージと用語はこんな感じ。

両端キュー（Double Ended Queue）

先頭と末尾でデータの追加・取り出し・削除等ができるデータ構造です。

基本的にはこれがベースで、LIFOもFIFOもこの両端キューを特殊化したものという扱いです。

だから、FIFOとしても、LIFOとしても使えます。

さらに、先頭に追加するか、末尾に追加するかを条件で振り分けて、取り出しだけ先頭からだけにして「条件付きFIFO」みたいなものにしたり・・色々柔軟に使えます。

優先度付キュー（Priority Queue）

キューに対して要素を優先度付きで追加して、取り出す時には常に優先度の高いものが取り出されるというようなキューです。

何かしらのデータを優先度付きでキューにつっこんで、優先度の高いものから常に処理させるコントローラ的なものとか、これも色々と使いでがあります。

 Pythonでの実装

キューの種類ごとに、Pythonの実装と典型的な利用例を書きます。

後入先出キュー（Last In First Out：LIFO　＝　スタック）

スタックは、Pythonの標準リストで問題なく実装可能です。

• 最後尾への追加：append()
• 最後尾からの取り出し：pop()

pythonの実装です。 

import time


start = time.time()

lifo_list = []
for i in range(1, 1000000):
    lifo_list.append(i)

for i2 in range(1, 1000000):
    poped = lifo_list.pop()

print(poped)

stop = time.time()
print('%.3f seconds' % (stop - start))

100万件スタックにプッシュして、100万回POPしてます。 

start = time.time()　

~

stop = time.time()
print('%.3f seconds' % (stop - start))

 で挟み込んで時間計測をしてみると、自分のPCで平均「0.240秒」くらいでした。

速度的な問題もないと思います。

先入先出キュー（First In First Out：FIFO）

これは、用途によって２通りの方法を使い分ける感じになります。

パイプライン処理とかでなければ、「両端キュー（Double Ended Queue）」の実装である、「Collections.deque」が使えます。

パイプライン処理の場合はスレッド間の協調をとる機能をそなえた「Queue」が使えます。

最初に「collections.deque」の実装例です。

• 最後尾への追加：append()
• 先頭からの取り出し：popleft()

となります。

import time
from collections import deque

start = time.time()

fifo_que = deque()
for i in range(1, 1000000):
    fifo_que.append(i)

for i2 in range(1, 1000000):
    poped = fifo_que.popleft()

print(poped)

stop = time.time()
print('%.3f seconds' % (stop - start))

リストのスタックの例と同様に100万回処理してます。

自分のPCで平均「0.202秒」くらいでした。

リストのスタックより速いってのは大したもんですね。

今度は「Queue」です。

同期FIFOキューです。

docs.python.org

Queueに入れたタスクが完了するのを待つパターンをやってみます。

from queue import Queue
import threading


def do_work(item):
    print("Now working=", item)


def worker():
    while True:
        item = q.get()
        if item is None:
            break
        do_work(item)
        q.task_done()

q = Queue()
num_worker_threads = 4
items = [100, 200, 301, 231, 442, 452, 993, 444]

threads = []
for i in range(num_worker_threads):
    t = threading.Thread(target=worker)
    t.start()
    threads.append(t)

for item in items:
    q.put(item)

# 全てのタスクが終了するのを待つ
q.join()

# workerを停止するためにNoneをputする
for i in range(num_worker_threads):
    q.put(None)
for t in threads:
    t.join()

worker タスクをスレッド４つ分動かして、キューにput()されるのを待って実行させてから、全てのタスクの終了を待って、worker()を停止させて、スレッドを終了させるということをやってます。

自分のPCで動かした結果は、都度違うのですが、こんな感じに出力されます。

Now working= 100
Now working= 301
Now working= 452
Now working= 993
Now working= 200
Now working= 231
Now working= 442
Now working= 444

優先度付キュー（Priority Queue） 

heapqモジュールを使います。

heapqモジュールは、標準のList型にヒープを作成して、ランダムに追加しても、取り出す時には一番優先度の高いもの（数値なら一番小さいもの）になるようにします。

• heappush()でキューに追加します。
• heappop()で優先度の一番高いものを取り出します。

ランダムな整数をヒープキューに収めて、取り出す例の実装です。

import heapq
import random

heap_list = []

ini_list = [random.randint(1, 100) + x for x in range(1, 10)]
print(ini_list)
for x in ini_list:
    heapq.heappush(heap_list, x)

for i in range(1, 10):
    r = random.randint(1, 100)
    heapq.heappush(heap_list, r)
    print(heap_list, "=>", end="")
    print(heapq.heappop(heap_list))

ランダムな整数を10個キューにおさめたものに、ランダムな整数を追加しては取り出す・・ってのをやってます。 

それで本当に優先度が高い（数字が一番小さい）ものを取り出しているかを見ます。

結果は・・例えば・・こんな感じです。

[18, 34, 76, 44, 73, 99, 25, 65, 91]
[18, 34, 25, 44, 73, 99, 76, 65, 91, 94] =>18
[9, 25, 76, 44, 34, 99, 94, 65, 91, 73] =>9
[23, 25, 76, 44, 34, 99, 94, 65, 91, 73] =>23
[25, 34, 76, 44, 73, 99, 94, 65, 91, 90] =>25
[34, 44, 76, 65, 55, 99, 94, 90, 91, 73] =>34
[8, 44, 76, 65, 55, 99, 94, 90, 91, 73] =>8
[44, 55, 76, 65, 73, 99, 94, 90, 91, 82] =>44
[55, 65, 76, 82, 73, 99, 94, 90, 91, 78] =>55
[24, 65, 76, 82, 73, 99, 94, 90, 91, 78] =>24

 確かに、左側の取り出す前のリストを見ると、その中の一番小さい数がpopされているのがわかります。

でも。

一番左（先頭）にだけ、一番優先度が高い（数字が小さい）ものを、heappush()時に送り込んでいるようですが、それ以外の二番手以降の並び順はバラバラだというのが面白いですね。

毎回、全体を整列しなおしてると思ってましたが、こういう所でスピードを稼いでいるんですね。

まとめ

スタックとキューについて、ざっくりまとめました。

割とよく使うデータ構造なので、知らずに自分で実装してしまってたりしないように、何があるかは覚えておかないと・・です。。

ではでは。