Jak zaimplementować haszowanie zmiennoprzecinkowe z przybliżoną równością

Powiedzmy, że mamy następującą klasę Python (problem istnieje w Javie tak samo z equalsi hashCode)

class Temperature:
    def __init__(self, degrees):
        self.degrees = degrees

gdzie degreesjest temperatura w kelwinach jako liczba zmiennoprzecinkowa. Teraz chciałbym wdrożyć testy równości i mieszanie Temperaturew 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 == bimplikuje hash(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ę?

wdrożyć testy równości i mieszanie dla Temperatury w sposób, który porównuje wartości zmienne do różnicy epsilon zamiast bezpośrednich testów równości,

Rozmyta równość narusza wymagania, które Java stawia wobec equalsmetody, a mianowicie przechodniość , tzn. Że jeśli x == yi y == zwtedy x == z. Ale jeśli robisz rozmytą równość, na przykład z epsilonem 0,1, wtedy 0.1 == 0.2i 0.2 == 0.3, ale 0.1 == 0.3nie 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).

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.

1. Dla każdego z dwóch punktów w epsilon od siebie, które nie mają tej samej wartości skrótu.

   • Dostosuj schemat mieszania, aby te dwa punkty miały taką samą wartość.
2. Indukując dla wszystkich takich par, cała sekwencja liczb zmiennoprzecinkowych zwinie się w kierunku pojedynczej wartości.

Jest kilka przypadków, w których nie będzie to prawdą:

• Pozytywna / negatywna nieskończoność
• NaN
• Kilka zdenormalizowanych zakresów, które mogą nie być powiązane z głównym zakresem dla danego epsilonu.
• być może kilka innych wystąpień specyficznych dla formatu

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:

[0.001, 0.002)
[0.002, 0.003)
[0.003, 0.004)
...
[122.999, 123.000)
...

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.

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!

#Pseudo code
class Temperature:
    def __init__(self, degrees):
        #CHECK INVALID VALUES HERE
        #TRANSFORM TO KELVIN HERE
        self.degrees = Math.floor(kelvin/EPSILON)

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:

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

2. 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,

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

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*√2da 2zamiast 2.00000001lub podobnie. Oczywiście wprowadzi to dodatkowe komplikacje, które mogą, ale nie muszą być tego warte.