Est-il possible d'obtenir un hashcode d'un flotteur avec epsilon?
https://stackoverflow.com/questions/580905
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Il est bien connu que la comparaison Talocher == est généralement une erreur. Dans une classe 3D vecteur (avec des composants de flotteur X, Y, Z) i REDIGES deux vecteurs sont considérés comme égaux si la distance est considérée comme nulle.
public override bool Equals(object obj)
{
if (obj == null) {
return false;
}
if (GetType () != obj.GetType ()) {
return false;
}
float d = DistSq ((Vec) obj);
return IsConsideredZero (d);
}
public float DistSq(Vec p)
{
Vec d = this - p;
return d.LengthSq ();
}
public float LengthSq()
{
return X * X + Y * Y + Z * Z;
}
private const float VEC_COMPARE_EPSILON_ABS = 1E-05f;
public static bool IsConsideredZero(float f)
{
return Math.Abs (f) < VEC_COMPARE_EPSILON_ABS;
}
Jusqu'à présent, tout a bien fonctionné. Cependant, maintenant je voudrais obtenir un hashcode du vecteur. Je peux voir que quelque chose comme hash = (int)X^(int)Y^(int)Z est vouée à l'échec.
Le mieux que je pouvais trouver était:
public override int GetHashCode()
{
return 0;
}
Ceci, bien sûr, sorte de suce. Est-il possible d'obtenir un hashcode raisonnable? Nans et d'autres valeurs spéciales sont possibles, mais peu probable, dans le cas qui est important.
La solution
Il est impossible en supposant que vous voulez avoir les propriétés hashcode / normales égalité:
- Si X = Y et Y = Z puis X = Z (transitivité)
- Si X = Y alors Y = X (commutivity)
- X = X pour tous les X (réflexivité)
La première règle est le problème - parce que si chaque valeur est considérée comme « égale » à l'autre plus grand nombre représentable, vous vous retrouvez avec tous nombre étant égales par ailleurs. Par exemple, supposons qu'un nombre est réputé égal à un autre, ils sont de 0,1:
0 est égal à 0,08 0,08 est égal à 0,16 0,16 est égal à 0,24
=> 0 est égal à 0,16 par la règle de transitivité => 0 est égal à 0,24 par la règle de transitivité
(etc)
Si vous ignorez la règle de transitivité, alors vous encore (probablement) souhaitez que les valeurs « égales » à l'égalité d'hashcodes. Ceci impose effectivement la règle de transitivité - dans l'exemple ci-dessus, 0 et 0,08 doivent avoir les mêmes hashcodes, tout comme 0 et 0,16. Par conséquent, 0 et 0,16 doivent avoir les mêmes hashcodes, et ainsi de suite. Par conséquent, vous ne pouvez pas avoir utile hashcode -. Il doit être une constante
Autres conseils
Je ne pense pas que vous pouvez avoir une hashcode qui est compatible avec votre méthode de comparaison parce que celle-ci est pas transitive: pour les trois vecteurs A, B, C, si A.Equals(B) et B.Equals(C) sont vraies, il pourrait encore être le cas que A.Equals(C) est faux. (Imaginez si la distance entre A et B est 6E-6, entre B et C est 6E-6, et entre A et C est 1.2e-5) Mais l'égalité des hashcodes est toujours transitive, car ils ne sont que des chiffres.
Dans ce cas, je venais de créer une méthode de hashcode qui calcule le hachage sur la base des valeurs exactes des coordonnées à virgule flottante, et mention dans la documentation qu'il est incompatible avec égaux. Je sais que ce n'est pas vraiment une solution, mais étant donné que je ne pense pas une vraie solution existe, il est préférable d'avoir un hashcode non négligeable que seulement 0.
Je crains que ce n'est pas dans le cas général. Un croquis d'une preuve va comme ceci:
Prenez deux nombres a et b. Que la différence entre eux est d. Ensuite, si vous créez les d / numéros epsilon avec une étape epsilon entre les deux, chaque étape doit être « égale » à l'étape précédente, qui, par la sémantique hashcode ont la même hashcode. Donc, tous les numéros doivent avoir la même hashcode.
Vous ne pouvez résoudre ce problème si vous ajoutez une autre contrainte.
En aparté, vous définition Equals est faux aussi bien, car il peut être vrai que a.Equals (b) et (c) b.Equals mais pas a.Equals (c), ce qui est mauvais pour égaux. Ceci est connu comme la rupture transitivité propriété.
Que puis-je faire?
La solution dépend de ce que vous utilisez le hachage pour. Une solution serait d'introduire une grille conceptuelle. Changez les égaux et hashcode donc deux nombres sont égaux si dans le même cube de la grille, en arrondissant à un nombre constant de décimales, puis en prenant égaux et hashCode sur le nombre arrondi. Si être proche de zéro est un cas important, ajouter un décalage de epsilon / 2 avant l'arrondissement, donc zéro est le centre du cube. Ceci est correct, mais vous pouvez avoir deux numéros fermer arbitrairement ensemble (sous les limites du flotteur) sans être égale. Donc, pour certaines applications, il sera ok, d'autres, il ne sera pas. Ceci est similaire à une idée de mghie .
Tout le monde est correct ...
Cependant, une chose qui se fait souvent est d'étendre le concept de hachage un peu. Considérons une partition de votre espace 3D avec des boîtes avec un côté >> epsilon.
Le hachage d'un point est le bloc auquel il appartient. Lorsque vous souhaitez rechercher un point, vous ne cochez pas pour le point avec la case correspondante (comme vous le feriez pour une table de hachage normale), mais pour les cases voisines. En 3D, vous devriez vous en sortir avec des boîtes max 8.
Quelle que soit la technique que vous utilisez aura des problèmes parce que vous posiez quelque chose qui est impossible à résoudre.
Qu'est-ce que vous voulez est 1) hachage uniformément répartie de telle sorte que pour la plupart des nombres a et b où a! = B alors a.GetHashCode ()! = B.GetHashCode () mais 2) où a == b puis a.GetHashCode () == b.GetHashCode () doit être vrai.
renvoyant un remplit constant (2), mais pas (1).
Vous pouvez démontrer que l'arrondi à 1E-5 limites et à l'aide que comme un hachage viole remplit (1), mais constitue une violation (2). Prenez 1E-5 et 2E-5, par exemple. Arrondi produirait deux valeurs de hachage différentes mais ils être égaux. Cette contrainte est contraire (2) ci-dessus. Vous pouvez facilement généraliser ce pour prouver que tout arrondi du nombre se heurtera à un problème similaire.
Je vous recommande de choisir une approche différente. Je suppose que le problème sous-jacent est de déterminer si un point est proche d'un point que vous avez déjà. Je recommande de diviser recusively l'espace de coordonnées en deux (où les points le long de la limite (à savoir <= 1E-5 à partir d'une limite) dans les deux moitiés). Si vous vous divisez l'espace (pensez arbre binaire) progressivement, vous pouvez construire une structure de données qui vont rapidement retourner le résultat que vous voulez et être assez facile à construire.
Si je raté ma conjecture et vous devez utiliser un hachage peut alors faire ce que vous voulez avec deux valeurs de hachage de chaque arrondissement à 1E-5, mais compensée par 5E-6. Tous les points égaux compareront égaux sur l'une des deux valeurs de hachage. Cela vous devrez entrer point dans la table de hachage deux fois, une fois pour chaque routine de hachage.
