Hash dla funkcji lambda w Pythonie

Question

Próbuję uzyskać skrót funkcji lambda. Dlaczego otrzymuję dwie wartości (8746164008739 i -9223363290690767077)? Dlaczego skrót z funkcji lambda nie zawsze jest jedną wartością?

>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 
>>> fn = lambda: 1 
>>> hash(fn) 
8746164008739 
>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 
>>> fn = lambda: 1 
>>> hash(fn) 
8746164008739 
>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 

Answer 1

Nie można zagwarantować, że dwa obiekty będą miały taką samą wartość, chyba że będą porównywać równe [1].

Funkcje języka Python (w tym lambdy) nie są równe, nawet jeśli mają identyczny kod [2]. Na przykład:

>>> (lambda: 1) == (lambda: 1) 
False 

Wdrożenie to zachowanie wynika z faktu, że obiekty funkcji nie zapewniają własnego operatora równości. Zamiast tego dziedziczą domyślną, która używa tożsamości obiektu, tj. Jego adresu. Od documentation:

Jeśli nie __cmp__(), __eq__() lub __ne__() eksploatacja jest określona, ​​klasa przypadki są porównywane przez tożsamość obiektu („adres”).

Oto, co dzieje się w danym przykładzie:

fn = lambda: 1 # New function is allocated at address A and stored in fn. 
fn = lambda: 1 # New function is allocated at address B and stored in fn. 
       # The function at address A is garbage collected. 
fn = lambda: 1 # New function is allocated at address A and stored in fn. 
       # The function at address B is garbage collected. 
fn = lambda: 1 # New function is allocated at address B and stored in fn. 
       # The function at address A is garbage collected. 
... 

Ponieważ adres A zawsze jest mieszany do jednej wartości, a zająć B do drugiego, widzisz hash(fn) zastępcę pomiędzy tymi dwiema wartościami. To naprzemienne zachowanie jest jednak artefaktem implementacji i może zmienić jeden dzień, jeśli na przykład, garbage collector będzie zachowywał się nieco inaczej.

Poniższy wnikliwa uwaga zostało wniesione przez @ruakh:

Warto zauważyć, że nie jest możliwe, aby napisać ogólny proces określania, czy dwie funkcje są równoważne. (Jest to konsekwencją undecidability z halting problem.) Ponadto dwie funkcje Python może zachowywać się inaczej, nawet jeśli ich kod jest identyczna (ponieważ mogą one być zamknięcia nawiązujące do odrębny-but-identycznie nazwanych zmiennych). Ma więc sens, że funkcje Pythona nie przeciążają operatora równości: nie ma możliwości, aby zaimplementować coś lepszego niż domyślne porównanie obiektu.

[1] Odwrotność na ogół nie jest prawdziwa: dwa obiekty, które nie mają sobie równych, mogą mieć tę samą wartość skrótu. Nazywa się to hash collision.

[2] Wywołanie swoje lambdy a następnie mieszania wynik byłby oczywiście zawsze dają taką samą wartość, ponieważ hash(1) jest zawsze taka sama w obrębie jednego programu:

>>> (lambda: 1)() == (lambda: 1)() 
True 

Answer 2

hash obiektu lambda funkcją jest na podstawie jego adresu pamięci (w CPython jest to, co zwraca funkcja id). Oznacza to, że dowolne dwa obiekty funkcji będą miały różne wartości skrótów (zakładając, że nie ma kolizji mieszania), nawet jeśli funkcje zawierają ten sam kod.

Aby wyjaśnić, co dzieje się w pytaniu, najpierw zauważ, że pisanie fn = lambda: 1 tworzy nowy obiekt funkcji w pamięci i wiąże z nim nazwę fn. Ta nowa funkcja będzie miała zatem inną wartość skrótu do wszystkich istniejących funkcji.

Powtarzanie fn = lambda: 1, można się na przemian wartości dla mieszań bo gdy fn jest związany z nowo utworzonego obiektu funkcji, funkcji, które fnwcześniej wskazał na śmieci jest zebrane przez Pythona. Jest tak, ponieważ nie ma już żadnych odniesień do niego (ponieważ nazwa fn wskazuje teraz na inny obiekt).

Interpreter Pythona następnie wykorzystuje ten stary adres pamięci dla następnego nowego obiektu funkcji utworzonego przez zapisanie fn = lambda: 1.

To zachowanie może się różnić w zależności od systemu i implementacji w języku Python.

Answer 3

Za każdym razem, gdy robisz fn = lambda: 1, tworzony jest nowy obiekt funkcji, a stary obiekt powiązany z nazwą fn jest oznaczony do usunięcia. Ale Python nie tylko zwalnia obiekt, przekazując jego pamięć do systemu operacyjnego. Aby zminimalizować wywołania systemowe dla alokacji pamięci i zminimalizować fragmentację pamięci Python próbuje odzyskać pamięć, kiedy tylko może. Tak więc po utworzeniu fn = lambda: 1 po raz trzeci interpreter zauważa, że ​​ma blok pamięci podręcznej, który jest wystarczająco duży dla nowego obiektu funkcji, i dlatego używa tego bloku. I tak twój trzeci fn kończy się w tym bloku pamięci RAM, a więc ma ten sam identyfikator co pierwszy fn, ponieważ id obiektów CPython jest ich adresem pamięci.

(Jak wspominają inni hash dowolnego typu obiektu, który nie przewiduje specyficzny realizacja __hash__ oparty jest na identyfikatorze w CPython. A jeśli klasa nie definiuje metodę __cmp__ lub __eq__ nie należy zdefiniować __hash__ operacja też).

Answer 4

Podejmowanie decyzji, czy dwie funkcje są równe, jest niemożliwe, ponieważ stanowi nadzbiór problemu zatrzymania.

W idealnym świecie porównanie funkcji (i tym samym mieszania) spowodowałoby błąd typu. Python najwyraźniej tego nie lubi, a zamiast tego decyduje się użyć tożsamości funkcji do porównywania (a zatem i mieszania) ich.