Действительно ли безопасно использовать плавания в качестве ключей хеш-таблиц?
Я должен сохранить пар float,int в котором int оцените хранит количество случаев a float оцените в модели, которую я использую для инструмента, который я разрабатываю, и я задавался вопросом, безопасно ли сделать такие вещи..
Конечная точность должна быть проблемой при разговоре, плавания раньше направляли сравнения (или как содержание, которое будет хешировано), таким образом, я думаю, что аналогичному подходу препятствуют, действительно ли я прав?
На самом деле проблема состоит в том, что у меня нет никакой другой информации вместе с этими плаваниями, таким образом, я просто не могу использовать ничто больше в качестве ключа для хеш-таблицы, но в то же время, так как ключи будут, многие, имея хорошую производительность были бы хороши.
Возможно, лучшее решение состоит в том, чтобы использовать дерево двоичного поиска (или еще более усовершенствованная структура данных) для получения, по крайней мере, среднего случая O (logn) также, если постоянный множитель был бы лучше.
У Вас есть какое-либо предложение? Только для сообщения я разрабатываю в OCaml, но я думаю, что эти соображения можно считать агностиком языка
4 ответа
Обычная проблема с числами с плавающей запятой состоит в том, что вычисления являются приблизительными. Если вы вычисляете одно и то же значение двумя разными способами, результаты, скорее всего, будут немного отличаться. (В некоторых случаях вы можете получить небольшие различия, вычислив одно и то же значение дважды одним и тем же способом.)
Следовательно, если вы выполняете какие-либо вычисления с плавающей запятой, вы получите приблизительные значения и не должны полагаться на равенство. Если ваш источник вычислял числа с плавающей запятой по-разному, передаваемые вам данные будут приблизительными. Если вы получаете точные значения с плавающей запятой и можете рассчитывать на любые числа, которые должны быть одинаковыми, являясь точно таким же битовым представлением, тогда равенство работает как обычно, и вы можете использовать хеш-таблицу.
Я думаю, здесь есть пара вопросов
Безопасно ли использовать числа с плавающей запятой в качестве ключей к хеш-таблице?
Да. Я не могу сейчас придумать язык, на котором числа с плавающей запятой не соответствуют требованиям, необходимым для ключа в хеш-таблице (обычно стабильный хеш-код и семантика равенства)
Можно ли иметь хэш таблица с множеством ключей?
Зависит от того, сколько. Если количество ключей настолько велико, что таблица выходит за пределы допустимого размера памяти, то, конечно же, нет, поскольку это вызовет нехватку памяти. На эту часть вопроса действительно невозможно ответить без дополнительного контекста. Скорее всего, вы единственный, кто сможет на него ответить.
Уменьшает ли точность float по сравнению с другими типами, такими как int ?
Это зависит от реализации, но я верю в OCaml a float имеет двойную точность (8 байт). Таким образом, вопрос о том, делает ли точность ключ недействительным, эквивалентен запросу типа C # long , который не подходит в качестве ключа хеш-таблицы. У них обоих одинаковое количество возможных значений (они оба по 8 байтов). Я бы с уверенностью сказал, что long - допустимый тип ключа (использовал его часто, и в этом нет ничего плохого).
Я думаю, что реальный вопрос заключается в том, что вы безответственно создаете экземпляры float для использования в качестве ключа.
Если у меня заканчивается память с хеш-таблицей, будет ли двоичное дерево лучше?
Возможно, но не намного. Есть накладные расходы, связанные как с бинарными деревьями, так и с хеш-таблицами.Для хэш-таблиц это обычно неиспользуемые сегменты и следующие указатели в списках внутри сегментов. Для двоичного дерева каждый элемент в дереве имеет 2 дополнительных части служебных данных (левый и правый указатели). Если у вас заканчивается память, я не уверен, что переключение на двоичное дерево будет значительно лучше.
Вы говорите о проблеме с производительностью или о проблеме с достоверностью?
Для проверки достоверности: если вы хотите подсчитать появление идентичных чисел с плавающей запятой, то проблем нет. Если вы хотите подсчитать вхождения примерно одинаковых чисел с плавающей запятой, вам нужно выяснить, что для вас означает «примерно то же самое».
Возможно, все будет в порядке, если вы уверены, что собираетесь подсчитать количество экземпляров точного значение с плавающей запятой.
Как говорит Дэвид, неотъемлемая проблема хэш-таблиц с ключами с плавающей запятой заключается в том, что хэш-таблицы используют равенство для идентификации ключей, а равенство с плавающей запятой является немного ненадежной концепцией из-за ошибок вычислений. Нет общей гарантии, что 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. Я использовал примеры base-10 для простоты набора, но, конечно, "float" обычно означает двоичное представление.
Точно такая же проблема применима и к двоичному дереву. Хеш-таблицы на самом деле не заботятся о том, каковы их ключевые данные, им просто важно, чтобы кто-то мог предоставить функцию h , которая сопоставляет ключи с целыми числами, например, для любых x и ] y вы хотите считать "равным", h (x) == h (y) .Затем для повышения производительности вы хотите, чтобы h больше не вводил «коллизий» (экземпляры h (x) == h (y) , где x! = Y ) чем случайный шанс. Для этого с поплавками нет никаких препятствий. Вы должны убедиться, что вы не включаете в хэш ничего, что не участвует в сравнениях, и это помогает, если вы включаете всю информацию, которая действительно участвует в сравнениях.
Если вы сможете решить вопрос о том, что именно вы на самом деле считаете, это может привести вас к нужной структуре данных. Если вам нужна некоторая терпимость в матчах, возможно, вам лучше всего отсортировать все свои числа с плавающей запятой, а затем искать кластеры значений.