Самая быстрая карта C++?

Важное предупреждение: Если вы не измерили (а ваш вопрос предполагает, что нет), что производительность карты существенно влияет на производительность вашего приложения (большой процент времени тратится на поиск и обновление карту) не пытайтесь сделать это быстрее. Придерживайтесь std :: map (или std :: unordered_map или любой доступной реализации hash_map ). Ускорение вашего приложения на 1%, вероятно, не окупится. Вместо этого сделайте это без ошибок.

Повторяя ответ Ричарда: измерьте производительность с помощью различных реализаций карты, используя ваши реальные классы и реальные данные.

Некоторые дополнительные примечания:

• Поймите разницу между ожидаемой стоимостью (хэш-карты обычно имеют меньшую стоимость) и стоимостью наихудшего случая (O (logn) для сбалансированного двоичного дерева, но намного выше для хеш-карты, если вставка запускает перераспределение хеш-массива ) и амортизированной стоимости (общая стоимость, разделенная на количество операций или элементов; зависит от таких вещей, как соотношение новых и существующих элементов). Вам нужно выяснить, что в вашем случае является более ограничивающим. Например, перераспределение хэш-карт может быть слишком большим, если вам нужно придерживаться очень низкого предела задержки.

• Выясните, где находится настоящее узкое место. Возможно, стоимость поиска на карте незначительна по сравнению, например, с Стоимость ввода-вывода.

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

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

Item *sentinel[65536];  // sentinel page, initialized to NULLs.
Item (*pages[65536])[65536];  // list of pages,
                              // initialized so every element points to sentinel

Тогда поиск выполняется так же просто, как:

Item *value = pages[index >> 16][index & 0xFFFF];

Когда вам нужно установить новое значение:

if (pages[index >> 16] == sentinel) {
  pages[index >> 16] = allocate_new_null_filled_page();
}
pages[index >> 16][index & 0xFFFF] = value;

• Настройте карту реализация.

  • Например. каждый hash_map хочет знать приблизительное количество элементов заранее. Это помогает избежать ненужного перераспределения хеш-таблицы и (возможно) повторного хеширования всех ключей.

  • В моем специализированном примере, приведенном выше, вы наверняка попробуете разные размеры страниц или трехуровневую версию.

  • Общая оптимизация предоставляет специализированный распределитель памяти, позволяющий избежать многократного выделения небольших объектов.