Мне нужно сопоставить примитивные ключи (int, возможно, long) для структурирования значений в высокопроизводительной структуре данных хэш-карты.
В моей программе будет несколько сотен таких карт, и каждая карта обычно содержит не более нескольких тысяч записей. Однако карты будут постоянно «обновляться» или «вспениваться»; представьте обработки миллионы addи deleteсообщений в секунду.
Какие библиотеки на C или C ++ имеют структуру данных, подходящую для этого варианта использования? Или как бы вы порекомендовали создать свой собственный? Благодаря!
@roe:Операции добавления / удаления выполняются намного (в 100 раз) чаще, чем операция получения.Ответы:
Я бы порекомендовал вам попробовать Google SparseHash (или версию C11 Google SparseHash-c11 ) и посмотреть, подходит ли он вашим потребностям. У них есть реализация с эффективным использованием памяти, а также оптимизированная по скорости. Давным-давно я провел тест, это была лучшая реализация хеш-таблицы, доступная с точки зрения скорости (однако с недостатками).
источник
Обратите внимание на массивы Джуди от LGPL . Сам никогда не использовал, но несколько раз мне рекламировали.
Вы также можете попробовать протестировать контейнеры STL (std :: hash_map и т. Д.). В зависимости от платформы / реализации и настройки исходного кода (предварительное выделение максимально возможного объема динамической памяти стоит дорого) они могут быть достаточно производительными.
Кроме того, если производительность окончательного решения превышает стоимость решения, вы можете попробовать заказать систему с достаточным объемом оперативной памяти, чтобы поместить все в простые массивы. Производительность доступа по индексу не имеет себе равных.
Это намекает на то, что вы можете в первую очередь сосредоточиться на улучшении алгоритмов. Если данные только записываются, а не читаются, тогда зачем их вообще писать?
источник
Просто используйте
boost::unordered_map(илиtr1т. Д.) По умолчанию. Затем профилируйте свой код и посмотрите, является ли этот код узким местом. Только после этого я предлагаю тщательно проанализировать ваши требования, чтобы найти более быструю замену.источник
std::unordered_mapзанимает 90 +% всего моего времени выполнения, хотя я использую карты только для относительно небольшой части обработки.Если у вас есть многопоточная программа, вы можете найти несколько полезных хеш-таблиц в библиотеке строительных блоков Intel thread . Например, tbb :: concurrent_unordered_map имеет тот же API, что и std :: unordered_map, но его основные функции являются потокобезопасными.
Также взгляните на библиотеку глупостей facebook , она имеет высокопроизводительную параллельную хеш-таблицу и список пропусков .
источник
хаш очень эффективен. Существует подробный тест автора: https://attractivechaos.wordpress.com/2008/10/07/another-look-at-my-old-benchmark/, и он также показывает, что хэш превосходит многие другие хеш-библиотеки.
источник
из источников Android (таким образом, под лицензией Apache 2)
https://github.com/CyanogenMod/android_system_core/tree/ics/libcutils
посмотрите hashmap.c, выберите include / cutils / hashmap.h, если вам не нужна потокобезопасность, вы можете удалить код мьютекса, образец реализации находится в libcutils / str_parms.c
источник
Сначала проверьте, подходят ли существующие решения, такие как libmemcache, вашим потребностям.
Если не ...
Хеш-карты кажутся однозначным ответом на ваши требования. Он обеспечивает поиск o (1) на основе ключей. В наши дни большинство библиотек STL предоставляют какой-то хэш. Так что используйте тот, который предоставляется вашей платформой.
Как только эта часть будет завершена, вы должны протестировать решение, чтобы убедиться, что алгоритм хеширования по умолчанию достаточно хорош для ваших нужд.
Если это не так, вам следует изучить несколько хороших алгоритмов быстрого хеширования, которые можно найти в сети.
Если этого недостаточно, вы можете самостоятельно скатить модуль хеширования, который устранит проблему, которую вы видели с тестированными контейнерами STL, и одним из алгоритмов хеширования, описанных выше. Обязательно где-нибудь выложите результаты.
О, и это интересно, что у вас есть несколько карт ... возможно, вы можете упростить, используя свой ключ в виде 64-битного числа с старшими битами, используемыми для различения, какой карте он принадлежит, и добавления всех пар значений ключа в один гигантский хеш. Я видел хэши, содержащие около сотни тысяч символов, которые отлично работали с базовым алгоритмом хеширования простых чисел.
Вы можете проверить, как это решение работает по сравнению с сотнями карт ... я думаю, что это могло бы быть лучше с точки зрения профилирования памяти ... пожалуйста, опубликуйте результаты где-нибудь, если вам удастся выполнить это упражнение
Я считаю, что больше, чем алгоритм хеширования, это может быть постоянное добавление / удаление памяти (можно ли этого избежать?) И профиль использования кеша процессора, который может быть более важным для производительности вашего приложения.
удачи
источник
Попробуйте хэш-таблицы из разных шаблонов контейнеров . Его
closed_hash_mapскорость примерно такая же, как у Googledense_hash_map, но его проще использовать (нет ограничений на содержащиеся значения), а также есть некоторые другие преимущества.источник
Я бы предложил утхаш . Просто включите,
#include "uthash.h"затем добавьтеUT_hash_handleв структуру и выберите одно или несколько полей в своей структуре, которые будут действовать в качестве ключа. Слово о производительности здесь .источник
http://incise.org/hash-table-benchmarks.html gcc имеет очень хорошую реализацию. Однако учтите, что он должен учитывать очень плохое стандартное решение:
http://www.cplusplus.com/reference/unordered_map/unordered_map/rehash/
Это означает, что стандарт говорит, что реализация ДОЛЖНА БЫТЬ основана на связанных списках. Это предотвращает открытую адресацию, которая имеет лучшую производительность.
Я думаю, что Google Sparse использует открытую адресацию, хотя в этих тестах только плотная версия превосходит конкурентов. Однако разреженная версия превосходит всех конкурентов по использованию памяти. (также у него нет плато, чистая прямая линия по количеству элементов)
источник