n-knuu's logs

憧れ駆動。だいたい競プロ

Pythonのキューと優先度付きキュー

概要

Pythonでは、キューとしてlistとcollections.dequeとqueue.Queueが、優先度付きキューとしてheapqとqueue.PriorityQueueが使えることは知っていたのだけれど、どれを使えばいいのか毎回迷ってしまうのでとりあえず時間を計測してみた。

結論

特に気にしないなら、速さの面で有利なキューはcollections.dequeを、優先度付きキューはheapqを使う。

実行環境

Python 3.4.1 |Anaconda 2.1.0 (x86_64)| (default, Sep 10 2014, 17:24:09)
[GCC 4.2.1 (Apple Inc. build 5577)] on darwin
OS X Yosemite 10.10.3

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の利点についてはよく分からなかった。