Эффективно «хэш» Набор значений для Indice
Прежде всего, отказ от ответственности; hash — несколько неточный термин для того, к чему я стремлюсь, пожалуйста, не стесняйтесь предлагать лучший заголовок.
В любом случае, я сейчас пытаюсь запрограммировать сложный пространственный алгоритм, работающий в режиме реального времени. Чтобы сэкономить циклы, я решил создать справочную таблицу, которая содержит все 32 000 возможностей.
Если бы я делал это условно, значения (Inclusive range и count field) 2x +0 -> +15 и 3x -2 -> +2 были бы сопоставлены с двумя четырехбитными и тремя трехбитными значениями соответственно, давая мне размер таблицы поиска 2 ^ (2 * 4 + 3 * 3) = 131 072 записей, почти 410% отходов.
Принимая во внимание природу алгоритма, коллизии могут нанести вред его функциональности (поэтому нет традиционных хеш-функций, если я не смогу гарантировать коллизии со всеми соответствующими значениями). Кроме того, структура, с которой я работаю, довольно большая (то есть я бы / действительно / хотел бы избежать выделения более 200% того, что мне нужно). Наконец, поскольку на эту таблицу будут ссылаться так часто, я бы хотел избежать издержек на традиционную хэш-таблицу как при поиске в корзине, так и при чрезмерно сложной хэш-функции.
Приняв более традиционный компьютерный подход, я начинаю твердо полагать, что решение лежит в некоторой математике преобразования базы, о которой я совершенно не знаю. Есть идеи, если это так?
Решение
Вы можете рассчитать индекс так же, как рассчитали максимальное количество комбинаций, умножив каждый элемент. Возьмите каждый элемент из наиболее значимого в наименее значимый, добавьте константу, чтобы он варьировался от 0 до n-1, и умножьте на количество оставшихся комбинаций.
Учитывая ваши 0 до 15 значений a, b (диапазон 16) и от -2 до +2 значений c, d, e (диапазон 5):
index = a * 16*5*5*5 + b * 5*5*5 + (c+2) * 5*5 + (d+2) * 5 + (e+2);
Другие решения