優先順位付きキューを使おうとして、17.7. queue — 同期キュークラス – Python 3.3.3 ドキュメントを見たところ、よく分からない一文に遭遇した。

最小の値を持つ要素が最初に検索されます

書いていることの意味は分かるんですよ。分からないのは、「じゃあ比較はどうすればいいの？」という点。 ちなみに、自作クラスのインスタンスを優先順位付きキューにそのまま入れてみたら、怒られました。

1
2
3
4

from queue import PriorityQueue

pq = PriorityQueue()
pq.put(A())

1

TypeError: unorderable types: A() < A()

このエラーから察するに、PriorityQueue自身に比較用メソッドを渡してあげるのではなく、 インスタンス間で大小を比較できるようにしなさい、ということなのだろうと推測しました。 そうと分かれば話は早いってんで、 Python言語リファレンスの3. データモデル を見ると、目的の情報を見つけることが出来ました。

1
2
3
4
5
6
7
8

object.__lt__(self, other)
object.__le__(self, other)
object.__eq__(self, other)
object.__ne__(self, other)
object.__gt__(self, other)
object.__ge__(self, other)

これらはいわゆる “拡張比較 (rich comparison)” メソッドです。

objectには特殊メソッド名がいくつかあるのですが、その中に比較に関するメソッドも 用意されていたわけですね。

今回のエラーから必要なのは、__lt__ メソッドをオーバーライドしてあげれば良いと分かり、 早速Aクラスに__lt__メソッドの詳細を実装したところ、うまく動きました。