Powiedzmy, że mamy następującą klasę Python (problem istnieje w Javie tak samo z equals
i hashCode
)
class Temperature:
def __init__(self, degrees):
self.degrees = degrees
gdzie degrees
jest temperatura w kelwinach jako liczba zmiennoprzecinkowa. Teraz chciałbym wdrożyć testy równości i mieszanie Temperature
w taki sposób
- porównuje wartości zmienne do różnicy epsilon zamiast bezpośrednich testów równości,
- i honoruje umowę, która
a == b
implikujehash(a) == hash(b)
.
def __eq__(self, other):
return abs(self.degrees - other.degrees) < EPSILON
def __hash__(self):
return # What goes here?
Dokumentacja Pythona mówi trochę o liczbach mieszających, aby się upewnić, hash(2) == hash(2.0)
ale nie jest to ten sam problem.
Czy w ogóle jestem na dobrej drodze? A jeśli tak, to jaki jest standardowy sposób implementacji haszowania w tej sytuacji?
Aktualizacja : Teraz rozumiem, że ten rodzaj testowania równości dla liczb zmiennoprzecinkowych eliminuje przechodniość ==
i equals
. Ale jak to idzie w parze z „powszechną wiedzą”, że pływa, nie należy bezpośrednio porównywać? Jeśli zaimplementujesz operator równości poprzez porównanie liczb zmiennoprzecinkowych, narzędzia analizy statycznej będą narzekać. Czy mają rację?
kelvin
?Odpowiedzi:
Rozmyta równość narusza wymagania, które Java stawia wobec
equals
metody, a mianowicie przechodniość , tzn. Że jeślix == y
iy == z
wtedyx == z
. Ale jeśli robisz rozmytą równość, na przykład z epsilonem 0,1, wtedy0.1 == 0.2
i0.2 == 0.3
, ale0.1 == 0.3
nie ma.Podczas gdy Python nie dokumentuje takiego wymogu, nadal implikacje posiadania nieprzechodniczej równości sprawiają, że jest to bardzo zły pomysł; rozumowanie o takich typach powoduje ból głowy.
Dlatego zdecydowanie nie polecam tego.
Albo zapewnij dokładną równość i oprzyj na niej swój skrót w oczywisty sposób, i zapewnij oddzielną metodę wykonywania rozmytego dopasowania, lub zastosuj podejście klasy równoważności sugerowane przez Kaina. Chociaż w tym drugim przypadku zalecam, abyś poprawił swoją wartość do reprezentatywnego elementu klasy równoważności w konstruktorze, a następnie poszedł z prostą dokładną równością i mieszaniem dla reszty; w ten sposób o wiele łatwiej jest uzasadnić typy.
(Ale jeśli to zrobisz, równie dobrze możesz użyć reprezentacji punktu stałego zamiast zmiennoprzecinkowego, tj. Użyjesz liczby całkowitej do zliczenia tysięcznych stopnia lub jakiejkolwiek wymaganej precyzji).
źródło
==
powinna „zainfekować”==
typy je zawierające. Oznacza to, że jeśli postępują zgodnie z twoją radą, by zapewnić dokładną równość, to ich narzędzie do analizy statycznej powinno być skonfigurowane tak, aby ostrzegało, gdy używana jest równośćTemperature
. To jedyna rzecz, którą możesz naprawdę zrobić.float approximation
pole, w którym nie uczestniczy==
. Poza tym narzędzie do analizy statycznej już ostrzega wewnątrz==
implementacji klas, gdy jeden z porównywanych elementów jestfloat
typem.float
pole, w którym nie uczestniczy==
, nie konfiguruj swojego narzędzia, aby ostrzegało==
. Jeśli klasa to zrobi, przypuszczalnie oznaczenie klasy==
jako „zbyt dokładnej” spowoduje, że narzędzie zignoruje tego rodzaju błąd w implementacji. Np. W Javie, jeśli@Deprecated void foo()
,void bar() { foo(); }
to ostrzeżenie, ale@Deprecated void bar() { foo(); }
nie jest. Być może wiele narzędzi tego nie obsługuje, ale niektóre mogą.Powodzenia
Nie będziesz w stanie tego osiągnąć bez głupoty z haszowaniem lub poświęcenia epsilonu.
Przykład:
Załóżmy, że każdy punkt ma własną wartość skrótu.
Ponieważ liczby zmiennoprzecinkowe są sekwencyjne, będzie istniało do k liczb przed daną wartością zmiennoprzecinkową i do k liczb po danej wartości zmiennoprzecinkowej, które mieszczą się w pewnym epsilonie danego punktu.
Dla każdego z dwóch punktów w epsilon od siebie, które nie mają tej samej wartości skrótu.
Jest kilka przypadków, w których nie będzie to prawdą:
Jednak> = 99% zakresu zmiennoprzecinkowego będzie mieszać się z pojedynczą wartością dla dowolnej wartości epsilon, która zawiera co najmniej jedną wartość zmiennoprzecinkową powyżej lub poniżej określonej wartości zmiennoprzecinkowej.
Wynik
Albo> = 99% całego zakresu zmiennoprzecinkowego hashuje do pojedynczej wartości, co poważnie kompromituje zamiar wartości skrótu (i dowolnego urządzenia / kontenera opartego na dość rozproszonym haszu o niskiej kolizji).
Lub epsilon jest taki, że dozwolone są tylko dokładne dopasowania.
Ziarnisty
Zamiast tego możesz oczywiście zastosować bardziej szczegółowe podejście.
W ramach tego podejścia definiujesz dokładne segmenty do określonej rozdzielczości. to znaczy:
Każde wiadro ma unikatowy skrót, a każdy zmiennoprzecinkowy element w porównaniu z każdym zmiennoprzecinkowym w tym samym segmencie.
Niestety nadal możliwe jest, aby dwa pływaki były w odległości epsilon i miały dwa oddzielne skróty.
źródło
Możesz modelować swoją temperaturę jako liczbę całkowitą pod maską. Temperatura ma naturalną dolną granicę (-273,15 Celsjusza). Zatem podwójne (-273,15 jest równe 0 dla podstawowej liczby całkowitej). Drugim niezbędnym elementem jest szczegółowość mapowania. Już używasz tej ziarnistości pośrednio; to twój EPSILON.
Po prostu podziel swoją temperaturę przez EPSILON i zabierz głos, teraz twój hash i równy będą się synchronizować. W Pythonie 3 liczba całkowita jest nieograniczona, EPSILON może być mniejszy, jeśli chcesz.
UWAGA: Jeśli zmienisz wartość EPSILON i zserializujesz obiekt, nie będą one kompatybilne!
źródło
Implementacja zmiennoprzecinkowej tabeli mieszającej, która może znaleźć rzeczy, które są „w przybliżeniu równe” danemu kluczowi, będzie wymagać zastosowania kilku podejść lub ich kombinacji:
Zaokrąglij każdą wartość do przyrostu, który jest nieco większy niż zakres „rozmytego” przed zapisaniem jej w tabeli skrótów, a podczas próby znalezienia wartości sprawdź, czy w tablicy skrótów nie ma zaokrąglonych wartości powyżej i poniżej żądanej wartości.
Przechowuj każdy element w tabeli skrótów za pomocą kluczy, które są powyżej i poniżej żądanej wartości.
Zauważ, że użycie któregokolwiek z tych podejść będzie prawdopodobnie wymagało, aby wpisy w tablicy skrótów nie identyfikowały elementów, ale raczej listy, ponieważ prawdopodobnie będzie wiele elementów powiązanych z każdym kluczem. Pierwsze powyższe podejście zminimalizuje wymagany rozmiar tabeli skrótów, ale każde wyszukiwanie elementu spoza tabeli będzie wymagało dwóch odnośników tablicy skrótów. Drugie podejście będzie w stanie szybko stwierdzić, że elementów nie ma w tabeli, ale ogólnie wymaga, aby tabela zawierała około dwa razy więcej wpisów, niż byłoby to wymagane. Jeśli ktoś próbuje znaleźć obiekty w przestrzeni 2D, przydatne może być zastosowanie jednego podejścia dla kierunku X i jednego dla kierunku Y, aby zamiast mieć każdy element zapisany jeden raz, ale wymagając czterech operacji zapytania dla każdego wyszukiwania lub móc użyć jednego wyszukiwania, aby znaleźć element, ale trzeba przechowywać każdy element cztery razy,
źródło
Możesz oczywiście zdefiniować „prawie równy”, usuwając powiedz ostatnie osiem bitów mantysy, a następnie porównując lub mieszając. Problem polega na tym, że liczby bardzo blisko siebie mogą się różnić.
Jest tu pewne zamieszanie: jeśli dwie liczby zmiennoprzecinkowe są równe, są one równe. Aby sprawdzić, czy są równe, użyj „==”. Czasami nie chcesz sprawdzać równości, ale kiedy to robisz, „==” jest właściwą drogą.
źródło
To nie jest odpowiedź, ale rozszerzony komentarz, który może być pomocny.
Pracowałem nad podobnym problemem podczas korzystania z MPFR (opartego na GNU MP). Podejście „kubełkowe” przedstawione przez @ Kain0_0 wydaje się dawać akceptowalne wyniki, ale należy pamiętać o ograniczeniach podkreślonych w tej odpowiedzi.
Chciałem dodać, że - w zależności od tego, co próbujesz zrobić - użycie systemu algebry komputerowej „dokładnego” ( emptora zastrzeżenia ), takiego jak Mathematica, może pomóc uzupełnić lub zweryfikować niedokładny program numeryczny. Umożliwi to obliczenie wyników bez obawy o zaokrąglenie, na przykład
7*√2 - 5*√2
da2
zamiast2.00000001
lub podobnie. Oczywiście wprowadzi to dodatkowe komplikacje, które mogą, ale nie muszą być tego warte.źródło