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

Question

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

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

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

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

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

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

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

Спасибо

Answer 1

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

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

Answer 2

Вам нужна только отсортированная таблица записей, у которых есть идентификаторы для начала. Код может составить для вас индекс и использовать индекс с двоичным поиском для поиска. Индекс будет 40кб. Вы, вероятно, сможете сэкономить столько. Его можно было бы сделать 30 КБ, если действительно 3-байтовые идентификаторы, но это было бы ненужным осложнением, если вам действительно не хватает 10 КБ.

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

VAR_GLOBAL
  entries : ARRAY[1..entryCount] OF ST_Entry := ...; // you need to preinitialize this array here
  index: ARRAY[1..entryCount] OF DINT;
  _dummy : BOOL := BuildIndex(ADR(index), ADR(entries), entryCount);
END_VAR
VAR_GLOBAL CONSTANT
  entryCount : DINT := 10000;
END_VAR

// Called once during PLC initialization only. Returns FALSE always.
FUNCTION BuildIndex : BOOL
VAR_INPUT
  index: POINTER TO DINT;
  entries : POINTER TO ST_ENTRY;
  count : DINT;
END_VAR
WHILE count > 0 DO
  index[count] := entries[count].Id;
  count := count - 1;
END_WHILE
END_FUNCTION

С такой настройкой индексированный поиск через двоичный поиск очень прост:

FUNCTION LookupEntry : REFERENCE TO ST_Entry
VAR_INPUT
  id : DINT;
END_VAR
VAR
  begin : DINT := 1;
  mid : DINT;
  end : DINT := GVL.entryCount;
  midId : DINT;
END_VAR
WHILE TRUE DO
  mid := (begin + end) / 2;
  midId := index[mid];
  IF midId = id THEN
    LookupEntry REF= entries[mid];
    EXIT;
  END_IF
  IF mid=begin AND mid=end THEN
    EXIT;
  END_IF
  IF midId < id THEN
    begin := mid;
  ELSE
    end := mid;
  END_IF
END_WHILE;
// may return an invalid reference, use of reference will throw
END_FUNCTION