Как я могу увеличить производительность при поиске карты с ключом типа std :: string?
https://stackoverflow.com/questions/256038
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я использую std::map (реализация VC ++), и поиск немного медленнее с помощью метода поиска карты.
Тип ключа std::string.
Могу ли я повысить производительность этого поиска string::size() с помощью переопределения сравнения пользовательских ключей для карты? Например, может быть, <=> & Lt; сравнение не учитывает простое сравнение <=> перед сравнением его данных?
Есть еще идеи по ускорению сравнения?
В моей ситуации карта всегда будет содержать < 15 элементов, но он запрашивается без остановок, а производительность имеет решающее значение. Может быть, есть лучшая структура данных, которую я могу использовать, которая была бы быстрее?
Обновление: карта содержит пути к файлам.
Update2: элементы карты часто меняются.
Решение
Сначала отключите все профилирование и переключатели 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 сравнениям для попадания. Но это зависит от ваших данных. Если большинство ваших строк пути имеют разную длину, то проверка размера, как описывает Мотти, может помочь.
При рассмотрении альтернативных алгоритмов необходимо учитывать, сколько " hit " ты получаешь. Является ли большинство ваших вызовов find () возвращением end () или попаданием? Если большинство из ваших find () возвращают end () (пропускает), то вы каждый раз просматриваете всю карту (сравнение строк 2logn).
Hash_map - хорошая идея; это должно сократить ваше время поиска примерно вдвое для хитов; больше для промахов.
Пользовательский алгоритм может быть вызван из-за природы строк пути, особенно если ваш набор данных имеет общее происхождение, как в приведенном выше коде.
Еще одна вещь, которую стоит рассмотреть, это то, как вы получаете строки поиска. Если вы используете их повторно, это может помочь кодировать их во что-то, что будет легче сравнивать. Если вы используете их один раз и отбрасываете их, то этот шаг кодирования, вероятно, слишком дорогой.
Однажды (давным-давно) я использовал что-то вроде дерева кодирования Хаффмана для оптимизации поиска строк. Подобное дерево поиска в двоичной строке может быть более эффективным в некоторых случаях, но довольно дорого для небольших наборов, подобных вашему.
Наконец, посмотрите на альтернативные реализации std :: map. Я слышал плохие вещи о производительности кода VC stl. В частности, библиотека DEBUG плохо проверяет вас при каждом вызове. StlPort была хорошей альтернативой, но я не пробовал ее несколько лет. Я всегда любил Boost .
Другие советы
As Даже сказал, что оператор, используемый в set, < не ==.
Если вам не важен порядок строк в вашем string.length, вы можете передать comp(a, b) == true пользовательский компаратор, который работает лучше, чем обычный less-than .
Например, если у многих ваших строк одинаковые префиксы (но они различаются по длине), вы можете отсортировать их по длине строки (поскольку comp(b, a) == true - это постоянная скорость).
Если вы это сделаете, остерегайтесь распространенной ошибки:
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";
Следуйте логике, и вы увидите, что <=> и <=>.
Правильная реализация:
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 swap эффективен, а размер набора данных невелик, это может не быть проблемой. std :: map компаратор не std :: equal_to это std :: less, я не уверен, что лучший способ замкнуть накоротко < сравните, чтобы он был быстрее встроенного.
Если всегда есть < 15 элементов, возможно, вы могли бы использовать ключ помимо std :: string?
У Motti есть хорошее решение. Тем не менее, я уверен, что для вашего & Lt; 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, и поэтому сравнение может происходить очень быстро (целочисленное сравнение) в астрономически высоком проценте времени, откатываясь по стандартной строке сравнивает, когда хэши равны.
Может быть, вы могли бы перевернуть строки, прежде чем использовать их в качестве ключей на карте? Это может помочь, если первые несколько букв каждой строки идентичны.
Вот несколько вещей, которые вы можете рассмотреть:
0) Вы уверены, что это узкое место в производительности? Понравились результаты Quantify, Cachegrind, gprof или что-то в этом роде? Потому что поиск на такой карте Smap должен быть довольно быстрым ...
1) Вы можете переопределить функтор, используемый для сравнения ключей, в std :: map < > есть второй параметр шаблона, чтобы сделать это. Я сомневаюсь, что вы можете сделать намного лучше, чем оператор & Lt ;, однако.
2) Содержимое карты сильно меняется? Если нет, и учитывая очень маленький размер вашей карты, возможно, использование отсортированного вектора и двоичного поиска может дать лучшие результаты (например, потому что вы можете лучше использовать локальность памяти.
3) Известны ли элементы во время компиляции? Вы можете использовать идеальную хеш-функцию для улучшения времени поиска, если это так. Найдите gperf в Интернете.
4) Много ли у вас поисков, которые ничего не нашли? Если это так, то, возможно, сравнение с первым и последним элементами в коллекции может устранить многие несоответствия быстрее, чем полный поиск каждый раз.
Они уже были предложены, но более подробно:
5) Поскольку у вас так мало строк, возможно, вы могли бы использовать другой ключ. Например, у вас все ключи одинакового размера? Можете ли вы использовать класс, содержащий массив символов фиксированной длины? Можете ли вы преобразовать свои строки в числа или некоторую структуру данных только с числами?
В зависимости от случаев использования вы можете использовать и другие методы. Например, у нас было приложение, которое должно было поддерживать более миллиона различных путей к файлам. Проблема в том, что существуют тысячи объектов, которым нужно хранить небольшие карты этих путей к файлам.
Поскольку добавление новых путей к файлам в набор данных было нечастой операцией, при добавлении пути в систему проводился поиск основной карты. Если путь не был найден, он был добавлен, и было возвращено новое целое число (начиная с 1). Если путь уже существует, то было возвращено ранее назначенное целое число. Затем каждая карта, поддерживаемая каждым объектом, была преобразована из строковой карты в целочисленную карту. Это не только значительно улучшило производительность, но и уменьшило использование памяти за счет отсутствия большого количества дубликатов строк.
Конечно, это очень специфическая оптимизация. Но когда дело доходит до улучшения производительности, вам часто приходится искать индивидуальные решения конкретных проблем.
И я ненавижу строки :) Они не слишком медленны для сравнения, но они действительно могут испортить кэш вашего процессора в высокопроизводительном программном обеспечении.
Попробуйте std :: tr1 :: unordered_map (находится в заголовке < tr1 / unordered_map >). Это хэш-карта, и, хотя она не поддерживает отсортированный порядок элементов, она, вероятно, будет намного быстрее, чем обычная карта.
Если ваш компилятор не поддерживает TR1, получите более новую версию. MSVC и gcc оба поддерживают TR1, и я считаю, что новейшие версии большинства других компиляторов также имеют поддержку. К сожалению, многие справочные сайты библиотеки не были обновлены, поэтому TR1 остается практически неизвестной технологией.
Я надеюсь, что C ++ 0x - это не так.
РЕДАКТИРОВАТЬ: обратите внимание, что метод хэширования по умолчанию для tr1 :: unordered_map - это tr1 :: hash, который, вероятно, должен быть специализирован для работы с UDT.
Если у вас длинные общие подстроки, три может быть лучшей структурой данных, чем карта или hash_map. Я сказал & Quot; Мог бы & Quot ;, хотя - hash_map уже перебирает ключ только один раз за поиск, поэтому должен быть довольно быстрым. Я не буду обсуждать это дальше, так как другие уже имеют.
Вы также можете рассмотреть сплайновое дерево, если некоторые ключи ищутся чаще, чем другие, но, конечно, это делает поиск в худшем случае хуже сбалансированного дерева, и поиск - это операции с мутацией, которые могут иметь значение для вас, если вы используете например замок читатель-писатель.
Если вы заботитесь о производительности поиска больше, чем о модификациях, вы можете добиться большего успеха с деревом AVL, чем с красно-черным, что, как я думаю, , является тем, что реализации STL обычно используют для отображения. Дерево AVL обычно лучше сбалансировано и поэтому в среднем требует меньше сравнений на поиск, но разница незначительна.
Поиск реализации, которой вы довольны, может быть проблемой. Поиск на главной странице Boost показывает, что у них есть Splay и AVL-дерево, но не три.
Вы упомянули в комментарии, что у вас никогда нет поиска, который ничего не может найти. Таким образом, вы можете теоретически пропустить окончательное сравнение, которое в дереве 15 & Lt; 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
