Comment implémenter le hachage flottant avec une égalité approximative

15

Disons que nous avons la classe Python suivante (le problème existe en Java tout comme avec equalset hashCode)

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

degreesest la température en Kelvin sous forme de flotteur. Maintenant, je voudrais implémenter le test d'égalité et le hachage d' Temperatureune manière qui

  • compare les flottants à une différence epsilon au lieu de tests d'égalité directs,
  • et honore le contrat que cela a == bimplique hash(a) == hash(b).
def __eq__(self, other):
    return abs(self.degrees - other.degrees) < EPSILON

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

La documentation Python parle un peu de hachage des nombres pour s'assurer que, hash(2) == hash(2.0)mais ce n'est pas tout à fait le même problème.

Suis-je même sur la bonne voie? Et si c'est le cas, quelle est la méthode standard pour implémenter le hachage dans cette situation?

Mise à jour : Je comprends maintenant que ce type de test d'égalité pour les flottants élimine la transitivité de ==et equals. Mais comment cela va-t-il de pair avec la «connaissance commune» selon laquelle les flotteurs ne devraient pas être comparés directement? Si vous implémentez un opérateur d'égalité en comparant les flottants, les outils d'analyse statique se plaindront. Ont-ils raison de le faire?

Martre
la source
9
pourquoi la question a la balise Java?
Laiv
8
À propos de votre mise à jour: je dirais que le hachage des flotteurs est généralement une chose discutable. Essayez d'éviter d'utiliser des flottants comme clés ou comme éléments d'ensemble.
J.Fabian Meier
6
@Neil: En même temps, l'arrondi ne ressemble-t-il pas à des entiers? J'entends par là: si vous pouvez arrondir à, disons, des millièmes de degrés, alors vous pourriez simplement utiliser une représentation à virgule fixe - un entier exprimant la température en millièmes de degrés. Pour la facilité d'utilisation, vous pourriez avoir un getter / setter convertissant de manière transparente de / vers des flotteurs si vous souhaitez ...
Matthieu M.
4
Kelvins ne sont plus des degrés. Les diplômes sont également ambigus. Pourquoi ne pas simplement l'appeler kelvin?
Solomon Ucko
5
Python a un support plus ou moins excellent en virgule fixe , c'est peut-être quelque chose pour vous.
Jonas Schäfer

Réponses:

41

implémenter les tests d'égalité et le hachage de la température d'une manière qui compare les flottants à une différence epsilon au lieu des tests d'égalité directs,

L'égalité floue viole les exigences que Java impose à la equalsméthode, à savoir la transitivité , c'est-à-dire que si x == yet y == z, alors x == z. Mais si vous faites une égalité floue avec, par exemple, un epsilon de 0,1, alors 0.1 == 0.2et 0.2 == 0.3, mais 0.1 == 0.3ne tient pas.

Bien que Python ne documente pas une telle exigence, les implications d'avoir une égalité non transitive en font une très mauvaise idée; le raisonnement sur de tels types induit des maux de tête.

Je vous recommande donc fortement de ne pas le faire.

Soit fournir une égalité exacte et baser votre hachage sur cela de manière évidente, et fournir une méthode distincte pour effectuer la correspondance floue, soit opter pour l'approche de classe d'équivalence suggérée par Kain. Bien que dans ce dernier cas, je vous recommande de fixer votre valeur à un membre représentatif de la classe d'équivalence dans le constructeur, puis de procéder avec une égalité exacte simple et un hachage pour le reste; il est beaucoup plus facile de raisonner sur les types de cette façon.

(Mais si vous faites cela, vous pourriez tout aussi bien utiliser une représentation à virgule fixe au lieu de virgule flottante, c'est-à-dire que vous utilisez un entier pour compter les millièmes de degré, ou la précision que vous souhaitez.)

Sebastian Redl
la source
2
pensées intéressantes. Donc, en accumulant des millions d'Epsilon et avec la transitivité, vous pouvez conclure que tout est égal à autre chose :-) Mais cette contrainte mathématique reconnaît-elle la base discrète des virgules flottantes, qui dans de nombreux cas sont des approximations du nombre qu'elles sont censées représenter?
Christophe
@Christophe Question intéressante. Si vous y réfléchissez, vous verrez que cette approche fera une seule grande classe d'équivalence à partir de flotteurs dont la résolution est supérieure à epsilon (elle est centrée sur 0, bien sûr) et laissera les autres flottants dans leur propre classe chacun. Mais ce n'est pas le sujet, le vrai problème est que le fait de conclure que 2 nombres sont égaux dépend de la comparaison d'un troisième et de l'ordre dans lequel cela est fait.
Ordous
Concernant l'édition de @OP, j'ajouterais que l'inexactitude de la virgule flottante ==devrait «infecter» les ==types les contenant. Autrement dit, s'ils suivent votre conseil de fournir une égalité exacte, leur outil d'analyse statique doit en outre être configuré pour avertir lorsque l'égalité est utilisée Temperature. C'est vraiment la seule chose que vous puissiez faire.
HTNW
@HTNW: Ce serait trop simple. Une classe de ratio peut avoir un float approximationchamp auquel il ne participe pas ==. De plus, l'outil d'analyse statique donnera déjà un avertissement dans l' ==implémentation des classes lorsque l'un des membres comparés est un floattype.
MSalters
@MSalters? Vraisemblablement, des outils d'analyse statique suffisamment configurables peuvent faire ce que je propose très bien. Si une classe possède un floatchamp auquel il ne participe pas ==, ne configurez pas votre outil pour avertir ==sur cette classe. Si la classe le fait, alors le marquage probable de la classe ==comme «trop exact» fera que l'outil ignorera ce type d'erreur dans l'implémentation. Par exemple, en Java, si @Deprecated void foo(), alors void bar() { foo(); }est un avertissement, mais @Deprecated void bar() { foo(); }ne l'est pas. Peut-être que de nombreux outils ne prennent pas en charge cela, mais certains le pourraient.
HTNW
16

Bonne chance

Vous n'allez pas pouvoir y arriver, sans être stupide avec des hachages, ou sacrifier l'epsilon.

Exemple:

Supposons que chaque point soit haché selon sa propre valeur de hachage unique.

Comme les nombres à virgule flottante sont séquentiels, il y aura jusqu'à k nombres avant une valeur en virgule flottante donnée, et jusqu'à k nombres après une valeur en virgule flottante donnée qui se trouvent dans un epsilon du point donné.

  1. Pour chacun des deux points dans epsilon l'un de l'autre qui ne partagent pas la même valeur de hachage.

    • Ajustez le schéma de hachage afin que ces deux points de hachage aient la même valeur.
  2. Introniser pour toutes ces paires la séquence entière de nombres à virgule flottante s'effondrera vers une valeur unique.

Il y a quelques cas où cela ne sera pas vrai:

  • Infini positif / négatif
  • NaN
  • Quelques plages dénormalisées qui peuvent ne pas être liées à la plage principale pour un epsilon donné.
  • peut-être quelques autres instances spécifiques au format

Cependant> = 99% de la plage en virgule flottante hachera à une valeur unique pour toute valeur d'Epsilon qui comprend au moins une valeur en virgule flottante au-dessus ou en dessous d'une valeur en virgule flottante donnée.

Résultat

Soit> = 99% de la plage de virgule flottante entière hachée à une seule valeur, ce qui compromet sérieusement l'intention d'une valeur de hachage (et tout appareil / conteneur reposant sur un hachage à faible collision assez distribué).

Ou l'epsilon est tel que seules les correspondances exactes sont autorisées.

Granulaire

Vous pouvez bien sûr opter pour une approche granulaire à la place.

Avec cette approche, vous définissez des compartiments exacts jusqu'à une résolution particulière. c'est à dire:

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

Chaque compartiment a un hachage unique, et tout point flottant dans le compartiment est égal à tout autre flottant du même compartiment.

Malheureusement, il est toujours possible que deux flotteurs soient à une distance de epsilon et ont deux hachages séparés.

Kain0_0
la source
2
Je conviens que l'approche granulaire ici serait probablement la meilleure, si cela correspond aux exigences du PO. Bien que j'aie peur que OP ait des exigences de type +/- 0,1%, ce qui signifie qu'il ne peut pas être granulaire.
Neil
4
@DocBrown La partie "impossible" est correcte. Si l'égalité basée sur epsilon doit impliquer que les codes de hachage sont égaux, alors vous avez automatiquement tous les codes de hachage égaux, donc la fonction de hachage n'est plus utile. L'approche des compartiments peut être fructueuse, mais vous aurez des numéros avec différents codes de hachage qui sont arbitrairement proches les uns des autres.
J.Fabian Meier
2
L'approche du compartiment peut être modifiée en vérifiant non seulement le compartiment avec la clé de hachage exacte, mais également les deux compartiments voisins (ou au moins l'un d'entre eux) pour leur contenu. Cela élimine le problème de ces cas de bord pour le coût de l'augmentation du temps de fonctionnement par un facteur d'au plus deux (lorsqu'il est correctement mis en œuvre). Cependant, cela ne modifie pas l'ordre général du temps d'exécution.
Doc Brown
Pendant que vous avez raison, tout ne s'effondrera pas. Avec un petit epsilon fixe, la plupart des nombres ne seront égaux qu'eux-mêmes. Bien sûr, pour ceux-là, l'epsilon sera inutile, donc encore une fois, en esprit, vous avez raison.
Carsten S
1
@CarstenS Oui, ma déclaration selon laquelle 99% de la plage de hachages à un seul hachage ne couvre pas réellement toute la plage de flottants. Il existe de nombreuses valeurs élevées qui sont séparées par plus que epsilon qui hacheront leurs propres compartiments uniques.
Kain0_0
7

Vous pouvez modéliser votre température sous forme d'entier sous le capot. La température a une limite inférieure naturelle (-273,15 Celsius). Donc, double (-273.15 est égal à 0 pour votre entier sous-jacent). Le deuxième élément dont vous avez besoin est la granularité de votre mappage. Vous utilisez déjà implicitement cette granularité; c'est votre EPSILON.

Il suffit de diviser votre température par EPSILON et de prendre la parole, maintenant votre hachage et votre égal se comporteront en synchronisation. En Python 3, l'entier est illimité, EPSILON peut être plus petit si vous le souhaitez.

ATTENTION Si vous modifiez la valeur d'EPSILON et que vous avez sérialisé l'objet, ils ne seront pas compatibles!

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

L'implémentation d'une table de hachage à virgule flottante qui peut trouver des éléments "approximativement égaux" à une clé donnée nécessitera l'utilisation de deux approches ou d'une combinaison de celles-ci:

  1. Arrondissez chaque valeur à un incrément légèrement supérieur à la plage "floue" avant de la stocker dans la table de hachage, et lorsque vous essayez de trouver une valeur, vérifiez dans la table de hachage les valeurs arrondies au-dessus et en dessous de la valeur recherchée.

  2. Stockez chaque élément dans la table de hachage à l'aide de clés situées au-dessus et en dessous de la valeur recherchée.

Notez que l'utilisation de l'une ou l'autre approche nécessitera probablement que les entrées de table de hachage n'identifient pas les éléments, mais plutôt les listes, car il y aura probablement plusieurs éléments associés à chaque clé. La première approche ci-dessus minimisera la taille requise de la table de hachage, mais chaque recherche d'un élément ne figurant pas dans le tableau nécessitera deux recherches de table de hachage. La deuxième approche sera rapidement en mesure d'identifier que les éléments ne sont pas dans le tableau, mais nécessitera généralement que le tableau contienne environ deux fois plus d'entrées que ce qui serait autrement requis. Si l'on essaie de trouver des objets dans l'espace 2D, il peut être utile d'utiliser une approche pour la direction X et une pour la direction Y, de sorte qu'au lieu d'avoir chaque élément stocké une fois mais nécessitant quatre opérations de requête pour chaque recherche, ou d'être pouvoir utiliser une recherche pour trouver un article mais avoir à stocker chaque article quatre fois,

supercat
la source
0

Vous pouvez bien sûr définir «presque égal» en supprimant par exemple les huit derniers bits de la mantisse, puis en comparant ou en hachant. Le problème est que les nombres très proches les uns des autres peuvent être différents.

Il y a une certaine confusion ici: si deux nombres à virgule flottante se comparent égaux, ils sont égaux. Pour vérifier si elles sont égales, vous utilisez "==". Parfois, vous ne voulez pas vérifier l'égalité, mais lorsque vous le faites, "==" est la voie à suivre.

gnasher729
la source
0

Ce n'est pas une réponse, mais un commentaire détaillé qui peut être utile.

J'ai travaillé sur un problème similaire, tout en utilisant MPFR (basé sur GNU MP). L'approche «bucket» telle que décrite par @ Kain0_0 semble donner des résultats acceptables, mais soyez conscient des limites mises en évidence dans cette réponse.

Je voulais ajouter que - selon ce que vous essayez de faire - l'utilisation d'un système d'algèbre informatique "exact" ( caveat emptor ) comme Mathematica peut aider à compléter ou à vérifier un programme numérique inexact. Cela vous permettra de calculer les résultats sans vous soucier de l'arrondi, par exemple, 7*√2 - 5*√2donnera 2au lieu de 2.00000001ou similaire. Bien sûr, cela entraînera des complications supplémentaires qui peuvent ou non en valoir la peine.

BurnsBA
la source