Есть ли способ получить хэш-код числа с плавающей запятой с помощью эпсилона?
https://stackoverflow.com/questions/580905
-
06-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Хорошо известно, что сравнение чисел с плавающей запятой по == обычно является ошибкой.В классе 3D-векторов (с плавающими компонентами X, Y, Z), который я написал, два вектора считаются равными, если их расстояние считается нулевым.
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;
}
До сих пор все работало нормально.Однако теперь я хотел бы получить хэш-код вектора.Я вижу это что-то вроде hash = (int)X^(int)Y^(int)Z обречен на провал.
Лучшее, что я мог придумать, это:
public override int GetHashCode()
{
return 0;
}
Это, конечно, как-то отстой.Есть ли способ получить разумный хэш-код?NaN и другие специальные значения возможны, но маловероятны, если это важно.
Решение
Это невозможно, если вы хотите иметь обычные свойства хэш-кода/равенства:
- Если X = Y и Y = Z, то X = Z (транзитивность)
- Если X = Y, то Y = X (коммутативность)
- X = X для всех X (рефлексивность)
Проблема заключается в первом правиле: если каждое значение считается «равным» следующему большему представимому числу, вы получите все числа равны.Например, предположим, что число считается равным другому, если оно находится в пределах 0,1:
0 равняется 0,08 0,08 равна 0,16 0,16 равна 0,24
=> 0 равно 0,16 правилом транзитивности => 0 равняется 0,24 правилом транзитивности
(и т. д)
Если вы проигнорируете правило транзитивности, вы все равно (предположительно) захотите, чтобы «равные» значения имели равные хэш-коды.Это эффективно обеспечивает соблюдение правила транзитивности — в приведенном выше примере 0 и 0,08 должны иметь одинаковые хэш-коды, как и 0 и 0,16.Поэтому 0 и 0,16 должны иметь одинаковые хэш-коды и так далее.Поэтому у вас не может быть никаких полезный хеш-код - он должен быть константой.
Другие советы
Я не думаю, что у вас может быть хэш-код, соответствующий вашему методу сравнения, поскольку последний не является транзитивным:для любых трех векторов A, B, C, если A.Equals(B) и B.Equals(C) правда, все еще может быть так, что A.Equals(C) является ложным.(Представьте, что расстояние между A и B равно 6e-6, между B и C — 6e-6, а между A и C — 1,2e-5). Но равенство хеш-кодов всегда транзитивно, поскольку это просто числа.
В этом случае я бы просто создал метод хеш-кода, который вычисляет хэш на основе точных значений координат с плавающей запятой, и упомянул бы в документации, что он несовместим с равными.Я знаю, что это не совсем решение, но, учитывая, что я не думаю, что реальное решение существует, лучше иметь нетривиальный хэш-код, чем просто 0.
Боюсь, это не в общем случае.Схема доказательства выглядит так:
Возьмем любые два числа a и b.Пусть разница между ними равна d.Затем, если вы создаете числа d/epsilon с шагом epsilon между ними, каждый шаг должен быть «равен» предыдущему шагу, который по семантике хэш-кода имеет тот же хэш-код.Таким образом, все числа должны иметь один и тот же хэш-код.
Вы сможете решить эту проблему, только если добавите какое-то другое ограничение.
Кроме того, ваше определение Equals также неверно, так как может быть верно, что a.Equals(b) и b.Equals(c), но не a.Equals(c), что неверно для равных.Это известно как нарушение Транзитивность свойство.
Что я могу сделать тогда?
Решение зависит от того, для чего вы используете хеш.Одним из решений было бы введение концептуальной сетки.Измените равенства и хэш-код так, чтобы два числа были равны, если они находятся в одном и том же кубе сетки, округлив до постоянного количества десятичных знаков, а затем взяв равенства и хеш-код для округленного числа.Если важно, чтобы значение было близко к нулю, перед округлением добавьте смещение эпсилон/2, чтобы ноль был центром куба.Это правильно, но вы можете иметь два числа, сколь угодно близких друг к другу (в пределах числа с плавающей запятой), но не равных.Так что для некоторых приложений это будет нормально, для других — нет.Это похоже на идею из мгхи.
Все правы...
ОДНАКО часто приходится немного расширять концепцию хеша.Рассмотрим раздел вашего трехмерного пространства коробками со стороной >> эпсилон.
Хэш точки — это блок, которому она принадлежит.Когда вы хотите найти точку, вы проверяете не точку в соответствующем поле (как если бы вы делали это для обычного хеша), а также соседние поля.В 3D вам сойдёт с рук максимум 8 коробок.
Какую бы технику вы ни использовали, она будет иметь проблемы, потому что вы поставили перед собой задачу, которую невозможно решить.
То, что вам нужно, это 1) равномерно распределенный хеш, такой, что для большинства чисел a и b где a != b, затем a.GetHashCode() != b.GetHashCode(), но 2) где a == b, тогда a.GetHashCode() = = b.GetHashCode() должно иметь значение true.
Возврат константы удовлетворяет (2), но не (1).
Вы можете продемонстрировать, что округление на границах 1E-5 и использование этого в качестве хэша нарушает выполнение (1), но нарушает (2).Возьмем, к примеру, 1E-5 и 2E-5.Округление приведет к получению двух разных значений хеш-функции, но при сравнении они будут равными.Это нарушает ограничение (2), приведенное выше.Вы можете легко обобщить это и доказать, что любое округление числа приведет к аналогичной проблеме.
Я рекомендую вам выбрать другой подход.Я предполагаю, что основная проблема заключается в том, чтобы определить, близка ли какая-то точка к уже имеющейся у вас точке.Я рекомендую рекусивно разделить координатное пространство пополам (где точки вдоль границы (т.<=1E-5 от границы) в обеих половинах).Если вы постепенно разделите пространство (например, двоичное дерево), вы сможете построить структуру данных, которая быстро вернет желаемый результат, и ее будет довольно легко построить.
Если я пропустил свою догадку и вам необходимо использовать хеш, тогда вы можете делать то, что хотите, с двумя значениями хеш-функции, каждое из которых округляется до 1E-5, но со смещением на 5E-6.Все равные точки будут сравниваться равными по одному из двух значений хеш-функции.Для этого вам потребуется ввести точку в хеш-таблицу дважды, по одному разу для каждой хеш-программы.
