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

Исправьте меня, я ошибаюсь, но std:: map - упорядоченная карта, поэтому каждый раз, когда я вставляю значение, карта использует алгоритм для сортировки своих элементов внутри, что занимает некоторое время.

Мое приложение получает информацию о некоторых элементах на постоянном интервале.

Это приложение сохраняет карту, которая определяется следующим образом:

::std::map<DWORD, myItem*>

Сначала все элементы считаются "новыми" для приложения. Объект "Item" выделяется и добавляется на эту карту, связывая его идентификатор и указатель на него.

Когда это не "новый" элемент (просто обновление этого объекта), мое приложение должно найти объект на карте, используя данный идентификатор и обновить.

В большинстве случаев я получаю обновления.

Мой вопрос:
Есть ли какая-либо более быстрая реализация карты или я должен продолжать использовать ее?
Я лучше использую unordered_map?

Ответ 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.