『テスト駆動開発』をPythonで写経するにあたって演算子のオーバーロードとハッシュテーブルについて調べた

こんにちは。完全リモートワークもそろそろ3ヶ月目に入って、運動不足が深刻になってきた丸山です。今回は超有名な技術書『テスト駆動開発』をPythonで写経しながら学んでいく途中でわからなかったこと、調べたことなどを記事にまとめてみました。知識としては基本的な内容かもしれませんが、私と同じように『テスト駆動開発』を読んでいてピンとこなかった方の助けになれたら幸いです。

eqメソッドを再定義する

書籍では序盤にMoneyを値オブジェクトとして表現する方法が登場します。 Moneyを値オブジェクトとして扱うにあたって、例えば以下のようなテストを通す必要があります。

def test_equality_true_dollar():
    """
    5ドルと5ドルは等しいことを確認する
    """
    assert Money.dollar(5) == Money.dollar(5)

ところが、単純に以下のような実装を行なってもテストは通りません。

class Money:
    def __init__(self, amount, currency):
        self.amount = amount
        self.currency = currency
   
    @classmethod
    def dollar(klass, amount):
        return Money(amount, "USD")
  
assert Money.dollar(5) == Money.dollar(5)
# AssertionError

pythonの == 演算子はデフォルトではオブジェクトIDを比較するため、値が同じでもオブジェクトIDが違えばFalse返ってしまいます。そこで、値が同じであれば== でTrueを返すように、 __eq__() メソッドを再定義します。(書籍のjavaのコードではequalsメソッドを定義している部分に対応します。)

__eq__() は == 演算子が使用された際に、暗黙的に対象のオブジェクトに実行されるメソッドで、これを再定義することで==演算子の動作も再定義できます。

ここでは、amountとcurrencyが同じならTrueを返すように実装すると、別のオブジェクトでも値が同じなら同じものとして扱えるようになります。

def __eq__(self, money):
    return self.currency == money.currency and self.amount == money.amount

その他の特殊メソッド

書籍では10章(68ページ)で、エラーメッセージ読みやすくするためにtoStringメソッドを実装しています。これもpythonでは特殊メソッドにあたり、同じことを実現するためには __str___() メソッドを実装します。

def __str__(self):
    return f"{self.amount} {self.currency}"

__str__() はprint()関数を実行する際にも対象のオブジェクトに自動的に実行されて出力されます。標準では<main.Money object at 0x10c3a16d0>のように出力されてしまうますが、上記のように __str__() を再定義することで、実行時のオブジェクトの状態を把握しやすくなります。

# __str__()を実装しない場合
print(Money.dollar(5))
# &lt;__main__.Money object at 0x10c3a16d0&gt;
  
# __str__()を実装した場合
print(Money.dollar(5))
# 5 USD

独自オブジェクトを辞書型のキーにするには

また、書籍では14章(106ページ)でPairという通貨のペアを値オブジェクトとして定義し、ratesという通過ペア: 取引レートを表す辞書型のキーとして使う場面があります。ここでjavaでは、equalsメソッドとhashメソッドを定義していますが、pythonでは __eq__() メソッドと __hash__() メソッドになります。

class Pair:
    def __init__(self, source, to):
        self.source = source
        self.to = to
  
    def __eq__(self, pair):
        return self.source == pair.source and self.to == pair.to
  
    def __hash__(self):
        return hash(self.to + self.source)
  
usd_jpy = Pair("USD", "JPY")
rates = {}
  
rates[usd_jpy] = 1
  
assert rates[usd_jpy] == 1
# sourceとtoが同じであれば同じものとして扱いたいので、当然Trueであってほしい
assert rates[usd_jpy] == rates[Pair("USD", "JPY")]
# __hash__メソッドがない場合、TypeError: unhashable type: 'Pair'

独自のオブジェクトを辞書型のキーとして利用するためには、 __eq__() だけでなく __hash__() メソッドが定義されている必要があります。

hashメソッドの役割とは...?

ひとまずこれで、独自オブジェクトを辞書型のキーとして使うという目的は達成できましたが、なぜhashメソッドを定義することで、辞書型のキーとして使えるようになるのかがわかりませんでした。そこで調べてみたところ、pyhton(や他の多くの言語)の辞書型(ハッシュテーブル)の実装に関わった理由であることがわかりました。

まず辞書型がそれぞれの辞書を配列に格納するような形で保管されていると仮定して考えてみます。この場合、"John"がキーになっている項目を探して取り出すためには、配列を1から順に確認していく必要があります。例になっている辞書型は4つしか項目がありませんが、項目が増えれば増えるほど、項目を探すための計算量が大きくなってしまいます。

-+-------------------+
0|{"Tarou": "male"}  |
-+-------------------+
1|{"John": "male"}   |
-+-------------------+
2|{"Chika": "female"}|
-+-------------------+
3|{"Jane": "female"} |
-+-------------------+

そこで、計算量を減らすためのアイデアを導入します。辞書に項目を追加する際に、格納する位置をキーをハッシュ関数を利用して計算した値を利用して決定することにします。 (ここでは仮に以下のような結果になったと想定します。キー→格納位置 "Tarou"→0, "John"→1, "Jane"→3, "Chica"→"5", "Yuta"→7)

-+-------------------+
0|{"Tarou": "male"}  |
-+-------------------+
1|{"John": "male"}   |
-+-------------------+
2|                   |
-+-------------------+
3| {"Jane": "female"}|
-+-------------------+
4|                   |
-+-------------------+
5|{"Chika": "female"}|
-+-------------------+
6|                   |
-+-------------------+
7|{"Yuta": "male"}   |
-+-------------------+

人間が見ると穴ぼこだらけで不自然なテーブルに見えますが、プログラム上では扱いやすい形になっています。というのは、例えば"Yuta"がキーになっている項目を取得したい場合、再度ハッシュ関数を利用して格納されている位置を計算すれば、取得した格納位置に直接アクセスすることができるようになるためです。

格納位置を計算   "Yuta" → 7 


                -+-------------------+
直接アクセス→    7|{"Yuta": "male"}   |
                -+-------------------+

この方法なら、項目数が1つでも、10000あっても、同じ計算量で項目を探すことができるため、計算量の節約になるのです。このようなデータ構造をハッシュテーブルと呼ぶようです。

PythonのHash()関数

Pythonの話に戻ると、辞書型のキーからハッシュ値を計算する際、自動的にhash(キーオブジェクト)が実行されます。 hash()は暗黙的に対象のオブジェクトの __hash__() メソッドを実行します。そのため、 __hash__() が実装されていないオブジェクトは辞書型のキーとして扱うことができないのです。また、 __eq__ で等しいと判定されるようなオブジェクトの場合、 __hash__ メソッドの結果も同じになるように実装しないといけません。

値オブジェクトはdataclassを使った方が良さそう

これまで演算子のオーバーライドについて色々と説明してきましたが、Python 3.7から導入されたdataclassesを利用すると、 __eq__ , __hash__ などの再定義を自動的に行ってくれるようです。

from dataclasses import dataclass
  
@dataclass(frozen=True)
class Money:
    amount: int = 0 # インスタンス変数の型とデフォルト値を設定
    currency: str = "JPY"
  
  
a = Money(amount=1)
b = Money(amount=1)
  
# __eq__()を再定義しなくても、==で比較可能になっている
assert a == b

使い方は上記のように@dataclassデコレータをclass定義の際に利用します。 dataclassを利用すると、自分で __eq__ を実装しなくても、インスタンスヘンスの値(今回の場合amountとcurrency)が同じなら同じものとして判断されるようです。

__hash__ , __str__ に関しても同様で、自動的に実装されるようです。

@dataclass(frozen=True)
class Pair:
    source: str
    to: str
  
a = Pair("JPY", "USD")
b = Pair("JPY", "USD")
  
assert a == b
  
pair_dict = {}
pair_dict[a] = 1
assert pair_dict[b] == 1 
# 同じ値のオブジェクトなら、同じ辞書のキーとして使える
  
print(a)
# Pair(source='JPY', to='USD') 
# __str__()を再定義しなくても綺麗に出力してくれる