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

Question

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

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

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

EDIT:

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

EDIT 2:

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

Answer 2

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