Допустим, у нас есть следующий класс Python (проблема существует в Java точно так же с equals
и hashCode
)
class Temperature:
def __init__(self, degrees):
self.degrees = degrees
где degrees
температура в Кельвинах как поплавок. Теперь я хотел бы реализовать тестирование на равенство и хэширование Temperature
таким образом, чтобы
- сравнивает поплавки с разницей в эпсилон вместо прямого тестирования на равенство,
- и соблюдает контракт, который
a == b
подразумеваетhash(a) == hash(b)
.
def __eq__(self, other):
return abs(self.degrees - other.degrees) < EPSILON
def __hash__(self):
return # What goes here?
Документация Python говорит немного о хэшировании чисел, чтобы гарантировать это, hash(2) == hash(2.0)
но это не совсем та же проблема.
Я даже на правильном пути? И если да, то каков стандартный способ реализации хеширования в этой ситуации?
Обновление : теперь я понимаю, что этот тип проверки на равенство для поплавков устраняет транзитивность ==
и equals
. Но как это сочетается с «общеизвестным», что поплавки не должны сравниваться напрямую? Если вы реализуете оператор равенства путем сравнения чисел с плавающей запятой, инструменты статического анализа будут жаловаться. Правы ли они на это?
источник
kelvin
?Ответы:
Нечеткое равенство нарушает требования, которые Java накладывает на
equals
метод, а именно транзитивность , то есть то, что еслиx == y
иy == z
, тоx == z
. Но если вы делаете нечеткое равенство, например, с эпсилоном 0,1, то0.1 == 0.2
и0.2 == 0.3
, но0.1 == 0.3
не выполняется.Хотя Python не документирует такое требование, все же последствия наличия непереходного равенства делают его очень плохой идеей; рассуждения о таких типах вызывают головную боль.
Поэтому я настоятельно рекомендую вам не делать этого.
Либо обеспечьте точное равенство и основывайте свой хэш на этом очевидным образом, либо предоставьте отдельный метод для нечеткого сопоставления, либо используйте подход класса эквивалентности, предложенный Каином. Хотя в последнем случае я рекомендую вам зафиксировать свое значение для репрезентативного члена класса эквивалентности в конструкторе, а затем перейти к простому точному равенству и хешированию для всего остального; так легче рассуждать о типах.
(Но если вы сделаете это, вы могли бы также использовать представление с фиксированной запятой вместо числа с плавающей запятой, то есть вы используете целое число для подсчета тысячных долей или любой необходимой вам точности.)
источник
==
должна «заразить»==
типы, содержащие их. То есть, если они последуют вашему совету относительно точного равенства, их инструмент статического анализа должен быть дополнительно настроен на предупреждение о том, что равенство используетсяTemperature
. Это единственное, что ты можешь сделать, правда.float approximation
поле, в котором не участвует==
. Кроме того, инструмент статического анализа уже выдаст предупреждение внутри==
реализации классов, когда один из сравниваемых членов являетсяfloat
типом.float
поле, в котором он не участвует==
, не настраивайте инструмент для предупреждения==
об этом классе. Если класс делает, то, вероятно, пометка класса==
как «слишком точного» заставит инструмент игнорировать такого рода ошибки в реализации. Например, в Java, если@Deprecated void foo()
, тоvoid bar() { foo(); }
это предупреждение, но@Deprecated void bar() { foo(); }
это не так. Может быть, многие инструменты не поддерживают это, но некоторые могут.Удачи
Вы не сможете достичь этого, не будучи глупыми с хэшами или не пожертвовав эпсилоном.
Пример:
Предположим, что каждая точка хэширует свое уникальное хеш-значение.
Поскольку числа с плавающей запятой являются последовательными, до заданного значения с плавающей запятой будет до k чисел и до k чисел после заданного значения с плавающей запятой, которые находятся в пределах некоторого эпсилона от данной точки.
Для каждых двух точек в эпсилоне друг от друга, которые не разделяют одно и то же значение хеш-функции.
Есть несколько случаев, когда это не будет иметь место:
Однако> = 99% диапазона с плавающей запятой хеширует одно значение для любого значения epsilon, которое включает, по крайней мере, одно значение с плавающей запятой выше или ниже некоторого заданного значения с плавающей запятой.
результат
Либо> = 99% всего диапазона с плавающей запятой хеширует к одному значению, серьезно компрометируя намерение значения хеша (и любое устройство / контейнер, полагающееся на довольно распределенный хеш с низким коллизией).
Или эпсилон таков, что разрешены только точные совпадения.
зернистый
Вы могли бы, конечно, пойти на гранулярный подход вместо этого.
При таком подходе вы определяете точные сегменты вплоть до определенного разрешения. то есть:
Каждое ведро имеет уникальный хеш, и любая плавающая точка внутри ведра сравнивается с любой другой плавающей точкой в том же ведре.
К сожалению, все еще возможно, чтобы два поплавка находились на расстоянии в эпсилон, и имели два отдельных хэша.
источник
Вы можете смоделировать свою температуру как целое число под капотом. Температура имеет естественную нижнюю границу (-273,15 по Цельсию). Итак, double (-273.15 равно 0 для вашего целого числа). Второй элемент, который вам нужен, это детализация вашего отображения. Вы уже используете эту гранулярность неявно; это твой ЭПСИЛОН.
Просто поделите свою температуру на EPSILON и возьмите ее за пол, теперь ваш хэш и ваш ровный будут вести себя синхронно. В Python 3 целое число не ограничено, EPSILON может быть меньше, если хотите.
ВНИМАНИЕ! Если вы измените значение EPSILON и сериализовали объект, они будут несовместимы!
источник
Реализация хэш-таблицы с плавающей точкой, которая может находить вещи, «приблизительно равные» данному ключу, потребует использования нескольких подходов или их комбинации:
Округлите каждое значение с приращением, которое несколько больше, чем «нечеткий» диапазон, перед сохранением его в хеш-таблице, и при попытке найти значение проверьте в хеш-таблице округленные значения выше и ниже искомого значения.
Сохраните каждый элемент в хэш-таблице, используя ключи выше и ниже искомого значения.
Обратите внимание, что использование любого из этих подходов, вероятно, потребует, чтобы записи хеш-таблицы не идентифицировали элементы, а скорее списки, поскольку, вероятно, будет иметься несколько элементов, связанных с каждым ключом. Первый подход, приведенный выше, сведет к минимуму требуемый размер хеш-таблицы, но каждый поиск элемента, которого нет в таблице, потребует двух просмотров хеш-таблицы. Второй подход позволит быстро определить, что элементов нет в таблице, но обычно требует, чтобы таблица содержала примерно вдвое больше записей, чем требовалось бы в противном случае. Если кто-то пытается найти объекты в двумерном пространстве, может быть полезно использовать один подход для направления X и один для направления Y, чтобы вместо того, чтобы каждый элемент хранился один раз, но требовалось четыре операции запроса для каждого поиска или возможность использовать один поиск, чтобы найти предмет, но хранить каждый предмет по четыре раза,
источник
Конечно, вы можете определить «почти равный», удалив, скажем, последние восемь битов мантиссы, а затем сравнив или хэшируя. Проблема в том, что числа, очень близкие друг к другу, могут быть разными.
Здесь есть некоторая путаница: если два числа с плавающей точкой сравниваются равными, они равны. Чтобы проверить, равны ли они, используйте «==«. Иногда вы не хотите проверять равенство, но когда вы это делаете, «==» - это путь.
источник
Это не ответ, а расширенный комментарий, который может быть полезен.
Я работал над аналогичной проблемой, используя MPFR (на основе GNU MP). Подход «ведра», описанный @ Kain0_0, кажется, дает приемлемые результаты, но имейте в виду ограничения, выделенные в этом ответе.
Я хотел добавить, что - в зависимости от того, что вы пытаетесь сделать - использование «точной» ( caveat emptor ) системы компьютерной алгебры, такой как Mathematica, может помочь дополнить или проверить неточную числовую программу. Это позволит вам вычислять результаты, не беспокоясь о округлении, например,
7*√2 - 5*√2
даст2
вместо2.00000001
или аналогичный. Конечно, это приведет к дополнительным осложнениям, которые могут или не стоит того.источник