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

Ответ 1

Мне лучше использовать unordered_map?

Возможно.

std:map обеспечивает согласованную производительность в O (log n), потому что она должна быть реализована как сбалансированное дерево. Но std:unordered_map будет реализовываться как хеш-таблица, которая может дать вам производительность O (1) (хорошая хеш-функция и распределение ключей по хэш-кодам), но это может быть O (n) (все в одном хэш-ведре и переходит к список). Обычно можно ожидать чего-то между этими крайностями.

Таким образом, вы можете иметь разумную производительность (O (log n)) все время, или вам нужно обеспечить, чтобы все линии достигли хорошей производительности с хешем.

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

Ответ 2

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

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

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

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

• Узнайте, где настоящее узкое место. Возможно, что стоимость поиска на карте незначительна по сравнению с, например, IO.

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

В вашем примере (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 любит заранее знать приблизительное количество элементов. Это помогает избежать ненужного перераспределения хэш-таблицы и (возможно) переименования всех ключей.

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

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

Ответ 3

Всякий раз, когда вы вставляете или удаляете элемент, выделение/освобождение памяти стоит дорого. Вместо этого вы можете использовать такой распределитель: https://github.com/moya-lang/Allocator, который ускоряет std :: map в два раза, как говорит автор, но я нашел его еще быстрее, особенно для других контейнеров STL.