Действительно ли я должен кэшировать хэш-код строки STL, используемой в качестве ключа хеша?
У меня есть выполнение некоторого анализа производительности программного обеспечения, которое я разрабатываю, и я нашел что поиски на глобальном словаре взятий URL приблизительно 10% времени фазы "загрузки" приложения. Словарь реализован как станд. STL C++:: карта, которая имеет O (LG n) поиски. Я собираюсь переместить его в hash_map, который примерно зафиксировал поиски времени. stl строковый класс не имеет свойства хэш-кода, и он, конечно, не кэширует хэш-код. Это означает, что каждый поиск требует регенерации хэш-кода.
Я скептически настроен, что кэширование хэш-кода стоит усилия. Это означало бы изменять много строк кода для использования нового строкового класса с кэшируемым свойством хэш-кода. Учитывая, что текущая реализация действительно регистрирует (n) полные сравнения строк в каждый поиск, я думаю, уменьшая его до в основном одного строкового обхода (хеш-функцией) на поиск, большая победа.
У кого-либо есть опыт с кэширующимися строковыми хэш-кодами? Это когда-либо оказывалось стоящим усилия?
4 ответа
У меня нет опыта кэширования хэш-кодов, но недавно я выполнил некоторую работу по преобразованию std::map в std::tr1::unorddered_map. На ум приходят две мысли. Во-первых, попробуйте сначала профилировать это относительно простое изменение, так как оно иногда ухудшает ситуацию, в зависимости от того, что делает ваш код. Это может само по себе дать достаточное ускорение перед дальнейшей оптимизацией. Во-вторых, что говорит ваш профайлер о других 90% времени инициализации? Даже если бы вы оптимизировали глобальный словарь до 0 раз, вы в лучшем случае улучшите производительность на 10%.
Когда вы сравниваете хэш-карту с картой, попробуйте также Trie или связанную структуру данных (все, что вы можете найти с полки):
К сожалению, вы можете потратить много времени на беспокойство насчет кеш-дружественности. В этом отношении Trie похоже на дерево, которое у вас уже есть, и хеш-карта, вероятно, будет вести себя лучше, чем наивно выделенное дерево.
Кроме того, меня немного смущает этот вопрос. Если вы ищете одну и ту же строку объект несколько раз, так что кеширование его хеш-значения имеет смысл, не следует ли вам просто кэшировать результат поиска? Вся суть хеш-таблицы в том, что разные объекты, которые имеют хеш-значение, равное одному и тому же значению. Если вы не вычисляете один и тот же хэш несколько раз из разных строк, содержащих одни и те же символы, то ваша хеш-таблица, вероятно, не выполняет свою работу.
Если вы имеете в виду кеширование значений ключей, уже находящихся в хеш-таблице, это зависит от хеш-таблицы.
Одно предупреждение.
Несмотря на то, что карта хэшей может иметь фиксированное время поиска, она также может иметь O(N) поиск. Хотя это и не обычный случай, но случается.
Таким образом, в то время как Вы всегда должны платить за время O(log N) на карте, Вы также гарантируете, что оно не будет хуже.
Вам, конечно, нужно будет профилировать чтобы проверить свои результаты. Перейдите на хеш-карту, а затем посмотрите, где вы проводите большую часть времени. Если вы не хешируете ключи вправо и влево, я сомневаюсь, что большая часть вашего времени будет потрачена на это. Хеширование задумано как быстрая операция, иначе хеш-карта не будет иметь преимуществ перед заказанным контейнером.
Компилятор сам узнает, не была ли строка изменена, и, вероятно, сможет кэшировать результат для вас (в той же области). Тем не менее, вы не хотите наследовать от std :: string ; Классы STL не были созданы для этого.
Вместо этого создайте std :: pair и передайте ее:
std :: pair
Затем вам нужно будет перегрузите функцию (здесь используется Boost, а не TR1; я не знаю, насколько они похожи) hash_value для вашего типа в том же пространстве имен, в котором определена пара:
size_t hash_value(const string_hash_pair& pPair)
{
return pPair.second; // don't actually hash
}
И все. Обратите внимание, что в паре неизменяемы как строка , так и size_t . Это потому, что если строка изменяется, ваш хеш неверен. Поэтому мы делаем его const , а также можем сделать хэш const .
Вам понадобится вспомогательная функция:
string_hash_pair make_string_hash(const std::string& pStr)
{
return std::make_pair(pStr, boost::hash_value(pStr));
}
Теперь, если вы собираетесь использовать строку для поиска, просто сделайте из нее пару, и вы получите хеширование с постоянным временем.
Тем не менее, я действительно сомневаюсь, что нужно так много работать. Функции хеширования обычно тривиальны. Кроме того, не создавайте свой собственный . Используйте уже существующий проверенный хеш-код; сделать дерьмовый хеш довольно легко.