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

15

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

Kuna
źródło
9
dlaczego pytanie ma tag Java?
Laiv
8
O twojej aktualizacji: Powiedziałbym, że hashowanie jest ogólnie wątpliwe. Staraj się unikać używania pływaków jako kluczy lub elementów zestawu.
J. Fabian Meier
6
@Neil: Jednocześnie zaokrąglanie nie brzmi jak liczby całkowite? Rozumiem przez to: jeśli możesz zaokrąglić do, powiedzmy, tysięcznych stopni, to możesz po prostu użyć reprezentacji punktu stałego - liczby całkowitej wyrażającej temperaturę w tysięcznych stopniach. Dla łatwości użycia, możesz mieć getter / seter transparentnie konwertujący z / do floatów, jeśli chcesz ...
Matthieu M.
4
Kelwiny nie są już stopniami. Stopnie są również niejednoznaczne. Dlaczego nie po prostu to nazwać kelvin?
Solomon Ucko
5
Python ma mniej więcej doskonałą obsługę punktu stałego , może to coś dla Ciebie.
Jonas Schäfer

Odpowiedzi:

41

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

Sebastian Redl
źródło
2
ciekawe myśli. Tak więc, gromadząc miliony epsilonów i przechodząc, można wnioskować, że wszystko jest równe cokolwiek innego :-) Ale czy to matematyczne ograniczenie uznaje dyskretne podstawy zmiennoprzecinkowe, które w wielu przypadkach są przybliżeniami liczby, którą mają reprezentować?
Christophe
@Christophe Interesujące pytanie. Jeśli się nad tym zastanowisz, zobaczysz, że takie podejście utworzy jedną dużą klasę równoważności z liczb zmiennoprzecinkowych, których rozdzielczość jest większa niż epsilon (oczywiście jest wyśrodkowana na 0), i pozostawi pozostałe zmiennoprzecinkowe we własnej klasie. Ale nie o to chodzi, prawdziwy problem polega na tym, że to, czy stwierdzi, że 2 liczby są równe, zależy od tego, czy istnieje trzecia porównywana liczba i kolejność, w jakiej to się robi.
Ordous
Odnosząc się do edycji @ OP, dodałbym, że niepoprawność zmiennoprzecinkowa ==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ć.
HTNW,
@HTNW: To byłoby zbyt proste. Klasa współczynnika może mieć float approximationpole, 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 jest floattypem.
MSalters
@MSalters? Przypuszczalnie wystarczająco konfigurowalne narzędzia do analizy statycznej mogą zrobić to, co zasugerowałem. Jeśli klasa ma floatpole, 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ą.
HTNW
16

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.

Kain0_0
źródło
2
Zgadzam się, że podejście granularne byłoby prawdopodobnie najlepsze, gdyby spełniało wymagania OP. Chociaż obawiam się, że OP ma wymagania dotyczące +/- 0,1%, co oznacza, że ​​nie może być szczegółowy.
Neil
4
@DocBrown Część „niemożliwa” jest poprawna. Jeśli równość oparta na epsilon powinna sugerować, że kody skrótu są równe, automatycznie wszystkie kody skrótu są równe, więc funkcja skrótu nie jest już użyteczna. Podejście do segmentów może być owocne, ale będziesz mieć liczby z różnymi kodami skrótu, które są dowolnie blisko siebie.
J. Fabian Meier
2
Podejście kubełkowe można zmodyfikować, sprawdzając nie tylko wiadro z dokładnym kluczem skrótu, ale także dwa sąsiednie wiadra (lub co najmniej jedno z nich) pod kątem ich zawartości. Eliminuje to problem tych przypadków skrajnych związanych z kosztem wydłużenia czasu działania co najwyżej dwa razy (przy prawidłowym wdrożeniu). Nie zmienia to jednak ogólnej kolejności czasu pracy.
Doc Brown
Kiedy masz rację w duchu, nie wszystko się zawali. Przy stałym małym epsilonie większość liczb będzie się równała. Oczywiście dla tych epsilon będzie bezużyteczny, więc ponownie, w duchu masz rację.
Carsten S,
1
@CarstenS Tak, moje stwierdzenie, że 99% mieszania zakresu do jednego skrótu nie obejmuje w rzeczywistości całego zakresu zmiennoprzecinkowego. Istnieje wiele wartości wysokiego zakresu, które są oddzielone przez więcej niż epsilon, który będzie mieszał się z własnymi unikatowymi segmentami.
Kain0_0
7

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)
Alessandro Teruzzi
źródło
1

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,

supercat
źródło
0

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

gnasher729
źródło
0

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.

BurnsBA
źródło