Я хочу сделать набор чисел с плавающей запятой, но с изюминкой:
При проверке, является ли некоторое число с плавающей запятой x членом набора s, я хочу, чтобы тест возвращал true, если s содержит некоторое число с плавающей запятой f, такое что
abs(x - f) < tol
Другими словами, если набор содержит число, близкое к x, вернуть true. В противном случае вернуть ложь.
Один из способов сделать это, как я думал, состоит в том, чтобы хранить числа в куче, а не в наборе хэшей, и использовать правило приблизительного равенства, чтобы решить, содержит ли куча близкое число.
Однако это заняло бы log(N) времени, что неплохо, но было бы неплохо получить O(1), если бы такой алгоритм существовал.
У кого-нибудь есть идеи, как это возможно?
@н.м. это O (1), но не совсем точно, поскольку, если вам не повезет, вы можете найти совпадение в пределах 2tol. Вы можете сопоставить округленный ключ -> отсортированный список ключей, что является точным, но дает O (log n), если есть сильно заполненное ведро.
Это не может найти значения между дополнительными ключами. Рассмотрим кучу, содержащую число 1.0, которое в одинарной точности IEEE-754 равно 0011111110000000000000000000000000. Если tol = 1E-6 (примерно 2**-17), это означает, что мне нужно вычесть приблизительно 0000000000000000001111111 из мантиссы, затем добавить 0111100000000 мантисса, а также все числа между ними. Вы можете видеть, что справа от мантиссы есть семь единиц, поэтому вам нужно добавить 2 * (2 ** 7 - 1) числа к набору, примерно 256 чисел. Я должен согласиться, что технически это O (1), но накладные расходы немного высоки.
256x накладные расходы могут показаться не такими уж плохими, но есть еще 2 проблемы: 1) Если вы хотите, чтобы tol был 1E-3 вместо 1E-6, количество добавлений увеличивается в 1024 раза, так что теперь мы говорим о > 256 000 добавлений для каждого интересующего нас числа 2) если вы используете числа с двойной точностью, этот подход быстро становится непригодным для использования.
@PaulHankin «вы можете найти совпадение в пределах 2tol» Откажитесь от совпадений, которые вам не нужны. Это не слишком отличается от обычных хэш-коллизий. Вы просто отбрасываете записи с таким же хэшем, но отличающиеся от того, что вы ищете. Это только увеличивает количество столкновений. Вы можете получить, что все ваши записи будут иметь один и тот же хеш, но это может произойти и с обычной хеш-таблицей.
@JamesStrieter Конечно, Nx256 намного хуже, чем NlogN для всех реалистичных N, но я понятия не имею, откуда взялось 256. Возможно, из «а также всех чисел между ними», что определенно не то, что вам следует делать.
@н.м. 256 исходит из моего первого комментария, где я показываю, сколько добавлений нужно сделать, чтобы добавить 1.0 в набор с допуском 1E-6.
Вместо того, чтобы хранить набор чисел f-p, сохраните набор интервалов чисел f-p, центрированных на ваших исходных числах, и +/- допуск для сопоставления равенства. Это не повлияет на сложность поиска членства, но может предложить некоторое полезное улучшение для постоянного термина(ов). За счет места и некоторых предварительных вычислений.
@HighPerformanceMark, это классная идея! Простите мое невежество, но как найти ближайшее ведро за время O(1)?
Мне нужно сохранить число 1.0 (уже округленное до кратного tol
, поэтому никаких дальнейших действий не требуется) и больше ничего. Я не знаю, откуда взялась эта идея «все числа между ними». Я никогда не говорил, не имел в виду и не предлагал ничего подобного. Вы получаете число для сохранения, округляете его до кратного tol
и используете это значение в качестве ключа, сохраняете исходное число, которое вы получили с помощью этого ключа, и все. Конец истории.
@HighPerformanceMark предлагает почти то же самое, что и я. Мэтт Тиммерманс также предлагает почти то же самое. Наконец, ваша собственная идея маскирования битов также точно такая же.
У вас не может быть (математически обоснованного) «набора», который заменяет «равно» на «близко к допуску», потому что ваш оператор равенства должен быть транзитивным. Однако вы можете иметь набор (произвольных) чисел с плавающей запятой и проверять (произвольное) x
, если в вашем наборе есть число, близкое к tol
. В вашем случае tol
всегда одинаково? Это сила двойки? Насколько велика она обычно по сравнению с относительной точностью вашего типа с плавающей запятой?
Вам нужно изменить название вашего вопроса. Возможно, существует способ O (n) для создания набора, при этом каждый элемент требует O (1). Но я достаточно уверен, что невозможно создать, инициализировать и добавить n
элементов в набор за время O(1).
Две идеи, которые у меня были (и ни в коем случае не обязательно лучшие):
1.) Замаскируйте младшие N битов числа всеми нулями. Например, если вы хотите, чтобы допуск был ок. 1E-3, установите младшие 10 бит мантиссы в 0 при сложении. Сделайте то же самое при проверке.
Одним из предостережений этого подхода является то, что реальные компьютеры часто делают странные вещи с LSB мантиссы, когда вы не смотрите. Вы храните x = b00111111100000000000000000000000, и когда вы его извлекаете, вы получаете 00111111100000000000000000000000001, 0011111101111111111111111111111111111111111 и т. д. Причин для этого по-прежнему много, но суть в том, что это хрупко. Все, что полагается на равенство поплавка, хрупко.
2.) Создайте хешируемую структуру данных, содержащую разные поля из числа с плавающей запятой IEEE-754 по отдельности. Зачем это делать? ты спрашиваешь. Причина двоякая:
A.) Используя объект, который не является числом с плавающей запятой, вы не позволяете среде выполнения рассматривать это число как число с плавающей запятой. Я знаю, что это не должно иметь значения, но я столько раз видел искалеченный LSB, что это явно имеет значение, даже если трудно сказать, почему. Это преодолевает одну оговорку с сохранением кратного tol/4 в виде числа с плавающей запятой. Мне нравится идея округления числа до кратного tol. Единственным недостатком является то, что если вы храните число как число с плавающей запятой, среда выполнения все равно может искажать LSB, что является исходной мотивацией для этого вопроса.
B.) Вы можете сохранить только верхние N старших разрядов мантиссы - другими словами, выберите N так, чтобы 2**-N представляло относительный допуск, который вам нравится.
Это отражает идею округления до кратного tol, но также не сообщает среде выполнения и/или процессору, что это число с плавающей запятой, тем самым предотвращая искажение LSB.
Интересно услышать другие идеи, критику и т.
"Вы храните x = b00111111100000000000000000000000, и когда вы его извлекаете, вы получаете 0011111110000000000000000000000001, 0011111101111111111111111111111111111111111". Так делают только сломанные компьютеры. «Все, что полагается на равенство с плавающей запятой, является britte». Неправильно, иначе вы не сможете хэшировать числа с плавающей запятой.
@н.м. Тогда мне пришлось бы выбросить все компьютеры НАСА в мусорку, что я бы и сделал с удовольствием, но, к сожалению, я не могу позволить себе новые :/
Если вы не слишком придирчивы к допуску, вы можете округлить каждое число до ближайшего кратного tol/4.
Затем вы можете использовать хэш-карту, но когда вы добавляете число x, добавьте пол (4x/tol), пол (4x/tol+1) и пол (4x/tol-1).
Когда вы ищете число x, ищите этаж (4x/tol), этаж (4x/tol+1) и этаж (4x/tol-1).
Вы обязательно найдете совпадение в пределах tol/2, и вы можете найти совпадение в пределах tol.
Вместо другого набора измените значение «закрыть».
Создайте функцию, которая отображает каждое конечное float
в целое число.
Мысленно поместите каждое положительное float
в список, отсортированный по значению. 0.0 находится в индексе 0, а MAX_FLOAT
находится в индексе N
. (Вероятно, для отрицательных значений: от -MAX_FLOAT
до -0,0 сопоставляется с -N
до 0. общий порядок
Чтобы определить, являются ли 2 значения float
«близкими», вычтите их индексы и сравните с допуском.
Это поддерживает идею плавающей запятой в числах с плавающей запятой, поскольку допуск является фиксированным целым числом в домене отображения индекса, но масштабируется в домене float
.
Округлите сохраненные ключи до числа, кратного
tol
. Найдитеx'
,x' - tol
иx'+tol
, гдеx'
— ключ поиска, округленный до кратногоtol
. Помогает, еслиtol
— это2^n
, гдеn
— (возможно, отрицательное) целое число.