为什么查找字符串的find方法比我的单次查找速度更快？

Question

我很惊讶C++ STL字符串的查找子字符串方法find()比简单的O(n)字符串遍历还要快。这里有两个不同的函数：第一个函数只是在str1和str2上做了一次O(n)的遍历，但仍然没有第二个函数(str2中查找str1)，后者可能需要O(n^2)的时间复杂度。我知道它们做的工作稍微有些不同，但为什么第二个函数更快呢？你们有任何想法吗？谢谢！ P.S 这两个函数是整个项目的一部分。它们在我的代码中被调用了很多次，用第二个函数运行时间大约减半(135秒对235秒)！

bool Is_Included1(string str1, string str2)
{
    size_t i,s;
    s=str1.size();
    if (s<=str2.size())
    {
        for (i=0;i<s;i++)
            if (str1[i]!=str2[i])
                return false;
        return true;
    }
    return false;
}


bool Is_Included2(string str1, string str2)
{
    size_t i;
    if (str1.size()<=str2.size())
    {
        i=str2.find(str1);
        if (i==0)
            return true;
        else
            return false;
    }
    return false;
}

- Hamed100101

---

"我知道第一个函数执行了稍微不同的任务" 好的... - gdoron

第一个函数执行的功能截然不同。这与“轻微”毫不相符...第一个函数只是检查第一个字符串是否为第二个字符串的前缀... - ppeterka

我经过测试确认STL比手写代码更快，不知何故，经常使用的库比自制代码更快。答案肯定在STL代码中... - philippe lhardy

Boyer Moore算法的示例是O(n+m)而不是O(n.m)...。 - philippe lhardy

谢谢提供链接。但我还在思考我的代码，它是O(m)或(n)，取决于哪个字符串更短。我想知道他们如何优化他们的代码？例如，在我的代码（Is_Included1）中是否有任何可能的优化？ - Hamed100101

Answer 1

我已经追踪了GCC 4.7.2的实现。 其复杂度为O(nm)，其中n，m是两个字符串的长度。

假设n.size()小于m.size()，对于每个可能的m的起始点i，它首先比较n[0]和m[i]（traits_type::eq），然后调用traits_type::compare，它实际上执行__builtin_memcmp()。

这不是确切的实现，但它说明了算法。

for (size_t i=0; i<m.size(); ++i) {
    if (traits_type::eq(n[0], m[i]) &&
        traits_type::compare(n[1], m[i+1], n.size()-1) == 0) {
            return i;
    }
}
return -1;

虽然算法的时间顺序更差，但我猜测这是因为 __builtin_memcmp() 并没有逐个字符进行比较，因此比我们预期的要快。

顺便说一下，如果您经常调用该函数，应传递两个字符串的 const 引用而不是传值，这会导致不必要的复制。

如下所示：

bool Is_Included2(const string& str1, const string& str2)
{
    if (str1.size() > str2.size()) return false;
    return str2.find(str1) == 0;
}

- cw.ahbong

Answer 2

数组访问器[i]与指针算术之间的区别。

str1[i]和str2[i]的使用是主要区别。这些访问器通常不像使用底层指针算法一样优化，例如，const char* c1 = str1.cstr()，然后执行++c1; ++c2来迭代它们（这是任何STL实现在幕后都会做的事情）。

一般来说，底层硬件更善于迭代指针而不是数组。有时编译器可以优化循环以使用指针算术而不是数组算术，但由于std::string使用复杂的重载operator[]实现，因此它基本上总是会通过每次迭代循环来进行arrayBase+offset操作。

试一下：

bool Is_Included1(string str1, string str2)
{
    size_t i,s;
    s=str1.size();
    if (s<=str2.size())
    {
        const char* c1 = str1.c_str();
        const char* c2 = str2.c_str();
        for (i=0;i<s;i++, c1++, c2++)
            if (*c1!=*c2)
                return false;
        return true;
    }
    return false;
}

看看这与STL参考实现相比如何。

(请注意，STL版本很可能仍然会更快，因为现在您可以进一步优化它以完全删除对 int i 的使用)

- jstine

---

我想提供一个通用建议：在C++中，忘记数组访问曾经存在过吧！迭代器更高效、更灵活，因为它们也适用于其他没有随机访问的容器。这个建议在C语言中也大多适用。 - Jan Hudec

如果编译器可以内联operator[]，那么它也应该能够进行优化。但是这有两个前提条件：启用内联和关闭断言（检查、检查、检查...是的，operator[]确实包含断言）。 - Jan Hudec

Answer 3

原因可能至少部分是你的查询结构特定，找到原因是一个有趣的侦探挑战！例如，当str2比str1长得多（并且不包含完全不同的字符）时，你的实现显然会更快。为避免混淆，暂时假设两个字符串具有相同的长度。

可能的解释是，STL版本的实现使用CPU上可用的较长寄存器批量比较字符。你可以将几个字符装入单个寄存器中，并同时进行比较。这样，您可以一次比较几个连续字符（即使使用标准64位寄存器，也可以打包8个字符并同时比较它们）。有关讨论，请参见此Stack Overflow问题。

另一个可能的解释是，STL使用一种算法，例如从字符串的末尾开始比较字符串，而字符串的结尾往往比字符串的前缀差异更大。

你可以通过运行测试来检查：速度差异是由匹配还是非匹配引起的？对于我的第二个解释，你会发现STL版本中的非匹配更好，而第一个解释会给匹配带来更多速度。

- eyal