Pythonのキューと優先度付きキュー
概要
Pythonでは、キューとしてlistとcollections.dequeとqueue.Queueが、優先度付きキューとしてheapqとqueue.PriorityQueueが使えることは知っていたのだけれど、どれを使えばいいのか毎回迷ってしまうのでとりあえず時間を計測してみた。
結論
特に気にしないなら、速さの面で有利なキューはcollections.dequeを、優先度付きキューはheapqを使う。
list vs collections.deque vs queue.Queue
まずキューについて、公式リファレンスには以下のように書いてある。
5.1.2. リストをキューとして使う
リストをキュー (queue) として使うことも可能です。この場合、最初に追加した要素を最初に取り出します (“first-in, first-out”)。しかし、リストでは効率的にこの目的を達成することが出来ません。追加(append)や取り出し(pop)をリストの末尾に対しておこなうと速いのですが、挿入(insert)や取り出し(pop)をリストの先頭に対しておこなうと遅くなってしまいます(他の要素をひとつずつずらす必要があるからです)。キューの実装には、 collections.deque を使うと良いでしょう。このクラスは良く設計されていて、高速な追加(append)と取り出し(pop)を両端に対して実現しています。
5. データ構造 — Python 3.4.3 ドキュメント
それとは別に、queue.Queueクラスがある。
17.7. queue — 同期キュークラス — Python 3.4.3 ドキュメント
こちらは"マルチスレッドプログラミングで特に有益"と書いてあるが、実際は速度はどれくらいなのか気になった。そこで、timeitモジュールを使って時間を計測してみることにした。
使ったコード
ランダムに整数のリストを作成して、全部append→全部popということをやっている。
結果
list | 2.220s |
---|---|
collections.deque | 2.049s |
queue.Queue | 8.385s |
heapq vs queue.PriorityQueue
Pythonで優先度付きキューを使う際は、ヒープキューを実装したheapqモジュール
8.5. heapq — ヒープキューアルゴリズム — Python 3.4.3 ドキュメント
と、queue.PriorityQueueクラスがある。
17.7. queue — 同期キュークラス — Python 3.4.3 ドキュメント
上と同様にtimeitで時間を計測してみることにした。
使ったコード
上と同様に、ランダムに整数のリストを作成して、全部append→全部popということをやっている。
結果
heapq | 2.592s |
---|---|
queue.PriorityQueue | 8.674s |
まとめなど
deque < list < < < < Queue
heapq < < < < PriorityQueue
となった。
dequeとlistの差があまり出なかったのは、リストが10**3と短いからだろうか。挿入の回数 < 削除の回数 となるようなリストだともっとわかりやすく差が出るのかもしれない。
マルチスレッドプログラミングについてはほとんど知らないのでQueueやPriorityQueueの利点についてはよく分からなかった。