Использование буста неупорядоченной карты

Question

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

1. Каждое сгенерированное значение идентифицируется с использованием 25 уникальных ключей.
2. Я использую boost :: hash_combine , чтобы сгенерировать seed для хеш-таблицы, используя эти 25 ключей.

3. Я храню значения в хеш-таблице, объявленной как

   boost::unordered_map<Key_Object, Data_Object, HashFunction> hashState;

4. Я провел профилирование времени по своему алгоритму и обнаружил, что почти 95% времени выполнения тратится на извлечение / вставку данных в хеш-таблицу.

5. Это были данные моей хеш-таблицы

   hashState.size() 1880

   hashState.load_factor() 0.610588

   hashState.bucket_count() 3079

   hashState.max_size() 805306456

   hashState.max_load_factor() 1

   hashState.max_bucket_count() 805306457

У меня есть следующие два вопроса

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

2. C ++ STL имеет hash_multimap, который также соответствует моим требованиям. Как повысить библиотеки unordered_map по сравнению с hash_multimap с точки зрения производительность вставки / извлечения .

Answer 1

Вы уверены, что используемая хеш-функция не является узким местом? Какой процент времени занимает хеш-функция? Можете ли вы сделать тот же тест и заменить вставку / извлечение простым вызовом хеша.

Answer 2

Если ваша хеш-функция не является причиной, лучшее, что вы можете сделать, это, вероятно, использовать другую реализацию карты. Поскольку ваши ключи довольно велики, лучшим вариантом может быть использование unordered_map из Boost.Intrusive library . В качестве альтернативы вы можете попробовать закрытое хеширование: Google SparseHash или MCT , хотя профилирование, безусловно, необходимо, потому что закрытое хеширование рекомендуется, когда элементы достаточно малы. (SparseHash более проверен и хорошо протестирован, но MCT не нуждается в этих set_empty() / set_deleted() методах).

EDIT:

Я только что заметил, что в упомянутой мной библиотеке Boost нет навязчивой карты, только set и multiset. Тем не менее, вы можете попробовать две закрытые библиотеки хеширования.

РЕДАКТИРОВАТЬ 2:

STL hash_map не является стандартным, это, вероятно, некоторое расширение и не переносимо во всех компиляторах.