Как я могу увеличить производительность при поиске карты с ключом типа std::string?
Я использую std::map (Реализация VC++), и поиск немного медленен с помощью метода поиска карты.
Тип ключа std::string,
Могу ли я увеличить производительность этого std::map поиск с помощью пользовательского ключа сравнения для карты? Например, может быть std::string <сравнить не принимает во внимание простое string::size() сравнить, прежде чем сравнивать свои данные?
Любые другие идеи, чтобы ускорить сравнение?
В моей ситуации карта всегда будет содержать < 15 элементов, но она запрашивается без остановки, а производительность критична. Может быть, есть лучшая структура данных, которую я могу использовать, которая была бы быстрее?
Обновление: карта содержит пути к файлам.
Обновление 2: элементы карты часто меняются.
14 ответов
Сначала отключите все профилирование и переключатели DEBUG. Это может сильно замедлить STL.
Если это не так, частью проблемы может быть то, что ваши строки идентичны для первых 80-90% строки. Это не плохо для карты, обязательно, но для сравнения строк. Если это так, ваш поиск может занять гораздо больше времени.
Например, в этом коде find(), скорее всего, приведет к нескольким сравнениям строк, но каждый вернется после сравнения первого символа до "david", а затем будут проверены первые три символа. Таким образом, самое большее, 5 символов будут проверены за вызов.
map<string,int> names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;
map<string,int>::iterator iter = names.find("daniel");
С другой стороны, в следующем коде find(), скорее всего, проверит 135+ символов:
map<string,int> names;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/wilma"] = 1;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/fred"] = 2;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/barney"] = 3;
map<string,int>::iterator iter = names.find("/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/betty");
Это потому, что сравнения строк должны искать глубже, чтобы найти совпадение, так как начало каждой строки одинаково.
Использование size() в вашем сравнении на равенство не сильно вам поможет, так как ваш набор данных очень мал. Std::map сохраняется отсортированным, поэтому его элементы можно искать с помощью двоичного поиска. Каждый вызов должен найти менее 5 сравнений строк для промаха и в среднем 2 сравнения для попадания. Но это зависит от ваших данных. Если большинство ваших строк пути имеют разную длину, то проверка размера, как описывает Мотти, может сильно помочь.
Когда вы думаете об альтернативных алгоритмах, нужно учитывать, сколько "хитов" вы получаете. Является ли большинство ваших вызовов find() возвращением end() или попаданием? Если большая часть функции find() возвращает end() (отсутствует), то вы каждый раз просматриваете всю карту (сравнение строк 2logn).
Hash_map - хорошая идея; это должно сократить ваше время поиска примерно вдвое для хитов; больше для промахов.
Пользовательский алгоритм может быть вызван из-за природы строк пути, особенно если ваш набор данных имеет общее происхождение, как в приведенном выше коде.
Еще одна вещь, которую нужно учитывать, это то, как вы получаете строки поиска. Если вы используете их повторно, это может помочь кодировать их во что-то, что будет легче сравнивать. Если вы используете их один раз и отбрасываете их, то этот шаг кодирования, вероятно, слишком дорогой.
Однажды (давным-давно) я использовал что-то вроде дерева кодирования Хаффмана для оптимизации поиска строк. Подобное дерево поиска в двоичной строке может быть более эффективным в некоторых случаях, но это довольно дорого для небольших наборов, подобных вашему.
Наконец, посмотрите на альтернативные реализации std::map. Я слышал плохие вещи о производительности кода VC stl. В частности, библиотека DEBUG плохо проверяет вас при каждом вызове. StlPort был хорошей альтернативой, но я не пробовал его несколько лет. Я тоже всегда любил Boost.
Как даже сказал оператор использовал в set является < не ==,
Если вы не заботитесь о порядке строк в вашем set Вы можете передать set пользовательский компаратор, который работает лучше, чем обычный менее чем.
Например, если у многих ваших строк есть похожие префиксы (но они различаются по длине), вы можете отсортировать по длине строки (так как string.length постоянная скорость).
Если вы делаете это, остерегайтесь распространенной ошибки:
struct comp {
bool operator()(const std::string& lhs, const std::string& rhs)
{
if (lhs.length() < rhs.length())
return true;
return lhs < rhs;
}
};
Этот оператор не поддерживает строгий слабый порядок, у вас может быть две строки, каждая из которых меньше другой.
string a = "z";
string b = "aa";
Следуйте логике, и вы увидите, что comp(a, b) == true а также comp(b, a) == true,
Правильная реализация:
struct comp {
bool operator()(const std::string& lhs, const std::string& rhs)
{
if (lhs.length() != rhs.length())
return lhs.length() < rhs.length();
return lhs < rhs;
}
};
Во-первых, попробуйте использовать hash_map, если это возможно - вы правы, что стандартное сравнение строк сначала не проверяет размер (так как оно сравнивает лексикографически), но при написании собственного кода карты лучше избегать, Из вашего вопроса звучит так, что вам не нужно перебирать диапазоны; в этом случае на карте ничего нет hash_map.
Это также зависит от того, какие ключи у вас есть на карте. Они обычно очень длинные? Также, что означает "немного медленный"? Если вы не профилировали код, вполне возможно, что на это уходит другое время.
Обновление: Хм, узким местом в вашей программе является map::find, но карта всегда содержит менее 15 элементов. Это заставляет меня подозревать, что профиль каким-то образом вводил в заблуждение, потому что такая маленькая находка на карте не должна быть медленной. Фактически, map:: find должен быть настолько быстрым, что только издержки на профилирование могут быть больше, чем сам вызов find. Я должен спросить еще раз, вы уверены, что это действительно узкое место в вашей программе? Вы говорите, что строки - это пути, но вы не делаете никаких вызовов ОС, доступа к файловой системе, доступа к диску в этом цикле? Любой из них должен быть на несколько порядков медленнее, чем карта:: найти на маленькой карте. На самом деле любой способ получения строки должен быть медленнее, чем map::find.
Вы можете попробовать использовать отсортированный вектор ( вот один из примеров), это может оказаться быстрее (вам, конечно, придется профилировать его).
Причины думать, что это будет быстрее:
- Меньше выделения памяти и освобождения (вектор расширится до максимального используемого размера, а затем повторно использует освобожденную память).
- Двоичный поиск с произвольным доступом должен быть быстрее, чем обход дерева (особенно из-за локальности данных).
Причины думать, что это будет медленнее:
- Удаления и дополнения будут означать перемещение строк в памяти, так как
string"sswapявляется эффективным и размер набора данных невелик, это не может быть проблемой.
Компаратор std:: map не является std::equal_to, это std:: less, я не уверен, какой лучший способ замкнуть цепь <, чтобы она была быстрее встроенной.
Если всегда есть < 15 элементов, возможно, вы могли бы использовать ключ помимо std::string?
У Мотти есть хорошее решение. Тем не менее, я уверен, что для ваших < 15 элементов карта не является правильным способом, потому что ее издержки всегда будут больше, чем у простой таблицы поиска с соответствующей схемой хеширования. В вашем случае, этого может быть даже достаточно, чтобы хэшировать только по длине, и если это по-прежнему приводит к коллизиям, используйте линейный поиск по всем записям одинаковой длины.
Чтобы определить, прав ли я, необходим эталонный тест, но я совершенно уверен в его результате.
Может быть, вы могли бы перевернуть строки, прежде чем использовать их в качестве ключей на карте? Это может помочь, если первые несколько букв каждой строки идентичны.
Вы можете подумать о том, чтобы предварительно вычислить хеш для строки и сохранить его на своей карте. Это дает преимущество сравнения хешей вместо сравнения строк во время поиска по дереву std::map.
class HashedString
{
unsigned m_hash;
std::string m_string;
public:
HashedString(const std::string& str)
: m_hash(HashString(str))
, m_string(str)
{};
// ... copy constructor and etc...
unsigned GetHash() const {return m_hash;}
const std::string& GetString() const {return m_string;}
};
Это дает преимущества вычисления хэша строки один раз, при создании. После этого вы можете реализовать функцию сравнения:
struct comp
{
bool operator()(const HashedString& lhs, const HashedString& rhs)
{
if(lhs.GetHash() < rhs.GetHash()) return true;
if(lhs.GetHash() > rhs.GetHash()) return false;
return lhs.GetString() < rhs.GetString();
}
};
Поскольку хэши теперь вычисляются на HashedString Таким образом, они хранятся таким образом в std::map, и поэтому сравнение может происходить очень быстро (целочисленное сравнение) в астрономически высоком процентном соотношении времени, при использовании стандартной строки сравнение выполняется, когда хэши равны.
В зависимости от случаев использования вы можете использовать и другие методы. Например, у нас было приложение, которое должно было поддерживать более миллиона различных путей к файлам. Проблема в том, что существовали тысячи объектов, которым нужно было хранить небольшие карты этих путей к файлам.
Поскольку добавление новых путей к файлам в набор данных было нечастой операцией, при добавлении пути в систему проводился поиск основной карты. Если путь не был найден, он был добавлен, и было возвращено новое целое число (начиная с 1). Если путь уже существует, то было возвращено ранее назначенное целое число. Затем каждая карта, поддерживаемая каждым объектом, была преобразована из строковой карты в целочисленную карту. Это не только значительно улучшило производительность, но и уменьшило использование памяти за счет отсутствия большого количества дубликатов строк.
Конечно, это очень специфическая оптимизация. Но когда дело доходит до улучшения производительности, вам часто приходится искать индивидуальные решения конкретных проблем.
И я ненавижу строки:) Они не слишком медленны для сравнения, но они действительно могут испортить кэш вашего процессора на высокопроизводительном программном обеспечении.
Вот некоторые вещи, которые вы можете рассмотреть:
0) Вы уверены, что это узкое место в производительности? Понравились результаты Quantify, Cachegrind, gprof или что-то в этом роде? Потому что поиск на такой карте Smap должен быть довольно быстрым...
1) Вы можете переопределить функтор, используемый для сравнения ключей, в std::map<>, для этого есть второй параметр шаблона. Я сомневаюсь, что вы можете сделать намного лучше, чем оператор <, однако.
2) Сильно ли меняется содержимое карты? Если нет, и учитывая очень маленький размер вашей карты, возможно, использование отсортированного вектора и двоичного поиска может дать лучшие результаты (например, потому что вы можете лучше использовать локальность памяти.
3) Известны ли элементы во время компиляции? Вы можете использовать идеальную хеш-функцию для улучшения времени поиска, если это так. Поиск Gperf в Интернете.
4) Много ли у вас поисков, которые ничего не нашли? Если это так, то, возможно, сравнение с первым и последним элементами в коллекции может устранить многие несоответствия быстрее, чем полный поиск каждый раз.
Они уже были предложены, но более подробно:
5) Поскольку у вас так мало строк, возможно, вы могли бы использовать другой ключ. Например, у вас все ключи одинакового размера? Можете ли вы использовать класс, содержащий массив символов фиксированной длины? Можете ли вы преобразовать свои строки в числа или некоторую структуру данных только с числами?
Попробуйте std::tr1::unordered_map (находится в заголовке
Если ваш компилятор не поддерживает TR1, получите более новую версию. MSVC и gcc оба поддерживают TR1, и я считаю, что новейшие версии большинства других компиляторов также имеют поддержку. К сожалению, многие справочные сайты библиотеки не были обновлены, поэтому TR1 остается практически неизвестной технологией.
Я надеюсь, что C++0x не так.
РЕДАКТИРОВАТЬ: Обратите внимание, что метод хэширования по умолчанию для tr1:: unordered_map является tr1::hash, который, вероятно, должен быть специализированным для работы с UDT.
Там, где у вас длинные общие подстроки, три может быть лучшей структурой данных, чем карта или hash_map. Я сказал "может", хотя - hash_map уже пересекает ключ только один раз за поиск, поэтому должен быть довольно быстрым. Я не буду обсуждать это дальше, так как другие уже имеют.
Вы также можете рассмотреть Splay Tree, если некоторые ключи ищутся чаще, чем другие, но, конечно, это делает поиск в худшем случае хуже, чем сбалансированное дерево, и поиски являются мутационными операциями, которые могут иметь значение для вас, если вы используете например, замок читателя-писателя.
Если вы заботитесь о производительности поиска больше, чем о модификациях, вы можете добиться большего успеха с деревом AVL, чем с красно-черным, что, как мне кажется, является тем, что реализации STL обычно используют для отображения. Дерево AVL обычно лучше сбалансировано и поэтому в среднем требует меньше сравнений на поиск, но разница незначительна.
Поиск реализации, которой вы довольны, может быть проблемой. Поиск на главной странице Boost показывает, что у них есть Splay и AVL-дерево, но не три.
Вы упомянули в комментарии, что у вас никогда нет поиска, который ничего не может найти. Таким образом, теоретически вы можете пропустить окончательное сравнение, которое в дереве из 15 < 2^4 элементов может дать вам что-то вроде ускорения на 20-25%, не делая ничего другого. На самом деле, может быть, даже больше, так как одинаковые строки медленнее сравнивать. Стоит ли писать свой собственный контейнер только для этой оптимизации - это другой вопрос.
Вы могли бы также рассмотреть местность ссылки - я не знаю, можно ли избежать случайного пропуска страницы, выделяя ключи и узлы из небольшой кучи. Если вам нужно всего лишь около 15 записей одновременно, тогда, предполагая ограничение имени файла ниже 256 байт, вы можете убедиться, что все, к чему обращаются во время поиска, помещается на одной странице 4 КБ (кроме разыскиваемого ключа, конечно). Может случиться так, что сравнение строк незначительно по сравнению с парой загрузок страниц. Однако, если это ваше узкое место, должно происходить огромное количество поисков, поэтому я предполагаю, что все достаточно близко к процессору. Стоит проверить, может быть.
Еще одна мысль: если вы используете пессимистическую блокировку в структуре, где много споров (вы сказали в комментарии, что программа многопоточная), то независимо от того, что говорит вам профилировщик (в каком коде тратятся циклы ЦП), это может стоить вам больше, чем вы думаете, эффективно ограничивая вас до 1 ядра. Попробуйте блокировку читатель-писатель?
hash_map не является стандартным, попробуйте использовать unordered_map доступно в tr1 (которое доступно в boost, если в вашей цепочке инструментов его еще нет).
Для небольшого количества строк вы могли бы лучше использовать vector, как map обычно реализуется в виде дерева.
Почему бы вам не использовать вместо этого хеш-таблицу? Boost::unordered_map может сделать. Или вы можете развернуть свое собственное решение и сохранить crc строки вместо самой строки. Или, что еще лучше, поместите #defines для строк и используйте их для поиска, например:
#define "STRING_1" STRING_1