Супер высокопроизводительный C/C++ хеширует карту (таблица, словарь) [закрытый]

Я бы порекомендовал вам попробовать Google SparseHash (или версию C11 Google SparseHash-c11 ) и посмотреть, подходит ли он вашим потребностям. У них есть реализация с эффективным использованием памяти, а также оптимизированная по скорости. Я провел тест давно, это была лучшая реализация хеш-таблицы, доступная с точки зрения скорости (однако с недостатками).

В каких библиотеках на C или C++ есть структура данных, подходящая для этого случая использования? Или, как бы вы порекомендовали создать свою собственную? Спасибо!

Посмотрите LGPL'd Judy arrays. Сам никогда не использовал, но мне несколько раз рекламировали.

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

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

Операции add/delete выполняются намного (в 100 раз) чаще, чем операция get.

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

Сначала проверьте, подходят ли существующие решения, такие как libmemcache, вашим потребностям.

Если нет ...

Хеш-карты кажутся однозначным ответом на ваши требования. Он обеспечивает поиск o (1) на основе ключей. В наши дни большинство библиотек STL предоставляют какой-то хэш. Так что используйте тот, который предоставляется вашей платформой.

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

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

1. старый добрый алгоритм умножения простых чисел
2. http://www.azillionmonkeys.com/qed/hash.html
3. http://burtleburtle.net/bob/
4. http://code.google.com/p/google-sparsehash/

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

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

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

Я считаю, что больше, чем алгоритм хеширования, это может быть постоянное добавление / удаление памяти (можно ли этого избежать?) И профиль использования кэша процессора, которые могут быть более важными для производительности вашего приложения

удачи

Просто используйте boost::unordered_map (или tr1 и т.д.) по умолчанию. Затем профилируйте свой код и посмотрите, является ли этот код узким местом. Только после этого я бы предложил точно проанализировать ваши требования, чтобы найти более быструю замену.

Попробуйте хеш-таблицы из Разные шаблоны контейнеров . Его closed_hash_map примерно такая же скорость, как и Google density_hash_map , но его проще использовать (нет ограничений на содержащиеся значения), а также есть некоторые другие преимущества.