Как я могу увеличить производительность при поиске карты с ключом типа std :: string?

Question

Я использую std::map (реализация VC ++), и он немного медленен для поиска через метод поиска карты.

Тип ключа std::string.

Могу ли я повысить производительность этого поиска std::map с помощью пользовательского переопределения сравнения ключей для карты? Например, может быть, std::string <сравнение не учитывает простое <code>string::size() сравнение перед сравнением его данных?

Какие-нибудь другие идеи, чтобы ускорить сравнение?

В моей ситуации карта всегда будет содержать <15 элементов, но она запрашивается без остановки, а производительность критична. Может быть, есть лучшая структура данных, которую я могу использовать, которая была бы быстрее? </p>

Обновление: карта содержит пути к файлам.

Обновление 2: элементы карты часто меняются.

Answer 1

Сначала отключите все профилирование и переключатели 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 была хорошей альтернативой, но я не пробовал ее несколько лет. Я всегда любил Повышение тоже.

Answer 2

Как Даже сказал, что оператор, используемый в 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;
    }
};

Answer 3

Во-первых, попробуйте использовать hash_map, если это возможно - вы правы, что стандартное сравнение строк сначала не проверяет размер (так как оно сравнивает лексикографически), но вам нужно написать собственный код карты лучше избегать Из вашего вопроса звучит так, что вам не нужно перебирать диапазоны; в этом случае на карте ничего нет hash_map.

Это также зависит от того, какие ключи у вас есть на карте. Они обычно очень длинные? И что значит "немного медленный"? Если вы не профилировали код, вполне возможно, что на это уходит другое время.

Обновление: Хм, узким местом в вашей программе является карта :: найти, но карта всегда содержит менее 15 элементов. Это заставляет меня подозревать, что профиль каким-то образом вводил в заблуждение, потому что такая маленькая находка на карте не должна быть медленной. Фактически, map :: find должен быть настолько быстрым, что только издержки на профилирование могут быть больше, чем сам вызов find. Я должен спросить еще раз, вы уверены, что это действительно узкое место в вашей программе? Вы говорите, что строки - это пути, но вы не делаете никаких вызовов ОС, доступа к файловой системе, доступа к диску в этом цикле? Любой из них должен быть на несколько порядков медленнее, чем карта :: найти на маленькой карте. На самом деле любой способ получить строку должен быть медленнее, чем map :: find.

Answer 4

Вы можете попробовать использовать отсортированный вектор (, вот один пример ), это может оказаться быстрее (вам придется профилировать его, чтобы убедиться, конечно ).

Причины думать, что это будет быстрее:

1. Меньше выделения памяти и освобождения (вектор расширится до максимального используемого размера, а затем повторно использует освобожденную память).
2. Двоичный поиск с произвольным доступом должен быть быстрее, чем обход дерева (особенно из-за локальности данных).

Причины думать, что это будет медленнее:

1. Удаления и добавления будут означать перемещение строк в памяти, поскольку swap *1019* эффективен, а размер набора данных невелик, это не может быть проблемой.

Answer 5

У Мотти хорошее решение. Тем не менее, я уверен, что для ваших <15 элементов карта не является правильным способом, потому что ее издержки всегда будут больше, чем у простой таблицы поиска с соответствующей схемой хеширования. В вашем случае, этого может быть даже достаточно, чтобы хэшировать только по длине, и если это все еще приводит к коллизиям, используйте линейный поиск по всем записям одинаковой длины. </p>

Чтобы определить, прав ли я, необходим эталонный тест, но я вполне уверен в его результате.

Answer 6

std :: map компаратор не std :: equal_to это std :: less, я не уверен, что лучший способ замкнуть

Если всегда есть <15 элементов, возможно, вы могли бы использовать ключ помимо std :: string? </p>

Answer 7

Может быть, вы могли бы обратить строки, прежде чем использовать их в качестве ключей на карте? Это может помочь, если первые несколько букв каждой строки идентичны.

Answer 8

Вы можете подумать о том, чтобы предварительно вычислить хеш для строки и сохранить его на своей карте. Это дает преимущество сравнения хешей вместо сравнения строк во время поиска по дереву 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, и поэтому сравнение может происходить очень быстро (целочисленное сравнение) в астрономически высоком проценте времени, отступая по стандартной строке сравнивает, когда хэши равны.

Answer 9

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

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

Если вы заботитесь о производительности поиска больше, чем о модификациях, вы могли бы добиться большего успеха с деревом AVL, чем с красно-черным, что, как я думаю , - это то, что реализации STL обычно используют для отображения. Дерево AVL обычно лучше сбалансировано и поэтому в среднем требует меньше сравнений на поиск, но разница незначительна.

Поиск реализации, которой вы довольны, может быть проблемой. Поиск на главной странице Boost позволяет предположить, что у них есть Splay и AVL-дерево, но не три.

Вы упомянули в комментарии, что у вас никогда нет поиска, который ничего не может найти. Таким образом, теоретически можно пропустить окончательное сравнение, которое в дереве из 15 <2 ^ 4 элементов может дать вам что-то вроде ускорения на 20-25%, не делая ничего другого. На самом деле, может быть, даже больше, так как равные строки медленнее сравнивать. Стоит ли писать свой собственный контейнер только для этой оптимизации - это другой вопрос. </p>

Вы могли бы также рассмотреть местность ссылок - я не знаю, можно ли избежать случайного промаха страницы, выделяя ключи и узлы из небольшой кучи. Если вам нужно всего лишь около 15 записей одновременно, то, предполагая ограничение имени файла ниже 256 байт, вы можете убедиться, что все, к чему обращались во время поиска, помещается на одной странице 4 КБ (кроме разыскиваемого ключа, конечно). Может случиться так, что сравнение строк незначительно по сравнению с парой загрузок страниц. Однако, если это ваше узкое место, должно происходить огромное количество поисков, поэтому я предполагаю, что все достаточно близко к процессору. Стоит проверить, может быть.

Еще одна мысль: если вы используете пессимистическую блокировку для структуры, в которой много споров (вы сказали в комментарии, что программа многопоточная), то независимо от того, что вам говорит профилировщик (какой код циклы ЦП потрачено в), это может стоить вам больше, чем вы думаете, эффективно ограничивая вас до 1 ядра. Попробуйте блокировку чтения-записи?

Answer 10

Попробуйте std :: tr1 :: unordered_map (находится в заголовке ). Это хэш-карта, и, хотя она не поддерживает отсортированный порядок элементов, она, вероятно, будет намного быстрее, чем обычная карта.

Если ваш компилятор не поддерживает TR1, получите более новую версию. MSVC и gcc оба поддерживают TR1, и я считаю, что новейшие версии большинства других компиляторов также имеют поддержку. К сожалению, многие справочные сайты библиотеки не были обновлены, поэтому TR1 остается практически неизвестной технологией.

Я надеюсь, что C ++ 0x - не то же самое.

РЕДАКТИРОВАТЬ: Обратите внимание, что метод хэширования по умолчанию для tr1 :: unordered_map это tr1 :: hash, который должен быть специализирован для работы с UDT, вероятно.