Быстрый алгоритм хэширования для отображения / квантования набора чисел с плавающей точкой на небольшой набор отсортированных чисел с плавающей точкой

Question

С моим заявлением у меня есть

• Коллекция X:тысячи чисел с плавающей запятой с диапазоном значений [0, 1], не отсортированных.
• Коллекция Y:11 значений с плавающей точкой в диапазоне от [0, 1], отсортированных.
• Размер X известен.Пусть это будет L.

Цель состоит в том, чтобы квантовать X и сопоставить его с Y, чтобы мы получили хэш-массив индексов Y для X.В конечном счете Y будет затем квантован на 10 дискретных объектов, указывающих на него.

Пример, чтобы было немного понятнее,

• Y = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
• X = [0.678, 0.124, ..., 1.0, ., 0.013, 0.475]

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

• H(Y[0]) = H(0.678) = 6
• H(Y[1]) = H(0.124) = 1
• H(Y[n-2]) = H(0.013) = 0
• H(Y[n-1]) = H(0.475) = 4

Попытки

Наивно, я пробовал линейный и двоичный поиск для позиционирования каждого элемента X в Y так, чтобы элемент был найден между соседней парой элементов в Y.

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

Вопрос

Каков наилучший способ такого рода хэширования / квантования?X не отсортирован.

Спасибо!

Answer 1

Возьмем X, умножим, скажем, на 10 000, округлим в меньшую сторону до ближайшего целого числа.В простом C z = (int) (x умножить на 10000.0).

Существует 10 000 возможных значений z.Для большинства значений z вы можете определить индекс по z.Итак, создайте таблицу с 10 000 записями.В таблице сохраните индекс i, если вы можете доказать, что x должно быть сопоставлено с i, зная z, и сохраните -1, если вы не можете этого доказать.

В результате вы получаете правильное значение, вероятно, в 9 980 из 10 000 значений, а затем используете любой имеющийся у вас медленный алгоритм для оставшихся 1 из 500 значений.

пс.Тот же размер таблицы будет использоваться для чисел с двойной точностью.Каким бы ни был размер таблицы, будет только несколько значений X, которые невозможно правильно сопоставить с помощью этого метода, возможно, 10 или 20.Если вы берете таблицу размером 10 000, то 99,8% или 99,9% отображаются правильно, а для 0,1% или 0,2% требуется медленный алгоритм.Точно то же самое происходит и с double.Вы могли бы использовать 1000 записей, тогда 10 или 20 неудачных записей составили бы 1% или 2%.

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