C сопоставление строк с перечислениями - сравнение строк с картой - оптимизация производительности

ProgramBox

C сопоставление строк с перечислениями — сравнение строк с картой — оптимизация производительности

Post author:admin
Запись опубликована:22 марта, 2023
Post category:Вопросы по программированию

#c #string #dictionary #enums

#c #строка #словарь #перечисления

Вопрос:

в моем коде я должен сопоставлять входные строки с перечисляемыми значениями. Это сопоставление используется довольно часто, и, согласно анализу производительности, оно является узким местом. На самом деле я сравниваю входную строку со всеми возможными строковыми значениями (if / then) и возвращаю правильное значение enum.

Для сравнения требуется около 50 различных значений.

Пример:

 enum properties_keys {
PROP_EXPANSION,
PROP_DIGITS,
PROP_INVALID,
//others...};

Сравнение-функция:

 properties_keys convertPropString(std::string input)
{
   if (input.compare("prop.expansion") == 0)
      return PROP_EXPANSION;
   if (input.compare("prop.digits") == 0)
      return PROP_DIGITS;
   //others...
   return PROP_INVALID;
}

Альтернатива: использование карты

Пример:

 properties_keys convertPropString(std::string input) {
    static std::unordered_map<std::string, properties_keys> const propStrings{
        { "prop.expansion", PROP_EXPANSION},
        { "prop.digits", PROP_DIGITS},
        //...
    };

    auto it = propStrings.find(input);
    if (it != propStrings.end()) {
        return it->second;
    }
    else { return PROP_INVALID; }
}

ВОПРОСЫ:

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

Спасибо всем экспертам.

1. std::map::find() гарантировал O (ld N), в то время как ваш if каскад имеет O (N). Даже быстрее, чем std::map::find() есть std::unordered_map::find() . Это может привести к O (1) с разумной хэш-функцией. (Я предполагаю, что std::hash(const std::stringamp;) это не должно быть так плохо, но вы можете проверить это для вашего конкретного ввода.)

2.это проблема с производительностью, потому что карта сначала «строится» при каждом вызове функции?Создание вашего std::unordered_map<std::string, properties_keys> static означает, что оно инициализируется только один раз (вероятно, при самом первом вызове функции). static переменные имеют время жизни от (не позднее) первого доступа до конца процесса — независимо от того, объявлены ли они внутри или вне областей действия функции.

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

4. просто напишите тест производительности с помощью Google-benchamar, выполните сборку в режиме выпуска и выполните измерения. Угадать, какая реализация быстрее, не так просто, как вы думаете, и довольно часто возникают неожиданные результаты.

5. @Scheff: Согласно вашему первому комментарию: поскольку я на самом деле использую неупорядоченную карту (см. Пример), это должен быть лучший вариант для использования?

Ответ №1:

Использование std::unordered_map<std::string, whatever> означает создание строки для каждого строкового литерала и узла для каждой записи карты. Это большая нагрузка на динамическую память.

Для фиксированного набора вещей я был бы склонен вручную свернуть карту в виде массива элементов в файловой области, где каждый элемент состоит из a const char* и соответствующего значения. Элементы сортируются вручную по их именам.

 struct element {
    const char *name;
    properties_keys value;
};

element element_map[] = {
    { "prop.digits", PROP_DIGITS },
    { "prop.expansion", PROP_EXPANSION },
    ...
};

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

Найдите элемент с std::binary_search соответствующим предикатом.

1. Ну, и чтобы убедиться, что нет ошибок при кодировании / сортировке таблицы «вручную», можно использовать утверждение с лямбда, которое гарантирует, что каждый элемент меньше, чем его преемник. (Я один из этих параноиков …)