我怎样才能加快std :: string与字符串文字的比较？

Question

我有一堆代码,std::string比较类型的对象与字符串文字的相等性.像这样的东西:

//const std:string someString = //blahblahblah;
if( someString == "(" ) {
   //do something
} else if( someString == ")" ) {
   //do something else
} else if// this chain can be very long

比较时间累积到一个严重的数量(是的,我描述),所以加快它是很好的.

代码将字符串与众多短字符串文字进行比较,这种比较很难避免.保留声明的字符串std::string很可能是不可避免的 - 有数千行代码.离开字符串文字和比较==也可能是不可避免的 - 重写整个代码将是一个痛苦.

问题是Visual C++ 11附带的STL实现使用了一些奇怪的方法.==映射到std::operator==(const basic_string&, const char*)哪些调用basic_string::compare( const char* ),这些调用又调用std::char_traits<char>( const char* )哪些调用strlen()来计算字符串文字的长度.然后对两个字符串运行比较,并将两个字符串的长度传递给该比较.

编译器很难分析所有这些并发出遍历字符串文字两次的代码.使用短文字,时间不多,但每次比较都涉及遍历文字两次而不是一次.简单地打电话strcmp()很可能会更快.

有没有什么我可以做的,比如编写一个自定义比较器类,有助于避免在这种情况下两次遍历字符串文字？

Answer 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.最快的解决方案 - 以更多编辑为代价 - 可能是构建(完美)散列或trie映射字符串文字到枚举常量,然后只是switch查找值.长if/ else if链通常闻到不好的IMO.

Answer 2

好吧,除了C++ 14之外string_literal,您可以轻松编写解决方案:

1. 要与单个字符进行比较,请使用字符文字和:

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

2. 要与字符串文字进行比较,您可以使用以下内容:

   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;
   }
   

免责声明:

• 第一个甚至可能是多余的,
• 只有当你衡量你所拥有的改进时才这样做.

Answer 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')而不是隐式添加的终止空字符,否则静态长度会被扭曲.使用C++ 11 constexpr可以防止这种可能性,但代码变得更加复杂,没有任何充分的理由.然后你会用类似的东西来比较你的字符串

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

Answer 4

您可以获得的最快字符串比较是通过实习字符串:构建一个包含所有已创建字符串的大型哈希表.确保每当创建一个字符串对象时,首先从哈希表中查找它,如果没有找到预先存在的对象,则只创建一个新对象.当然,这个功能应该封装在你自己的字符串类中.

完成此操作后,字符串比较等同于比较它们的地址.

这实际上是一种先用LISP语言推广的老技术.

关键是,为什么这个更快,每个字符串只需要创建一次.如果您小心,您将永远不会从相同的输入字节生成两次相同的字符串,因此字符串创建开销由您处理的输入数据量控制.并且对所有输入数据进行哈希处理并不是什么大问题.

另一方面,当你编写某种解析器或解释器时,比较往往会一遍又一遍地涉及相同的字符串(比如你与文字字符串的比较).并且这些比较被简化为单个机器指令.

Answer 5

2个其他想法：

A) 使用像 flex 这样的词法分析器工具构建 FSA，因此字符串被转换为整数标记值，具体取决于它匹配的内容。

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
   }
}