Есть ли способ получить хеш-код с плавающей точкой с помощью epsilon? - PullRequest
Новая
       31

Есть ли способ получить хеш-код с плавающей точкой с помощью epsilon?

11 голосов
/ 24 февраля 2009

Хорошо известно, что сравнивать поплавки с помощью == обычно ошибка. В классе трехмерных векторов (с плавающими компонентами 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 и другие специальные значения возможны, но маловероятны, если это важно.

Ответы [ 5 ]

13 голосов
/ 24 февраля 2009

Невозможно предположить, что вы хотите иметь нормальные свойства хэш-кода / равенства:

  • Если 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 должны иметь одинаковые хеш-коды и так далее. Поэтому у вас может не быть полезного хеш-кода - он должен быть константой.

8 голосов
/ 24 февраля 2009

Я не думаю, что у вас может быть хеш-код, который согласуется с вашим методом сравнения, потому что последний не транзитивен: для любых трех векторов 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.

7 голосов
/ 24 февраля 2009

Боюсь, это не в общем случае. Эскиз доказательства выглядит так:

Возьмите любые два числа a и b. Пусть разница между ними будет d. Затем, если вы создаете числа d / epsilon с шагом epsilon между ними, каждый шаг должен быть «равен» предыдущему шагу, который по семантике хэш-кода имеет тот же хеш-код. Поэтому все числа должны иметь одинаковый хеш-код.

Вы можете решить эту проблему, только если добавите какое-то другое ограничение.

Кроме того, ваше определение Equals также неверно, поскольку может быть верно, что a.Equals (b) и b.Equals (c), но не a.Equals (c), что неверно для equals. Это называется нарушением свойства Transitivity .

Что я могу сделать тогда?

Решение зависит от того, для чего вы используете хеш. Одним из решений будет введение концептуальной сетки. Измените equals и hashcode, чтобы два числа были равны, если в одном и том же кубе сетки, округляя до постоянного числа десятичных разрядов, затем получая equals и hashcode для округленного числа. Если значение близко к нулю является важным случаем, добавьте смещение epsilon / 2 перед округлением, чтобы ноль был центром куба. Это правильно, но вы можете иметь два числа произвольно близко друг к другу (в пределах числа с плавающей точкой), не будучи равными. Так что для некоторых приложений это будет хорошо, для других - нет. Это похоже на идею из mghie .

4 голосов
/ 24 февраля 2009

Все правы ...

ОДНАКО, что часто делается, это немного расширить концепцию хэширования. Рассмотрим раздел вашего трехмерного пространства с прямоугольниками со стороной >> epsilon.

Хэш точки - это поле, к которому она принадлежит. Когда вы хотите найти точку, вы проверяете не точку с соответствующим блоком (как вы бы сделали для обычного хэша), но также и соседние блоки. В 3d вы должны получить максимум 8 коробок.

2 голосов
/ 24 февраля 2009

Какой бы метод вы ни использовали, у вас будут проблемы, потому что вы поставили что-то, что невозможно решить.

То, что вы хотите, это: 1) равномерно распределенный хеш, так что для большинства чисел a и b, где a! = B, затем a.GetHashCode ()! = B.GetHashCode () но 2) где a == b, то a.GetHashCode () == b.GetHashCode () должен быть истинным.

Возвращение константы выполняет (2), но не (1).

Вы можете продемонстрировать, что округление в границах 1E-5 и использование его в качестве хеша нарушает выполнение (1), но нарушает (2). Возьмите 1E-5 и 2E-5, например. Округление даст два разных значения хеша, но они будут сравниваться одинаково. Это нарушает ограничение (2) выше. Вы можете легко обобщить это, чтобы доказать, что любое округление числа столкнется с подобной проблемой.

Я рекомендую вам выбрать другой подход. Я предполагаю, что основная проблема заключается в том, чтобы определить, близка ли какая-либо точка к точке, которая у вас уже есть. Я рекомендую рекурсивное разделение координатного пространства пополам (где точки вдоль границы (т. Е. <= 1E-5 от границы) на обе половины). Если вы постепенно делите свое пространство (например, двоичное дерево), вы можете создать структуру данных, которая быстро вернет желаемый результат и будет довольно легко построить. </p>

Если я пропустил свое предположение, и вы должны использовать хеш, то можете делать то, что хотите, с двумя значениями хеш-функции, каждое из которых округляется до 1E-5, но смещено на 5E-6. Все равные точки будут сравниваться равными по одному из двух значений хеша. Для этого потребуется дважды ввести точку в хеш-таблицу, по одному разу для каждой хеш-процедуры.

...