Таблица поиска для отсортированных непоследовательных элементов

Question

У меня есть массив элементов.Массив сортируется по идентификатору элементов, но идентификаторы являются непоследовательными, например, в номерах идентификаторов есть пробелы.

Сегодня я использую бинарный поиск, чтобы найти конкретный идентификатор.

Идентификатор составляет 3 байта, что дает около 16 миллионов возможностей.Количество идентификаторов в данном массиве намного меньше, возможно, 10 000.

Это встроенная платформа / plc, что означает, что у меня не может быть таблица поиска 16 МБ, которая занимает слишком много памяти.Я смотрел на наборы битов такое, но я не уверен, что это правильный подход или как рассчитать смещение массива из этого.

Я понимаю, что это может быть сложным, учитывая, что я хочусделайте старый добрый компромисс «скорость памяти», но у меня очень мало памяти, может быть, 2 МБ или меньше, чтобы сэкономить для этого.Но аппаратная часть исправлена.

Редактировать: элементы массива являются фиксированными для данного приложения, нет вставок или удалений элементов массива.

Как я могу построить / предварительно вычислить таблицу поиска илипохоже на ускорение поиска идентификатора?

Спасибо

Answer 1

Я предполагаю, что бинарный поиск слишком медленный.Поскольку таблица фиксированная, во время выполнения не будет добавлений или удалений, вы можете посмотреть на «идеальное решение».В Wiki есть очень хорошее художественное объяснение, объясняющее это https://en.wikipedia.org/wiki/Perfect_hash_function

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