読者です 読者をやめる 読者になる 読者になる

PythonでPriorityQueue

PythonでPriorityQueueを使おうと思ったら割と微妙な感じだったので書いてみる。
PriorityQueueとは優先順キューのこと。(優先順位にしたがって要素が追加削除できるキュー
ヒープアルゴリズムによって制御されており、
最小値を得ながら要素を追加していきたい、
なんていうときに使う。
どうしてこれが有用かというと、探索ルーチンなどのような場合に、
現在最小(最優先のもの)を探しながら見つかった要素をQueueに溜め込む、
なんていうときに単純なlistでは効率的にできないのだが、
これを解決する。
毎回ソートしたり、適切な場所に挿入するようなappendを書くよりずっと良い。

これには用意されているモジュールheapqを使う。
関数化されているので、heappushとheappopでデータを操作する簡易クラスを定義してみた。

from heapq import heappush, heappop
from random import randint
from time import time

class PriorityQueue(object):
    def __init__(self):
        self.queue = []
    def push(self, value):
        heappush(self.queue, value)
    def pop(self):
        return heappop(self.queue)
    def __len__(self):
        return len(self.queue)
    def __contains__(self, item):
        return item in self.queue
    #...

class Foo(object):
    def __init__(self, index, value):
        self.index = index
        self.value = value
    def __str__(self):
        return "Foo%02d(%d)" % (self.index, self.value)
    def __le__(self, other):
        return self.value <= other.value

queue = PriorityQueue()

data = [1,3,5,7,9,2,100,104,1000,2000,999,999,999,0,45]
for index, value in enumerate(data):
    queue.push(Foo(index, value))
    
while len(queue) > 0:
    foo = queue.pop()
    print foo

大小判定に__le__が使われているようなので要素に対する__le__を定義してある。

結果はこんな感じ。

Foo13(0)
Foo00(1)
Foo05(2)
Foo01(3)
Foo02(5)
Foo03(7)
Foo04(9)
Foo14(45)
Foo06(100)
Foo07(104)
Foo11(999)
Foo10(999)
Foo12(999)
Foo08(1000)
Foo09(2000)

popする際に適切な並びになっていることがわかる。
ただし、heapに使っているlistが常にソートされているわけではないことに注意。
あくまでpushやpopの際に適切な挿入や削除を行ってくれるだけ。
これだけで単にlistに挿入やソート済みlistを使うより何十倍も速くなる。
検証プログラムは時間があれば。