Быстрый алгоритм поиска-вставки-удаления для процессора с низким энергопотреблением

Question

У нас есть приложение, работающее на маломощном процессоре, которое должно быстро реагировать на поступающие данные.Данные поступают со связанным ключом.Каждая клавиша находится в диапазоне от 0 до 0xFE (макс. 0xFF).Размер данных варьируется от 1 до 4 КБ.Система обрабатывает данные как:

data in
key lookup -> insert key & data if not found
buffer data in existing key

После некоторого события ключ и связанные данные уничтожаются.

Мы тестируем несколько решений:

1. Предварительно выделено std::vector<std::pair<int,unsigned char *>>, которое ищет ключевое значение на основе позиции индекса.

2. std::map<int, unsigned char *>

3. Красно-черное дерево

4. std::vector<...> с двоичной сортировкой и двоичным поиском

Есть ли другие алгоритмы, которые могут быть быстрыми при вставке-поиске-удалении?

Спасибо.

Answer 1

std::map использует само сбалансированное дерево (например, красно-черное дерево), поэтому нет смысла повторно его реализовывать.

Сортировка std::vector с двоичным поиском имеет ту же производительностьсбалансированное бинарное дерево.Разница в том, что размещение ключа в середине вектора стоит дорого.

Поскольку у ваших ключей очень ограниченный диапазон, ваш лучший выбор аналогичен первому предложению:

std::vector<unsigned char *> data(0xFF);  // no need to have a pair

Таким образом, простая проверка data[key] == NULL показывает, существуют ли данные для этого ключа или нет.Если бы это был я, я бы даже упростил это:

unsigned char *data[0xFF];

Answer 2

Если ключ находится в диапазоне [0, 0xFF), то вы можете использовать это:

std::vector<std::string> lut(0xFF); //lookup table

//insert 
lut[key] = data; //insert data at position 'key'

//delete 
lut[key].clear(); //clear - it means data empty

//search
if(lut[key].empty() )  //empty string means no key, no data!
{
   //key not found
}
else
{
    std::string & data = lut[key]; //found
}

Обратите внимание, что я использовал пустую строку, чтобы указать, что данные не существуют.