Pythonアルゴリズム
Pythonのキュー(queue)
このレッスンでは、collections.dequeを使って、先入れ先出しの効率的なキューを実装します。
はじめに
どんな問題を解決するか
印刷ジョブ、サポートの問い合わせ、プログラム間のメッセージは、届いた順に処理しなければなりません。キューはその順番を保ち、Python で正しい道具を選べば、何百万件でも速く動きます。
身近なたとえ
キューはチケット売り場の行列のようなものです。新しい人は最後尾に並び、先頭の人から対応されます。誰も割り込まないので、全員が来た順に対応されます。
チケットの行列からコードへ
deque(["first", "second"])🚶🚶 すでに2人が待っているqueue.append("third")🚶 新しい人が最後尾に並ぶqueue.popleft()🎫 先頭の人が対応されるlist(queue)👀 まだ待っている人ひと言でいうと
キューは先入れ先出し(FIFO)のコレクションで、要素は最後尾に追加し、先頭から取り出します。
重要なポイント
deque(["first", "second"])はすでに2つの要素を持つキューを作ります。queue.append("third")は最後尾に要素を追加します。queue.popleft()は先頭の要素を取り出して返し、ここでは"first"です。dequeは先頭からすばやく取り出せますが、リストでは残りの全要素をずらす必要があります。
どんな場面で使う?
- タスクや要求を届いた順に処理する。
- グラフや格子での幅優先探索。
- メッセージやイベントなど、作る側と使う側の間のバッファー。
使わなくてよいとき
- 最も新しい要素を先に出すべき場合:スタックを使います。
- 要素に優先度がある場合:優先度付きキューには
heapqを使います。 - 複数のスレッドがキューを共有する場合:
queue.Queueがロックを処理してくれます。
動きで理解する
enqueueとdequeueを試すと、要素が到着した順番どおりに出ていくことがわかります。
サンプルコード
main.py
from collections import deque
queue = deque(["first", "second"])
queue.append("third")
print("served:", queue.popleft())
print("waiting:", list(queue))
実行結果
served: first
waiting: ['second', 'third']
コードの解説
dequeでは、append()で右側に要素を追加し、popleft()で左側から取り出せます。どちらもO(1)です。普通のリストで先頭の要素を削除すると、後ろの要素をすべて前に詰める必要があるためO(n)かかります。そのため、キューにはdequeのほうが適しています。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
リストと pop(0) を使う
pop(0) は残りの全要素をずらすので、長いキューでは遅くなります。
問題
queue = ["first", "second"]
queue.pop(0)
修正
queue = deque(["first", "second"])
queue.popleft()
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
進み具合はこのブラウザーに保存されています ログインすると、どのデバイスでも引き継げます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
- Course Schedule Order Order courses so every prerequisite comes first. 難しい
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. 中級