6

myClassと の両方を実装するクラス ( と呼びましょう) が__hash__あり__eq__ます。また、オブジェクトを何らかの値にdictマップする もありmyClass、計算には時間がかかります。

私のプログラムの過程で、多くの (数百万のオーダー)myClassオブジェクトがインスタンス化されます。これがdict、これらの値を追跡するために を使用する理由です。

ただし、新しいmyClassオブジェクトが古いオブジェクトと同等である場合があります (__eq__メソッドで定義されているように)。そのため、そのオブジェクトの値を再度計算するのではなくmyClass、dict. これを達成するために、私はしますif myNewMyClassObj in dict。

これが私の質問です：

そのin句を使用すると、何が呼び出されますか、__hash__または__eq__? a を使用するポイントは、dictO(1) ルックアップ時間であることです。したがって、__hash__呼び出される必要があります。しかし、__hash__と__eq__が同等のメソッドではない場合はどうなるでしょうか? その場合、偽陽性になりif myNewMyClassObj in dictますか?

フォローアップの質問:

のエントリの数を最小限に抑えたいdictので、理想的には、一連の同等のmyClassオブジェクトの 1 つだけをdict. 繰り返しますが、 を__eq__計算するときに を呼び出す必要があるようです。これにより、 aの O(1) ルックアップ時間が O(n) ルックアップ時間にif myNewClassObj in dict汚されます。dict

4

3 に答える 3

8

まず、__hash__(myNewMyClassObj)呼び出されます。同じハッシュを持つオブジェクトがディクショナリに見つからない場合、Python はディクショナリにmyNewMyClassObjないものと見なします。(Python では、__eq__2 つのオブジェクトが等しいと評価される場合は常に、それら__hash__が同一でなければならないことに注意してください。)

ディクショナリ内に同じオブジェクト__hash__が見つかった場合__eq__、それぞれに対して が呼び出されます。__eq__いずれかが等しいと評価された場合、はmyNewMyClassObj in dict_True を返します。

__eq__したがって、との両方が高速であることを確認する必要があります__hash__。

フォローアップの質問: はい、dict_同等のオブジェクトのセットの 1 つだけを格納しMyClassます (によって定義されています__eq__)。（設定どおりです。）

__eq__同じハッシュを持ち、同じバケットに割り当てられたオブジェクトでのみ呼び出されることに注意してください。そのようなオブジェクトの数は、通常、非常に少数です (dict実装によって確認されます)。したがって、(大まかに)O(1)ルックアップのパフォーマンスは維持されます。

于 2012-10-21T20:38:58.563 に答える
7

__hash__常に呼び出されます。__eq__オブジェクトが実際に辞書にある場合、または同じハッシュを持つ別のオブジェクトが辞書にある場合に呼び出されます。ハッシュ値は、可能なキーの選択肢を絞り込むために使用されます。キーはハッシュ値によって「バケット」にグループ化されますが、ルックアップの場合、Python はバケット内の各キーがルックアップ キーと等しいかどうかをチェックする必要があります。http://wiki.python.org/moin/DictionaryKeysを参照してください。これらの例を見てください:

>>> class Foo(object):
...     def __init__(self, x):
...         self.x = x
...     
...     def __hash__(self):
...         print "Hash"
...         return hash(self.x)
... 
...     def __eq__(self, other):
...         print "Eq"
...         return self.x == other.x
>>> Foo(1) in d
Hash
Eq
10: True
>>> Foo(2) in d
Hash
Eq
11: True
>>> Foo(3) in d
Hash
Eq
12: True
>>> Foo(4) in d
Hash
13: False

__hash__その例では、が常に呼び出され ていることがわかります。__eq__オブジェクトが dict にある場合、ルックアップごとに 1 回呼び出されます。それらはすべて異なるハッシュ値を持っているため、そのハッシュ値を持つオブジェクトが実際にクエリされているオブジェクトであることを確認するには、1 つの等価チェックで十分です。 __eq__dict 内のオブジェクトのいずれも と同じハッシュ値を持たないため、最後のケースでは呼び出されFoo(4)ません。そのため、Python は__eq__.

>>> class Foo(object):
...     def __init__(self, x):
...         self.x = x
...     
...     def __hash__(self):
...         print "Hash"
...         return 1
... 
...     def __eq__(self, other):
...         print "Eq"
...         return self.x == other.x
>>> d = {Foo(1): 2, Foo(2): 3, Foo(3): 4}
Hash
Hash
Eq
Hash
Eq
Eq
>>> Foo(1) in d
Hash
Eq
18: True
>>> Foo(2) in d
Hash
Eq
Eq
19: True
>>> Foo(3) in d
Hash
Eq
Eq
Eq
20: True
>>> Foo(4) in d
Hash
Eq
Eq
Eq
21: False

このバージョンでは、すべてのオブジェクトが同じハッシュ値を持ちます。この場合__eq__、ハッシュは値を区別しないため、常に呼び出され、複数回呼び出されることもあります。そのため、Python は、等しい値が見つかるまで (またはそれらのいずれもが探しているもの)。最初の試行 (上記) で見つかる場合もあれFoo(1) in dictば、すべての値をチェックする必要がある場合もあります。

于 2012-10-21T20:38:06.787 に答える
1

__hash__ はオブジェクトが置かれるバケットを定義し、__eq__ はオブジェクトが同じバケットにある場合にのみ呼び出されます。

于 2012-10-21T20:38:07.597 に答える