3

O(n)为什么 C++ STL 字符串查找子字符串的 find 方法比简单的字符串传递要快，我有点震惊。这里有两个不同的函数：为什么在 , 中找到的第二个函数str1比str2第一个函数快（优化得很好）？我知道第一个函数的任务略有不同，但它仍然只是一个传递str1and str2 (O(n))，而第二个函数可能O(n^2)需要str1在str2. 真的为什么？你们有什么想法吗？先感谢您。

PS 这些功能是更大项目的一部分。它们在我的代码中被调用了很多次来比较两个字符串。如果我使用第二个函数，整个代码的运行时间几乎是一半（135 秒 VS 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;
}
4

3 回答 3

2

区别在于数组访问器[i]与指针算术。

使用str1[i]andstr2[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完全删除使用）

于 2013-05-10T12:37:35.080 回答
2

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

可能的解释是您的 STL 版本实现使用 CPU 上可用的较长寄存器对字符进行批量比较。您可以将多个字符打包到一个寄存器中，然后并行比较它们。这样，您可以一步比较几个连续的字符（即使使用标准的 64 位寄存器，您也可以打包 8 个字符并同时比较它们）。有关讨论，请参阅此堆栈溢出问题。

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

您可以通过运行测试来检查：速度差异是由于匹配还是不匹配，还是两者兼而有之？对于我的第二个解释，您会看到在 STL 版本中不匹配更好，第一个解释会加快匹配速度。

于 2013-05-10T12:27:20.467 回答
2

我已经跟踪了 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;
}
于 2013-05-10T12:26:11.273 回答