Самый эффективный контейнер для карты uint16_t to uint16_t

Question

Я занимаюсь разработкой программы для машины с очень низкой вычислительной мощностью, в которой я хочу сопоставить uint16_t ключи с uint16_t значениями.

В настоящее время я использую std::map использовать небезопасное чтение:

std::map<uint16_t, uint16_t> m;
//fill m only once

while(true){
    auto x = m[y];
}

Производительность по-прежнему неприемлема для требований.Есть ли лучшее решение с точки зрения скорости выполнения?

Редактировать: Некоторая информация:

• Общее количество элементов меньше 500
• Вставка выполняется только один раз
• Запрос значений выполняется более 250 раз / с
• Ключи и значения уникальны
• Оперативная память очень ограничена, общая оперативная память составляет 512 КБ, свободная оперативная память для этой части кода составляет менее 50 КБ
• 100 МГц одноядерный процессор

Answer 1

• Общее количество элементов меньше 500
• Вставка выполняется только один раз

Сохраните массив фиксированного размера (500)пары ключ-значение плюс «число допустимых элементов», если фактический размер известен только во время выполнения;заполнить его данными и отсортировать;тогда вы можете просто выполнить бинарный поиск.

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

Answer 2

Обычно двоичное дерево (std::map, которое вы используете в данный момент) обеспечивает адекватную производительность. Ваш бюджет процессора должен быть очень маленьким.

Бинарный поиск, вероятно, не будет намного быстрее. Хеш-таблица (std::unordered_map) может быть решением.

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

std::unordered_map<uint16_t, uint16_t> m(503); // 503 is a prime
m.emplace(123, 234);
m.emplace(2345, 345);

std::cout << m.find(123)->second; // don't use operator[] to avoid creating entries
std::cout << m.find(2345)->second;

Чтобы проверить качество функции хеширования, выполните итерацию по всем сегментам, вызвав bucket_size() и сложите все, что больше 1 (то есть столкновение).

Answer 3

Без дополнительной информации о вашей карте,

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

если вы намереваетесь использовать изрядное количество данных, но недостаточно, чтобы было слишком много коллизий хешей, std :: unordered_map амортизировало O (1) поисков, и если вас не волнует порядок, в котором они хранятся в том, что могло бы быть хорошим предположением.

если вы используете не много данных и хотите, чтобы они были гибкими, std :: vector - хороший выбор

Поскольку мы знаем только то, что это карта от uin16_t до uint16_t, лучшего ответа нет.