Co się dzieje, gdy wywołasz `if key in dyict`

Question

Mam klasę (nazwijmy ją myClass), która implementuje zarówno __hash__, jak i __eq__. Mam także dict, który odwzorowuje obiekty o wartościach, które wymagają trochę czasu.

W trakcie trwania mojego programu tworzy się wiele obiektów (rzędu milionów) myClass. Dlatego używam dict do śledzenia tych wartości.

Jednak czasami nowy obiekt myClass może być równoważny ze starszym (zgodnie z metodą __eq__). Więc zamiast obliczać wartość dla tego obiektu, wolę po prostu sprawdzić wartość starszego obiektu myClass w dict. Aby to osiągnąć, wykonuję if myNewMyClassObj in dict.

Oto moje pytanie:

Kiedy używam tego in klauzuli, co jest wywoływana, __hash__ lub __eq__? Punktem użycia dict jest to, że jest to czas wyszukiwania O (1). Tak więc musi zostać wywołany __hash__. Ale co, jeśli __hash__ i __eq__ nie są równorzędne metody? W takim przypadku, czy otrzymam fałszywy alarm za if myNewMyClassObj in dict?

Kontynuacja pytanie:

Chcę, aby zminimalizować liczbę wpisów w moim dict, więc chciałbym idealnie chce zachować tylko jeden zestaw równoważnych myClass obiektów w dict. Ponownie więc, wydaje się, że __eq__ musi być wywoływana podczas obliczania if myNewClassObj in dict, co kala O dict „S (1) Czas wyszukiwania do O (N) Czas wyszukiwania

Answer 1

Najpierw wywołuje się . Jeśli w słowniku nie znaleziono obiektu o tym samym haszu, Python przyjmuje, że myNewMyClassObj nie znajduje się w słowniku. (Zauważ, że Python wymaga, że ​​ilekroć __eq__ ocenia jako równe dla dwóch obiektów, ich __hash__ muszą być identyczne).

Jeśli niektóre obiekty z tej samej __hash__ znajdują się w słowniku, __eq__ jest wywoływana na każdym z nich. Jeśli wartość __eq__ jest równa jakiemukolwiek z nich, myNewMyClassObj in dict_ zwraca wartość True.

W ten sposób wystarczy upewnić się, że oba __eq__ i __hash__ są szybkie.

Na pytanie uzupełniające: tak, dict_ przechowuje tylko jeden z zestawu równoważnych obiektów MyClass (zgodnie z definicją __eq__). (Zgodnie z ustawieniem).

Należy pamiętać, że __eq__ jest wywoływany tylko na obiektach, które miały ten sam skrót i zostały przydzielone do tego samego zasobnika. Liczba takich obiektów jest zwykle bardzo mała (pewnie to zapewnia implementacja dict). Więc nadal masz (w przybliżeniu) wydajność wyszukiwania.

Answer 2

__hash__ zawsze będzie nazywany; __eq__ zostanie wywołany, jeśli obiekt rzeczywiście znajduje się w słowniku lub jeśli w słowniku znajduje się inny obiekt o tym samym haszowaniu. Wartość skrótu służy do zawężenia wyboru możliwych kluczy. Klucze są pogrupowane w "segmenty" według wartości mieszania, ale w przypadku wyszukiwania Python wciąż musi sprawdzić każdy klucz w wiadrze, aby uzyskać równość z kluczem wyszukiwania. Zobacz http://wiki.python.org/moin/DictionaryKeys. Spójrz na te przykłady:

>>> 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 

W tym przykładzie widać __hash__ jest zawsze nazywany. __eq__ jest wywoływana raz dla każdego wyszukiwania, gdy obiekt znajduje się w dykcie, ponieważ wszystkie mają oddzielne wartości mieszania, więc jedna kontrola równości jest wystarczająca do sprawdzenia, czy obiekt z tą wartością mieszającą jest rzeczywiście tą, której dotyczy zapytanie. __eq__ nie jest wywoływany w ostatnim przypadku, ponieważ żaden z obiektów w dykcie nie ma tej samej wartości skrótu co Foo(4), więc Python nie musi kontynuować z __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 

W tej wersji wszystkie obiekty mają tę samą wartość skrótu. W tym przypadku __eq__ jest zawsze wywoływane, czasami wiele razy, ponieważ hash nie rozróżnia wartości, więc Python musi jawnie sprawdzić równość względem wszystkich wartości w dyktafonie, dopóki nie znajdzie równego (lub stwierdzi, że żaden z nich nie jest równy ten, którego szuka). Czasem znajduje to przy pierwszej próbie (Foo(1) in dict powyżej), czasami musi sprawdzić wszystkie wartości.

Answer 3

__hash__ definiuje wiadro, w którym umieszczany jest obiekt, __eq__ zostaje wywołany tylko wtedy, gdy obiekty znajdują się w tym samym wiadrze.