Сверхвысокая производительность хэш-карты C/С++ (таблица, словарь)

Ответ 1

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

Ответ 2

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

Отъезд LGPL'd массивы Judy. Никогда не использовал себя, но был рекламирован мне несколько раз.

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

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

Операции add/delete намного (100x) чаще, чем операция get.

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

Ответ 3

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

Ответ 4

Если у вас многопоточная программа, вы можете найти полезные хэш-таблицы в библиотеке потоковых блоков Intel. Например, tbb:: concurrent_unordered_map имеет тот же api, что и std:: unordered_map, но его основные функции являются потокобезопасными.

Также посмотрите на facebook folly library, она имеет высокую производительность одновременно хеш-таблица и список пропусков.

Ответ 5

khash очень эффективен. Существует подробный ориентир автора: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/, а также показывает, что khash бьет многие другие хэш-библиотеки.

Ответ 6

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

Если нет...

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

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

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

• хорошее старое простое число умножить algo
• http://www.azillionmonkeys.com/qed/hash.html
• http://burtleburtle.net/bob/
• http://code.google.com/p/google-sparsehash/

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

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

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

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

удача

Ответ 7

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

Ответ 8

из источников android (таким образом, лицензия Apache 2)

https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils

Посмотрите на hashmap.c, выберите include/cutils/hashmap.h, если вам не нужна безопасность потоков, вы можете удалить код мьютекса, образец реализации находится в libcutils/str_parms.c

Ответ 9

Я бы предложил uthash. Просто включите #include "uthash.h", затем добавьте UT_hash_handle в структуру и выберите одно или несколько полей в своей структуре, чтобы действовать как ключ. Слово о производительности здесь.

Ответ 10

http://incise.org/hash-table-benchmarks.html gcc имеет очень хорошую реализацию. Однако помните, что он должен соблюдать очень плохое стандартное решение:

Если происходит повторное удаление, все итераторы являются недействительными, но ссылки и указатели на отдельные элементы остаются в силе. Если фактическая переадресация происходит, никаких изменений.

http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/

Это означает, что в основном стандарт говорит, что реализация ДОЛЖНА БЫТЬ основана на связанных списках. Это предотвращает открытую адресацию, которая имеет лучшую производительность.

Я думаю, что google sparse использует открытую адресацию, хотя в этих тестах только плотная версия превосходит конкуренцию. Однако редкая версия превосходит все конкуренты в использовании памяти. (также у него нет плато, чистая прямая по числу элементов)