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

Ответ 1

Подобно решению Dietmar, но с немного меньшим количеством редактирования: вы можете обернуть строку (один раз) вместо каждого литерала

#include <string>
#include <cstring>
struct FastLiteralWrapper {
    std::string const &s;

    explicit FastLiteralWrapper(std::string const &s_) : s(s_) {}

    template <std::size_t ArrayLength>
    bool operator== (char const (&other)[ArrayLength]) {
        std::size_t const StringLength = ArrayLength - 1;
        return StringLength == s.size()
            && std::memcmp(s.data(), other, StringLength) == 0;
    }
};

и ваш код будет выглядеть следующим образом:

const std:string someStdString = "blahblahblah";
// just for the context of the comparison:
FastLiteralWrapper someString(someStdString);
if( someString == "(" ) {
   //do something
} else if( someString == ")" ) {
   //do something else
} else if// this chain can be very long

NB. самое быстрое решение - за счет большего редактирования - это, вероятно, построение (идеального) хэша или тригонных строк литералов для перечисляемых констант, а затем просто switch для искаженного значения. Длинные цепи if/else if обычно пахнут плохой ИМО.

Ответ 2

Ну, кроме С++ 14 string_literal, вы можете легко составить код решения:

• Для сравнения с одним символом используйте символьный литерал и:

  bool operator==(const std::string& s, char c)
  {
    return s.size() == 1 && s[0] == c;
  }
  

• Для сравнения со строковым литералом вы можете использовать что-то вроде этого:

  template<std::size_t N>
  bool operator==(const std::string& s, char const (&literal)[N])
  {
    return s.size() == N && std::memcmp(s.data(), literal, N-1) == 0;
  }
  

Отказ от ответственности:

• Первый может быть даже лишним,
• Делайте это только в том случае, если вы измеряете улучшение по сравнению с тем, что у вас было.

Ответ 3

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

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

class Literal {
    char const* d_base;
    std::size_t d_length;
public:
    template <std::size_t Length>
    Literal(char const (&base)[Length]): d_base(base), d_length(Length - 1) {}
    bool operator== (std::string const& other) const {
        return other.size() == this->d_length
            && !other.memcmp(this->d_base, other.c_str(), this->d_length);
    }
    bool operator!=(std::string const& other) const { return !(*this == other); }
};
bool operator== (std::string const& str, Literal const& literal) {
    return literal == str;
}
bool operator!= (std::string const& str, Literal const& literal) {
    return !(str == literal);
}

Очевидно, это предполагает, что ваши литералы не вставляют нулевые символы ('\ 0'), кроме неявно добавленного конечного нулевого символа, поскольку в противном случае статическая длина была бы искажена. Используя С++ 11 constexpr, можно было бы защититься от этой возможности, но код становится несколько более сложным без веских оснований. Затем вы сравните свои строки, используя что-то вроде

if (someString == Literal("(")) {
    ...
}
else if (someString == Literal(")")) {
    ...
}

Ответ 4

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

Как только вы это сделаете, сравнение строк эквивалентно сравнению их адресов.

Это на самом деле довольно старый метод, впервые популяризированный с помощью языка LISP.

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

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

Ответ 5

2 другие идеи:

A) Создайте FSA с помощью инструмента лексического анализатора, такого как flex, поэтому строка преобразуется в значение целочисленного токена, в зависимости от того, что оно соответствует.

B) Используйте длину, чтобы разбить длинные цепи elseif, возможно, частично управляемые таблицами

Почему бы не получить длину строки что-то, наверху, просто сравните с литералами, которые она могла бы сопоставить.

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

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

int len = strlen (something);
if ( ! knownliterallength[ len]) {
    // not match
    ...
} else {
    // First char may be used to index search, or literals are stored in map with *func()

    switch (len)
    {
        case 1:  // Could use a look table index by char and *func()
            processchar( something[0]);
        break;

        case 2: // Short strings
        case 3: 
        case 4:
            processrunts( something);
        break

        default:
        //  First char used to index search, or literals are stored in map with *func()
            processlong( something);
        break
   }
}

Ответ 6

Это не самое приятное решение, но оно оказалось довольно быстрым, когда нужно сравнивать короткие строки (например, операторы и контрольные символы/ключевые слова в парсере script?).

Создайте дерево поиска на основе длины строки и сравните только символы. Попробуйте представить известные строки как перечисление, если это делает его более чистым в конкретной реализации.

Краткий пример:

enum StrE {
  UNKNOWN = 0 ,
  RIGHT_PAR ,
  LEFT_PAR ,
  NOT_EQUAL ,
  EQUAL
};

StrE strCmp(std::string str)
{
  size_t l = str.length();
  switch(l)
  {
    case 1:
    {
      if(str[0] == ')') return RIGHT_PAR;
      if(str[0] == '(') return LEFT_PAR;
      // ...
      break;
    }
    case 2:
    {
      if(str[0] == '!' && str[1] == '=') return NOT_EQUAL;
      if(str[0] == '=' && str[1] == '=') return EQUAL;
      // ...
      break;
    }
    // ...
  }
  return UNKNOWN;
}



int main()
{
  std::string input = "==";

  switch(strCmp(input))
  {
    case RIGHT_PAR:
      printf("right par");
      break;
    case LEFT_PAR:
      printf("left par");
      break;
    case NOT_EQUAL:
      printf("not equal");
      break;
    case EQUAL:
      printf("equal");
      break;
    case UNKNOWN:
      printf("unknown");
      break;
  }
}