Implementierung von Float-Hashing mit ungefährer Gleichheit

15

Nehmen wir an, wir haben die folgende Python-Klasse (das Problem existiert in Java genauso mit equalsund hashCode)

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

Wo degreesist die Temperatur in Kelvin als Schwimmer. Nun würde Ich mag Gleichheit Prüfung und Hashing implementieren Temperaturein einer Weise , dass

  • vergleicht Floats mit einer Epsilon-Differenz anstatt direkter Gleichheitsprüfung,
  • und hält den Vertrag ein, der a == bimpliziert hash(a) == hash(b).
def __eq__(self, other):
    return abs(self.degrees - other.degrees) < EPSILON

def __hash__(self):
    return # What goes here?

In der Python-Dokumentation wird ein wenig über das Hashing von Zahlen gesprochen, um sicherzustellen, dass hash(2) == hash(2.0)dies nicht ganz dasselbe Problem ist.

Bin ich überhaupt auf dem richtigen Weg? Und wenn ja, wie wird Hashing in dieser Situation standardmäßig implementiert?

Update : Jetzt verstehe ich, dass diese Art der Gleichheitsprüfung für Schwimmer die Transitivität von ==und beseitigt equals. Aber wie passt das zu dem "Allgemeinwissen", dass Schwimmkörper nicht direkt miteinander verglichen werden sollten? Wenn Sie einen Gleichheitsoperator durch Vergleichen von Floats implementieren, beklagen sich statische Analysetools. Haben sie Recht dazu?

Marder
quelle
9
Warum hat die Frage Javas Tag?
Laiv,
8
Zu Ihrem Update: Ich würde sagen, dass das Hasching von Floats generell eine fragwürdige Sache ist. Vermeiden Sie die Verwendung von Floats als Schlüssel oder als Set-Elemente.
J. Fabian Meier
6
@Neil: Klingt das Runden nicht gleichzeitig wie Ganzzahlen? Damit meine ich: Wenn Sie beispielsweise auf Tausendstel Grad runden können, könnten Sie einfach eine Festkommadarstellung verwenden - eine ganze Zahl, die die Temperatur in Tausendstel Grad ausdrückt. Zur Vereinfachung der Verwendung könnten Sie einen Getter / Setter haben, der transparent von / zu Floats konvertiert, wenn Sie möchten ...
Matthieu M.
4
Kelvin sind keine Grad mehr. Grad sind auch mehrdeutig. Warum nicht einfach anrufen kelvin?
Solomon Ucko
5
Python bietet mehr oder weniger exzellente Festkomma-Unterstützung , vielleicht ist das etwas für Sie.
Jonas Schäfer

Antworten:

41

Implementieren von Gleichheitstests und Hashing für die Temperatur in einer Weise, die Schwebungen mit einer Epsilon-Differenz vergleicht, anstatt direkte Gleichheitstests durchzuführen.

Die Fuzzy-Gleichheit verletzt die Anforderungen, die Java an die equalsMethode stellt, nämlich die Transitivität , dh wenn x == yund y == zdann x == z. Aber wenn Sie eine Fuzzy-Gleichheit mit zum Beispiel einem Epsilon von 0,1 machen, dann gilt 0.1 == 0.2und 0.2 == 0.3, aber 0.1 == 0.3nicht.

Obwohl Python eine solche Anforderung nicht dokumentiert, machen die Auswirkungen einer nicht-transitiven Gleichheit diese Idee dennoch sehr schlecht. Über solche Typen nachzudenken ist kopfschmerzerregend.

Deshalb empfehle ich Ihnen dringend, das nicht zu tun.

Stellen Sie entweder eine exakte Gleichheit bereit und stützen Sie Ihren Hash auf die offensichtliche Weise darauf, und stellen Sie eine separate Methode für das Fuzzy-Matching bereit, oder wählen Sie den von Kain vorgeschlagenen Ansatz für die Äquivalenzklasse. In letzterem Fall empfehle ich, dass Sie Ihren Wert auf ein repräsentatives Mitglied der Äquivalenzklasse im Konstruktor festlegen und dann mit einfacher exakter Gleichheit und Hashing fortfahren. Es ist viel einfacher, auf diese Weise über die Typen nachzudenken.

(Aber wenn Sie das tun, können Sie auch eine Festkomma-Darstellung anstelle von Gleitkomma verwenden, dh Sie verwenden eine Ganzzahl, um Tausendstel Grad zu zählen, oder welche Genauigkeit Sie auch immer benötigen.)

Sebastian Redl
quelle
2
interessante Gedanken. Wenn Sie also Millionen von Epsilon akkumulieren und die Transitivität nutzen, können Sie daraus schließen, dass alles gleich alles ist :-) Aber erkennt diese mathematische Einschränkung die diskrete Grundlage von Gleitkommazahlen an, die in vielen Fällen Näherungswerte für die Anzahl sind, die sie darstellen sollen?
Christophe
@Christophe Interessante Frage. Wenn Sie darüber nachdenken, werden Sie feststellen, dass mit diesem Ansatz eine einzelne große Äquivalenzklasse aus Floats erstellt wird, deren Auflösung größer als epsilon ist (sie ist natürlich auf 0 zentriert), und die anderen Floats jeweils in ihrer eigenen Klasse belassen. Aber das ist nicht der Punkt, das eigentliche Problem ist, dass die Schlussfolgerung, dass zwei Zahlen gleich sind, davon abhängt, ob eine dritte verglichen wird und in welcher Reihenfolge dies erfolgt.
Ordentliche
Bei der Bearbeitung von @ OP möchte ich hinzufügen, dass die Fehlerhaftigkeit von Gleitkommazahlen ==die ==Typen, die sie enthalten, "infizieren" sollte. Das heißt, wenn sie Ihrem Rat zur Bereitstellung einer exakten Gleichheit folgen, sollte ihr statisches Analysetool weiter konfiguriert werden, um zu warnen, wenn Gleichheit verwendet wird Temperature. Das ist das Einzige, was Sie wirklich tun können.
HTNW
@HTNW: Das wäre zu einfach. Eine Verhältnisklasse kann ein float approximationFeld haben, an dem nicht teilgenommen wird ==. Außerdem gibt das statische Analysetool bereits innerhalb der ==Implementierung von Klassen eine Warnung aus, wenn eines der verglichenen Elemente ein floatTyp ist.
MSalters
@MSalters? Vermutlich können ausreichend konfigurierbare statische Analysewerkzeuge genau das tun, was ich vorgeschlagen habe. Wenn eine Klasse ein floatFeld hat, an dem sie nicht teilnimmt ==, konfigurieren Sie Ihr Tool nicht so, dass eine Warnung ==für diese Klasse ausgegeben wird. Wenn dies der Fall ist, führt das Markieren der Klasse ==als "zu genau" vermutlich dazu, dass das Tool diese Art von Fehler in der Implementierung ignoriert. ZB in Java ist if @Deprecated void foo()dann void bar() { foo(); }eine Warnung, ist es aber @Deprecated void bar() { foo(); }nicht. Möglicherweise unterstützen viele Tools dies nicht, einige jedoch.
HTNW
16

Viel Glück

Sie werden das nicht erreichen können, ohne dumm mit Hashes zu sein oder das Epsilon zu opfern.

Beispiel:

Angenommen, jeder Punkt hat seinen eigenen eindeutigen Hashwert.

Da Gleitkommazahlen sequentiell sind, gibt es bis zu k Zahlen vor einem gegebenen Gleitkommawert und bis zu k Zahlen nach einem gegebenen Gleitkommawert, die innerhalb eines Epsilons des gegebenen Punktes liegen.

  1. Für jeweils zwei Punkte innerhalb von epsilon, die nicht denselben Hashwert haben.

    • Passen Sie das Hashing-Schema so an, dass diese beiden Punkte den gleichen Wert haben.
  2. Induziert man für alle diese Paare die gesamte Folge von Gleitkommazahlen, so fällt diese zu einem einzigen Wert zusammen.

Es gibt einige Fälle, in denen dies nicht zutrifft:

  • Positive / Negative Unendlichkeit
  • NaN
  • Einige de-normalisierte Bereiche, die für ein bestimmtes Epsilon möglicherweise nicht mit dem Hauptbereich verknüpft werden können.
  • vielleicht ein paar andere formatspezifische Instanzen

Bei> = 99% des Gleitkommabereichs wird jedoch für jeden Wert von epsilon, der mindestens einen Gleitkommawert über oder unter einem bestimmten Gleitkommawert enthält, ein Hash auf einen einzelnen Wert gesetzt.

Ergebnis

Entweder> = 99% des gesamten Fließkomma-Bereichs wird auf einen einzelnen Wert gehasht, der die Absicht eines Hash-Werts ernsthaft beeinträchtigt (und jedes Gerät / jeder Container, der auf einem fair verteilten Hash mit niedriger Kollision beruht).

Oder das Epsilon ist so, dass nur exakte Übereinstimmungen zulässig sind.

Körnig

Sie können sich stattdessen natürlich für einen granularen Ansatz entscheiden.

Unter diesem Ansatz definieren Sie exakte Buckets bis zu einer bestimmten Auflösung. dh:

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

Jeder Bucket hat einen eindeutigen Hash, und jeder Gleitkommawert im Bucket gleicht einem anderen Gleitkommawert im selben Bucket.

Leider ist es immer noch möglich, dass zwei Floats einen Abstand von mehreren Kilometern haben und über zwei separate Hashes verfügen.

Kain0_0
quelle
2
Ich stimme zu, dass der granulare Ansatz hier wahrscheinlich am besten ist, wenn er den Anforderungen von OP entspricht. Obwohl ich befürchte, dass OP +/- 0,1% der Typanforderungen hat, bedeutet dies, dass es nicht granular sein kann.
Neil
4
@DocBrown Der Teil "nicht möglich" ist korrekt. Wenn Epsilon-basierte Gleichheit impliziert, dass die Hash-Codes gleich sind, haben Sie automatisch alle Hash-Codes gleich, sodass die Hash-Funktion nicht mehr nützlich ist. Der Buckets-Ansatz kann fruchtbar sein, aber Sie werden Zahlen mit unterschiedlichen Hash-Codes haben, die beliebig nahe beieinander liegen.
J. Fabian Meier
2
Der Bucket-Ansatz kann geändert werden, indem nicht nur der Bucket mit dem genauen Hash-Schlüssel, sondern auch die beiden benachbarten Buckets (oder mindestens einer von ihnen) auf ihren Inhalt überprüft werden. Damit ist das Problem dieser Randfälle für die Kosten der Laufzeiterhöhung um den Faktor höchstens zwei (bei korrekter Implementierung) beseitigt. Die allgemeine Laufzeitreihenfolge wird jedoch nicht geändert.
Doc Brown
Während Sie im Geist richtig sind, wird nicht alles zusammenbrechen. Mit einem festen kleinen epsilon gleichen sich die meisten Zahlen nur selbst. Natürlich wird das Epsilon für diejenigen nutzlos sein, also seid ihr wieder im Geiste richtig.
Carsten S
1
@CarstenS Ja, meine Aussage, dass 99% des Bereichs auf einen einzelnen Hash gehasht werden, deckt nicht den gesamten Float-Bereich ab. Es gibt viele Hochbereichswerte, die durch mehr als ein Epsilon voneinander getrennt sind und in ihre eigenen eindeutigen Eimer fließen.
Kain0_0
7

Sie können Ihre Temperatur als Ganzzahl unter der Haube modellieren. Die Temperatur hat eine natürliche Untergrenze (-273,15 Grad Celsius). Also, double (-273.15 ist gleich 0 für Ihre zugrunde liegende Ganzzahl). Das zweite Element, das Sie benötigen, ist die Granularität Ihrer Zuordnung. Sie verwenden diese Granularität bereits implizit. es ist dein EPSILON.

Teilen Sie einfach Ihre Temperatur durch EPSILON und nehmen Sie das Wort. Jetzt werden sich Ihr Hash und Ihr Equal synchron verhalten. In Python 3 ist die Ganzzahl nicht begrenzt, EPSILON kann kleiner sein, wenn Sie möchten.

ACHTUNG Wenn Sie den Wert von EPSILON ändern und das Objekt serialisiert haben, sind sie nicht kompatibel!

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

Das Implementieren einer Fließkomma-Hash-Tabelle, die Dinge finden kann, die einem bestimmten Schlüssel "ungefähr gleich" sind, erfordert die Verwendung einiger Ansätze oder einer Kombination davon:

  1. Runden Sie jeden Wert auf ein Inkrement, das etwas größer als der "Fuzzy" -Bereich ist, bevor Sie ihn in der Hash-Tabelle speichern. Wenn Sie versuchen, einen Wert zu finden, überprüfen Sie die Hash-Tabelle auf die gerundeten Werte über und unter dem gesuchten Wert.

  2. Speichern Sie jedes Element in der Hash-Tabelle mit Schlüsseln, die über und unter dem gesuchten Wert liegen.

Beachten Sie, dass die Verwendung eines der beiden Ansätze wahrscheinlich erfordert, dass Hash-Tabelleneinträge keine Elemente, sondern Listen identifizieren, da mit jedem Schlüssel wahrscheinlich mehrere Elemente verknüpft sind. Der oben beschriebene erste Ansatz minimiert die erforderliche Hash-Tabellengröße, aber für jede Suche nach einem Element, das nicht in der Tabelle enthalten ist, sind zwei Hash-Tabellen-Lookups erforderlich. Der zweite Ansatz kann schnell feststellen, dass Elemente nicht in der Tabelle enthalten sind, erfordert jedoch im Allgemeinen, dass die Tabelle etwa doppelt so viele Einträge enthält, wie ansonsten erforderlich wären. Wenn versucht wird, Objekte im 2D-Raum zu finden, kann es nützlich sein, einen Ansatz für die X-Richtung und einen für die Y-Richtung zu verwenden, sodass jedes Element nicht nur einmal gespeichert wird, sondern vier Abfrageoperationen für jede Suche erforderlich sind in der Lage, mit einer Suche einen Gegenstand zu finden, wobei jeder Gegenstand viermal gespeichert werden muss,

Superkatze
quelle
0

Sie können natürlich "fast gleich" definieren, indem Sie beispielsweise die letzten acht Bits der Mantisse löschen und dann vergleichen oder hashen. Das Problem ist , dass die Zahlen sehr nahe beieinander können unterschiedlich sein.

Hier gibt es einige Verwirrung: Wenn zwei Gleitkommazahlen gleich sind, sind sie gleich. Um zu überprüfen, ob sie gleich sind, verwenden Sie "==". Manchmal möchten Sie nicht auf Gleichheit prüfen, aber wenn Sie dies tun, ist „==“ der richtige Weg.

gnasher729
quelle
0

Dies ist keine Antwort, sondern ein erweiterter Kommentar, der hilfreich sein kann.

Ich habe an einem ähnlichen Problem gearbeitet, während ich MPFR (basierend auf GNU MP) verwendet habe. Der von @ Kain0_0 beschriebene "Bucket" -Ansatz scheint akzeptable Ergebnisse zu liefern. Beachten Sie jedoch die in dieser Antwort hervorgehobenen Einschränkungen.

Ich wollte hinzufügen, dass - je nachdem, was Sie versuchen - die Verwendung eines "exakten" Computeralgebrasystems ( Caveat Emptor ) wie Mathematica dabei helfen kann, ein ungenaues numerisches Programm zu ergänzen oder zu verifizieren. Dies ermöglicht es Ihnen , Ergebnisse zu berechnen , ohne sich Gedanken über die Runden, beispielsweise 7*√2 - 5*√2nachgeben 2statt 2.00000001oder ähnliches. Dies wird natürlich zusätzliche Komplikationen mit sich bringen, die sich möglicherweise lohnen oder auch nicht.

BurnsBA
quelle