Как реализовать хеширование с плавающей точкой с приближенным равенством

15

Допустим, у нас есть следующий класс 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. Но как это сочетается с «общеизвестным», что поплавки не должны сравниваться напрямую? Если вы реализуете оператор равенства путем сравнения чисел с плавающей запятой, инструменты статического анализа будут жаловаться. Правы ли они на это?

Куница
источник
9
почему вопрос имеет тег Java?
Laiv
8
О вашем обновлении: я бы сказал, что хеширование с плавающей точкой, как правило, сомнительная вещь. Старайтесь избегать использования поплавков в качестве ключей или элементов набора.
Дж. Фабиан Мейер
6
@Neil: В то же время, округление не звучит как целые числа? Под этим я подразумеваю: если вы можете округлить, скажем, до тысячных долей градуса, то вы можете просто использовать представление с фиксированной точкой - целое число, выражающее температуру в тысячных долях градуса. Для простоты использования вы можете иметь метод получения / установки прозрачного преобразования из / в число с плавающей точкой, если вы хотите ...
Matthieu M.
4
Кельвины больше не градусов. Степени также неоднозначны. Почему бы просто не позвонить kelvin?
Соломон Уко
5
Python имеет более или менее отличную поддержку с фиксированной запятой , возможно, это что-то для вас.
Йонас Шефер

Ответы:

41

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

Нечеткое равенство нарушает требования, которые Java накладывает на equalsметод, а именно транзитивность , то есть то, что если x == yи y == z, то x == z. Но если вы делаете нечеткое равенство, например, с эпсилоном 0,1, то 0.1 == 0.2и 0.2 == 0.3, но 0.1 == 0.3не выполняется.

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

Поэтому я настоятельно рекомендую вам не делать этого.

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

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

Себастьян Редл
источник
2
интересные мысли. Таким образом, накапливая миллионы эпсилонов и используя транзитивность, вы можете сделать вывод, что все равно чему-то другому :-) Но признает ли это математическое ограничение дискретное основание с плавающей запятой, которое во многих случаях является приближением числа, которое они должны представлять?
Кристоф
@Christophe Интересный вопрос. Если вы подумаете об этом, вы увидите, что этот подход создаст один класс большой эквивалентности из числа с плавающей точкой, разрешение которого больше, чем у эпсилона (конечно, с центром в 0), и оставит другие числа с плавающей точкой в ​​своем собственном классе. Но это не главное, реальная проблема заключается в том, что заключение о том, что 2 числа равны, зависит от того, сравнивается ли третье число и в каком порядке это делается.
Ордос
Обращаясь к редактированию @ OP, я бы добавил, что некорректность с плавающей точкой ==должна «заразить» ==типы, содержащие их. То есть, если они последуют вашему совету относительно точного равенства, их инструмент статического анализа должен быть дополнительно настроен на предупреждение о том, что равенство используется Temperature. Это единственное, что ты можешь сделать, правда.
HTNW
@HTNW: Это было бы слишком просто. Класс отношений может иметь float approximationполе, в котором не участвует ==. Кроме того, инструмент статического анализа уже выдаст предупреждение внутри ==реализации классов, когда один из сравниваемых членов является floatтипом.
MSalters
@MSalters? Предположительно, достаточно настраиваемые инструменты статического анализа могут делать то, что я предложил, просто отлично. Если у класса есть floatполе, в котором он не участвует ==, не настраивайте инструмент для предупреждения ==об этом классе. Если класс делает, то, вероятно, пометка класса ==как «слишком точного» заставит инструмент игнорировать такого рода ошибки в реализации. Например, в Java, если @Deprecated void foo(), то void bar() { foo(); }это предупреждение, но @Deprecated void bar() { foo(); }это не так. Может быть, многие инструменты не поддерживают это, но некоторые могут.
HTNW
16

Удачи

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

Пример:

Предположим, что каждая точка хэширует свое уникальное хеш-значение.

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

  1. Для каждых двух точек в эпсилоне друг от друга, которые не разделяют одно и то же значение хеш-функции.

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

Есть несколько случаев, когда это не будет иметь место:

  • Положительная / Отрицательная Бесконечность
  • NaN
  • Несколько Денормализованных диапазонов, которые не могут быть связаны с основным диапазоном для данного эпсилона.
  • возможно, несколько других конкретных форматов

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

результат

Либо> = 99% всего диапазона с плавающей запятой хеширует к одному значению, серьезно компрометируя намерение значения хеша (и любое устройство / контейнер, полагающееся на довольно распределенный хеш с низким коллизией).

Или эпсилон таков, что разрешены только точные совпадения.

зернистый

Вы могли бы, конечно, пойти на гранулярный подход вместо этого.

При таком подходе вы определяете точные сегменты вплоть до определенного разрешения. то есть:

[0.001, 0.002)
[0.002, 0.003)
[0.003, 0.004)
...
[122.999, 123.000)
...

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

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

Kain0_0
источник
2
Я согласен, что детальный подход здесь, вероятно, будет лучшим, если он соответствует требованиям OP. Хотя я боюсь, что OP имеет требования типа +/- 0,1%, то есть он не может быть гранулированным.
Нил
4
@DocBrown Часть "не возможно" верна. Если равенство на основе эпсилона должно подразумевать, что хеш-коды равны, то все хеш-коды автоматически равны, поэтому хеш-функция больше не нужна. Подход с использованием сегментов может быть плодотворным, но у вас будут числа с разными хеш-кодами, которые произвольно близки друг к другу.
J. Fabian Meier
2
Подход корзины может быть изменен путем проверки не только корзины с точным хеш-ключом, но также двух соседних блоков (или хотя бы одного из них) на предмет их содержимого. Это устраняет проблему этих крайних случаев из-за стоимости увеличения времени выполнения не более чем в два раза (при правильной реализации). Однако это не меняет общий порядок времени выполнения.
Док Браун,
Пока вы правы духом, не все рухнет. При фиксированном небольшом эпсилоне большинство чисел будут равны только себе. Конечно, для тех эпсилон будет бесполезен, поэтому, опять же, по духу вы правы.
Карстен С.
1
@CarstenS Да, мое утверждение о том, что 99% хэшей диапазона к одному хешу фактически не покрывают весь диапазон с плавающей запятой. Существует много значений верхнего диапазона, которые разделены более чем эпсилоном, который будет хэшировать свои собственные уникальные сегменты.
Kain0_0
7

Вы можете смоделировать свою температуру как целое число под капотом. Температура имеет естественную нижнюю границу (-273,15 по Цельсию). Итак, double (-273.15 равно 0 для вашего целого числа). Второй элемент, который вам нужен, это детализация вашего отображения. Вы уже используете эту гранулярность неявно; это твой ЭПСИЛОН.

Просто поделите свою температуру на EPSILON и возьмите ее за пол, теперь ваш хэш и ваш ровный будут вести себя синхронно. В Python 3 целое число не ограничено, EPSILON может быть меньше, если хотите.

ВНИМАНИЕ! Если вы измените значение EPSILON и сериализовали объект, они будут несовместимы!

#Pseudo code
class Temperature:
    def __init__(self, degrees):
        #CHECK INVALID VALUES HERE
        #TRANSFORM TO KELVIN HERE
        self.degrees = Math.floor(kelvin/EPSILON)
Алессандро Теруцци
источник
1

Реализация хэш-таблицы с плавающей точкой, которая может находить вещи, «приблизительно равные» данному ключу, потребует использования нескольких подходов или их комбинации:

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

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

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

Supercat
источник
0

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

Здесь есть некоторая путаница: если два числа с плавающей точкой сравниваются равными, они равны. Чтобы проверить, равны ли они, используйте «==«. Иногда вы не хотите проверять равенство, но когда вы это делаете, «==» - это путь.

gnasher729
источник
0

Это не ответ, а расширенный комментарий, который может быть полезен.

Я работал над аналогичной проблемой, используя MPFR (на основе GNU MP). Подход «ведра», описанный @ Kain0_0, кажется, дает приемлемые результаты, но имейте в виду ограничения, выделенные в этом ответе.

Я хотел добавить, что - в зависимости от того, что вы пытаетесь сделать - использование «точной» ( caveat emptor ) системы компьютерной алгебры, такой как Mathematica, может помочь дополнить или проверить неточную числовую программу. Это позволит вам вычислять результаты, не беспокоясь о округлении, например, 7*√2 - 5*√2даст 2вместо 2.00000001или аналогичный. Конечно, это приведет к дополнительным осложнениям, которые могут или не стоит того.

BurnsBA
источник