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

Question

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

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

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

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

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

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

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

Answer 1

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

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

Конечно, это очень специфическая оптимизация. Но когда дело доходит до улучшения производительности, вам часто приходится искать индивидуальные решения конкретных проблем.

И я ненавижу строки :) Они не слишком медленны для сравнения, но они действительно могут испортить кэш вашего процессора в высокопроизводительном ПО.

Answer 2

Вот некоторые вещи, которые вы можете рассмотреть:

0) Вы уверены, что это узкое место производительности? Понравились результаты Quantify, Cachegrind, gprof или что-то в этом роде? Потому что поиск на такой карте Smap должен быть довольно быстрым ...

1) Вы можете переопределить функтор, используемый для сравнения ключей, в std :: map <>, для этого есть второй параметр шаблона. Я сомневаюсь, что вы можете сделать намного лучше, чем оператор <, однако. </p>

2) Значительно ли меняется содержимое карты? Если нет, и учитывая очень маленький размер вашей карты, возможно, использование отсортированного вектора и двоичного поиска может дать лучшие результаты (например, потому что вы можете лучше использовать локальность памяти.

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

4) Много ли у вас поисков, которые ничего не нашли? Если это так, то, возможно, сравнение с первым и последним элементами в коллекции может устранить многие несоответствия быстрее, чем полный поиск каждый раз.

Они уже были предложены, но более подробно:

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

Answer 3

Почему бы вам не использовать вместо этого хеш-таблицу? Boost :: unordered_map может сделать. Или вы можете развернуть свое собственное решение и сохранить crc строки вместо самой строки. Или, еще лучше, поместите #defines для строк и используйте их для поиска, например,

#define "STRING_1" STRING_1

Answer 4

hash_map не является стандартным, попробуйте использовать unordered_map, доступный в tr1 (который доступен в boost, если в вашей цепочке инструментов его еще нет).

Для небольшого числа строк лучше использовать vector, так как map обычно реализуется в виде дерева.