Есть ли способ сделать набор поплавков с допуском и по-прежнему искать O (1)?

Я хочу сделать набор чисел с плавающей запятой, но с изюминкой:

При проверке, является ли некоторое число с плавающей запятой x членом набора s, я хочу, чтобы тест возвращал true, если s содержит некоторое число с плавающей запятой f, такое что

abs(x - f) < tol

Другими словами, если набор содержит число, близкое к x, вернуть true. В противном случае вернуть ложь.

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

Однако это заняло бы log(N) времени, что неплохо, но было бы неплохо получить O(1), если бы такой алгоритм существовал.

У кого-нибудь есть идеи, как это возможно?

Округлите сохраненные ключи до числа, кратного tol. Найдите x', x' - tol и x'+tol, где x' — ключ поиска, округленный до кратного tol. Помогает, если tol — это 2^n, где n — (возможно, отрицательное) целое число.

n. m. 03.12.2022 15:21

@н.м. это O (1), но не совсем точно, поскольку, если вам не повезет, вы можете найти совпадение в пределах 2tol. Вы можете сопоставить округленный ключ -> отсортированный список ключей, что является точным, но дает O (log n), если есть сильно заполненное ведро.

Paul Hankin 03.12.2022 15:25

Это не может найти значения между дополнительными ключами. Рассмотрим кучу, содержащую число 1.0, которое в одинарной точности IEEE-754 равно 0011111110000000000000000000000000. Если tol = 1E-6 (примерно 2**-17), это означает, что мне нужно вычесть приблизительно 0000000000000000001111111 из мантиссы, затем добавить 0111100000000 мантисса, а также все числа между ними. Вы можете видеть, что справа от мантиссы есть семь единиц, поэтому вам нужно добавить 2 * (2 ** 7 - 1) числа к набору, примерно 256 чисел. Я должен согласиться, что технически это O (1), но накладные расходы немного высоки.

James Strieter 03.12.2022 15:29

256x накладные расходы могут показаться не такими уж плохими, но есть еще 2 проблемы: 1) Если вы хотите, чтобы tol был 1E-3 вместо 1E-6, количество добавлений увеличивается в 1024 раза, так что теперь мы говорим о > 256 000 добавлений для каждого интересующего нас числа 2) если вы используете числа с двойной точностью, этот подход быстро становится непригодным для использования.

James Strieter 03.12.2022 15:31

@PaulHankin «вы можете найти совпадение в пределах 2tol» Откажитесь от совпадений, которые вам не нужны. Это не слишком отличается от обычных хэш-коллизий. Вы просто отбрасываете записи с таким же хэшем, но отличающиеся от того, что вы ищете. Это только увеличивает количество столкновений. Вы можете получить, что все ваши записи будут иметь один и тот же хеш, но это может произойти и с обычной хеш-таблицей.

n. m. 03.12.2022 15:39

@JamesStrieter Конечно, Nx256 намного хуже, чем NlogN для всех реалистичных N, но я понятия не имею, откуда взялось 256. Возможно, из «а также всех чисел между ними», что определенно не то, что вам следует делать.

n. m. 03.12.2022 15:42

@н.м. 256 исходит из моего первого комментария, где я показываю, сколько добавлений нужно сделать, чтобы добавить 1.0 в набор с допуском 1E-6.

James Strieter 03.12.2022 15:44

Вместо того, чтобы хранить набор чисел f-p, сохраните набор интервалов чисел f-p, центрированных на ваших исходных числах, и +/- допуск для сопоставления равенства. Это не повлияет на сложность поиска членства, но может предложить некоторое полезное улучшение для постоянного термина(ов). За счет места и некоторых предварительных вычислений.

High Performance Mark 03.12.2022 15:50

@HighPerformanceMark, это классная идея! Простите мое невежество, но как найти ближайшее ведро за время O(1)?

James Strieter 03.12.2022 15:52

Мне нужно сохранить число 1.0 (уже округленное до кратного tol, поэтому никаких дальнейших действий не требуется) и больше ничего. Я не знаю, откуда взялась эта идея «все числа между ними». Я никогда не говорил, не имел в виду и не предлагал ничего подобного. Вы получаете число для сохранения, округляете его до кратного tol и используете это значение в качестве ключа, сохраняете исходное число, которое вы получили с помощью этого ключа, и все. Конец истории.

n. m. 03.12.2022 16:54

@HighPerformanceMark предлагает почти то же самое, что и я. Мэтт Тиммерманс также предлагает почти то же самое. Наконец, ваша собственная идея маскирования битов также точно такая же.

n. m. 03.12.2022 17:04

У вас не может быть (математически обоснованного) «набора», который заменяет «равно» на «близко к допуску», потому что ваш оператор равенства должен быть транзитивным. Однако вы можете иметь набор (произвольных) чисел с плавающей запятой и проверять (произвольное) x, если в вашем наборе есть число, близкое к tol. В вашем случае tol всегда одинаково? Это сила двойки? Насколько велика она обычно по сравнению с относительной точностью вашего типа с плавающей запятой?

chtz 03.12.2022 23:56

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

Jim Mischel 05.12.2022 19:37
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
13
87
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

Две идеи, которые у меня были (и ни в коем случае не обязательно лучшие):

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». Неправильно, иначе вы не сможете хэшировать числа с плавающей запятой.

n. m. 03.12.2022 17:05

@н.м. Тогда мне пришлось бы выбросить все компьютеры НАСА в мусорку, что я бы и сделал с удовольствием, но, к сожалению, я не могу позволить себе новые :/

James Strieter 10.12.2022 15:13
Ответ принят как подходящий

Если вы не слишком придирчивы к допуску, вы можете округлить каждое число до ближайшего кратного 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.

Другие вопросы по теме

Похожие вопросы

Подсчитайте простой идентификатор тестирования AB с модулем из любой строки
Бинарный поиск с использованием средних геометрических
Что именно представляет эпсилон в основной теореме?
Я пытаюсь сделать простой алгоритм градиентного спуска в python, но он возвращается после прохождения самой низкой точки
Как найти путь в матрице, который должен проходить через несколько ячеек
Проблема реализации с сортировкой слиянием
Длина самой длинной убывающей подпоследовательности, построенной путем добавления элементов в конец и начало с использованием динамического программирования
Как можно разделить строки списка на максимально большие части (согласно лимиту строк) и максимально равные пакеты строк?
Производительность генератора паролей: Python против Javascript (скрипт приложений Google)
Присвоение цвета узлам графа таким образом, чтобы никакие два соседних узла не имели одинаковый цвет