Хороший способ хэшировать вектор с плавающей точкой?

Question

Мне хорошо известны все проблемы, связанные со сравнением поплавков. Это как раз причина этого вопроса.
Я хочу создать быструю хэш-таблицу для значений, которые являются трехмерными векторами (3 числа с плавающей точкой - x, y, z). Можно предположить, что длина вектора всегда равна 1,0 (sqrt(x*x+y*y+z*z) равно 1,0)

По сути, это означает, что я ищу хеш-функцию, которая принимает значения, которые почти равны одному и тому же значению без знака int, и соответствующий оператор равенства, который имеет значение true, если значения хеш-функции равны (не обязательно, только если они равный)

Редактировать -
Ложные срабатывания (то есть векторы, которые различны, но отображаются на одно и то же ведро) - это данные, поскольку это хеш-таблица.
Ложные негативы (т. Е. Векторы, которые находятся близко друг к другу, но отображаются в разные области), нежелательны, но кажется, что их невозможно избежать. В моем случае они не приведут к полному разрыву, просто некоторое дублирование данных, с которым мне придется смириться.

Answer 1

Я думаю, то, что вы ищете, напрямую невозможно. Одним из важных свойств равенства является то, что оно транзитивно. (т.е. если a == b и b == c, то a == c). Однако при измерении расстояния вам действительно не нужно это свойство. Пример:

Возьмите один поплавок (для простоты). Предположим, что мы хотим хэшировать каждое число с плавающей точкой, чтобы значения с плавающей точкой менее 1e-3 имели одинаковое значение. Теперь предположим, что мы добавили к этой хеш-таблице 1000 значений с плавающей запятой, все с точностью до 1e-4. Любые соседние 2 значения должны хешироваться в один и тот же тип с плавающей точкой, поскольку они ближе, чем 1e-3. Однако из-за транзитивности соседям по этим значениям также должно присваиваться одинаковое значение, а также их соседям и так далее. В результате все 1000 значений, включая пары дальше, чем 1e-3 друг от друга, будут хэшировать одно и то же целое число. Если бы вы нарисовали эти точки на картинке:

A  B  C  D  E  F  G  H ... Y Z

Предположим, что все промежутки находятся на расстоянии <1e-3, но A и Z на расстоянии> 1e-3 (не в масштабе!). Это не может быть выполнено, потому что если hash (A) == hash (B) и hash (B) == hash (C) и т. Д. Для всех пар (поскольку они <1e-3 друг от друга), чем hash (A ) должен == хэш (Z). </p>

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

Answer 2

Некоторые языки (C, Java 5) позволяют вам получить доступ к двоичному значению ваших чисел с плавающей запятой. Таким образом, вы можете извлечь первые N битов мантиссы (игнорируя последние несколько битов, которые вызывают проблемы во время сравнения) и вычислить из этого хеш.

Answer 3

Я бы конвертировал значения с плавающей точкой в ​​целые числа, например:

unsigned int IntValue = (int)(floatValue * MULT) + MULT;

, чтобы вы получили первые цифры и затем использовали

const MULT1 = (MULT << 1) + 1;
unsigned long long HashValue = (xIntValue * MULT1  * MULT1) + (yIntValue * MULT1) + zIntValue;

в качестве значения хеша (с использованием (MULT * 2) + 1, поскольку значения IntValues ​​будут в диапазоне от 0 до MULT * 2 включительно).

Необходимая память будет зависеть от мультипликатора MULT. Например, используя 32, вы получите хеш-таблицу, используя 64 * 64 * 64 * (размер элемента хеширования) = 262144 * (размер элемента хеша).

Answer 4

Я думаю, что вы эффективно пытаетесь решить ближайшую проблему. Я полагаю, что вы ищете локальное хеширование . Также вы можете использовать структуры дерева четырехугольников для достижения того же результата.

Answer 5

Можете ли вы рассказать о своей проблеме?

Предполагая, что вы используете хэш-карту для сопоставления некоторых дополнительных данных с конкретными векторами, вы можете просто использовать XOR двоичных представлений компонентов (если это возможно на выбранном вами языке). Затем используйте столько LSB (чтобы уменьшить коллизии), сколько вам нужно для хэш-карты. Это, конечно, будет иметь свойство, заключающееся в том, что два равных вектора (путем сравнения с плавающей запятой) могут не иметь одинаковый хэш (например, IEEE с плавающей запятой 0 равен -0, но они имеют разный знаковый бит).

Однако, если вы планируете использовать векторы, которые являются результатом различных вычислений, для поиска хеша, вы настраиваете себя на возможность отсутствия совпадения хеш-кодов из-за ошибок округления, и вам, вероятно, следует использовать что-то еще в любом случае .

Answer 6

Вам нужно, чтобы это была быстрая хеш-таблица или подходила бы древовидная структура?

Мне кажется, что было бы легче найти соответствующие поплавки в дереве поиска некоторых Сортировать. A B-Tree минимизирует количество пропусков кэша, если вы выберете правильный размер узла. Это должно сделать это довольно быстро на практике.

Answer 7

не знаю, как быстро это может быть, но поскольку у вас есть единичные векторы, все они лежат на поверхности сферы. преобразовать в http://en.wikipedia.org/wiki/Spherical_coordinate_system., затем использовать фи и тета, чтобы выбрать ведро. не будет ложных срабатываний. Вы можете посмотреть в соседних клетках на ложные негативы.