Безопасно ли использовать поплавки в качестве ключей хеш-таблиц?

Question

Мне нужно хранить пары float,int, в которых значение int хранит количество вхождений значения float внутри модели, которую я использую для инструмента, который я разрабатываю, и мне было интересно, если этобезопасно делать такие вещи ..

Конечная точность должна быть проблемой, когда говорящие поплавки используются для прямых сравнений (или в качестве содержимого, которое нужно хэшировать), поэтому я думаю, что подобный подход не рекомендуется, я прав?

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

Возможно, лучшим решением будет использование дерева двоичного поиска (или даже более продвинутой структуры данных), чтобы получить хотя бы среднее значениеслучай O (logn) также, если постоянный коэффициент будет лучше.

Есть ли у вас какие-либо предложения?Просто чтобы сообщить вам, что я разрабатываю в OCaml, но я думаю, что эти соображения можно считать независимыми от языка

Answer 1

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

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

Answer 2

Я думаю, что здесь есть пара вопросов

Безопасно ли использовать плавающие числа в качестве ключей для хеш-таблицы?

Да.Сейчас я не могу вспомнить язык, в котором floats не соответствуют требованиям, необходимым для ключа в хеш-таблице (обычно это стабильный хеш-код и семантика равенства)

Можно ли иметь хеш-таблицус большим количеством ключей?

Зависит от того, сколько.Если количество ключей настолько велико, это приводит к тому, что таблица расширяется за допустимый объем памяти, то, конечно, нет, поскольку это приведет к нехватке памяти.Действительно невозможно ответить на эту часть вопроса без большего контекста.Скорее всего, вы единственный, кто сможет ответить на него.

Точность float делает ее хуже, чем другие типы, такие как int?

Это зависит от реализациино я считаю, что в OCaml float имеет двойную точность (8 байт).Поэтому вопрос о том, делает ли точность его недействительным в качестве ключа, эквивалентен запросу типа C # long, который не подходит в качестве ключа хеш-таблицы.Они оба имеют одинаковое количество возможных значений (они оба 8 байтов).Я бы, конечно, сказал, что long является допустимым типом ключа (использовал его часто, и в этом нет ничего плохого).

Я думаю, что реальный вопрос в том, что вы безответственно создаете экземпляры float для использования в качестве ключа.

Если у меня заканчивается память с хэш-таблицей, будет ли двоичное дерево лучше?

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

Answer 3

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

Как говорит Дэвид, неотъемлемая проблема хеш-таблицы с ключами в числах с плавающей точкой заключается в том, что в хеш-таблицах используется равенство для идентификации ключей, а равенство с плавающей точкой является несколько ненадежным понятием из-за ошибок вычислений. Нет общей гарантии, что sin(pi / 6) == 0.5 или даже (2.0 / 3) * (2.0 / 3) == (4.0 / 9). В обоих случаях LHS может немного отличаться от RHS.

Итак, если некоторые из подсчитываемых вами записей вводятся как 0.5, а некоторые вычисляются как sin(pi / 6), и вы хотите, чтобы они были посчитаны вместе, то вам нужно сделать больше, чем просто хешировать значение с плавающей запятой.

Вам может сойти с рук округление, а затем хэширование, хотя вы никогда не избежите проблемы полностью. Например, если вы округлите до ближайшего 0,001, то вы идентифицируете 0.2020001 и 0.2020003 как «одно и то же значение с ошибкой вычисления», но не одинаково близкие 0.1014999 и 0.1015001. Я использовал примеры из 10 для простоты ввода, но, конечно, «float» обычно означает двоичное представление.

Точно такая же проблема применима к двоичному дереву. Hashtables на самом деле не волнует, что их ключевые данные «есть», они просто заботятся о том, чтобы кто-то мог предоставить функцию h, которая сопоставляет ключи с целыми числами, так что для любых x и y вы хотите считать «равными» h(x) == h(y). Затем, для производительности, вы хотите, чтобы h вводил не больше «коллизий» (экземпляров h(x) == h(y), где x != y), чем случайный шанс. Нет никаких препятствий для того, чтобы делать это с поплавками. Вы должны убедиться, что вы не включили в хеш ничего, что не участвует в сравнении, и это поможет, если вы включите всю информацию, которая участвует в сравнении.

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

Answer 4

Вы говорите о проблеме с производительностью или с действительностью?

Для достоверности: если вы хотите посчитать вхождения одинаковых чисел с плавающей запятой, тогда проблем нет. Если вы хотите посчитать вхождения одинаковых чисел с плавающей точкой, вам необходимо выяснить, что означает для вас «примерно одинаковое».