Pythonのfractions.Fraction.__hash__が遅いっぽいという話

AtCoder Beginner Contest 168 E - ∙ (Bullet)を解いていたときに気づいた話です。

直角の関係になっているイワシを判定して組み合わせから引くという問題です。
直角の組み合わせは有理数ライブラリを使えば見つけやすいので、fractions.Fractionを使って提出する。

……しかし、TLEしてしまいます。

その後自作の有理数ライブラリを作ってみて提出するとACになりました。
もともとfractionsが遅いことは有名だが、どうして大した計算もしていないのにTLEになるのか？と疑問に思ったのでいろいろ試してみると、__hash__関数が悪さしているんじゃないか？とたどり着きました。

Fractionの__hash__をオーバーライドして、__str__をそのままハッシュ化することとしてみます。

class frac(Fraction):
    def __hash__(self):
        return hash(super().__str__())

提出すると、無事ACできました。

__hash__をオーバーライドするだけでは他の遅さが解決できるわけではないですが、dictのキーとして参照する程度であればとりあえずやり過ごせますよという話でした。

徒然