PriorityQueueで比較法を指定する

Problem 70はフォーラム向けにまずPythonで解きました。そのとき、最初はPriorityQueueにつっこむ値をdoubleにしていました。しかし、これは正確ではありません。doubleで表現すると同じ値でも実は違う値ということもあり得ます。もっともそれが両方とも並べ替えになっているなどということはまず考えられません。それでも厳密性を保つためにFractionを最初は使いました。しかし、PythonのFractionが非常に遅いことはよく知られています。10¹²でdoubleに対して5.5倍ほど遅かったです。そこでFractionを自作します。

しかし、PythonのPriorityQueueはどうやらSTLやScalaのように比較法を指定できないようなのです。ただ、__lt__がオブジェクトにあればそれを見るようなので、Fractionを自作して__lt__を次のように書けばよいです。

class MyFrac:
    def __init__(self, a, b):
        self.a, self.b = a, b
    
    def __lt__(self, f):
        return self.a * f.b < self.b * f.a

これでFractionを使った時より1.7倍くらい速くなりました。