STL字符串比较方法和手动写入方法之间的巨大时间差

程序的任务是检查字符串s2是否是给定长度相等的s1和s2的另一个字符串（s1 + s1）的子字符串。例如：[s1，s2] = [“abc”，“bca”]应该返回true，而[s1，s2] = [“abc”，“bac”]应该返回false。STL字符串比较方法和手动写入方法之间的巨大时间差

并且两个字符串的长度限制是10^5。使用(s1+s1).find(s2) == string::npos约需0.1秒完成。

我实现它在一个复杂的O（n * m）天真的方法，它花了30秒！

s1 = s1 + s1; 
bool f = 0; 
for(int i = 0;i < s1.size() - s2.size() + 1;i++){ 
    f = 1; 
    for(int j = 0;j < s2.size();j++){ 
     if(s1[i+j] != s2[j]){ 
      f = 0; 
      break; 
     } 
    } 
    if(f) 
     break; 
} 
//the answer is f

所以我认为C++一样使用KMP算法，但我发现它是只用天真的方法有一些改进的实施，defind和GNU GCC。

但这甚至不是最大的问题。当我用s1.compare(i, s2.size(), s2)替换内部循环时，大约与STL找到方法.1秒大致相同。

bool f = 0; 
for(int i = 0;i < s1.size() - s2.size() + 1;i++){ 
    if(s1.compare(i, s2.size(), s2) == 0){ 
     f = 1; 
     break; 
    } 

}

那么C++编译器是以不同的方式实现比较吗？

C++编译器使用的方法在使用相同复杂度的情况下，如何超越朴素方法达300倍？

注：我用于先前码的测试是

S1 = “AB” * 50000 + “CA”

S2 = “AB” * 50000 + “AC”

来源

2017-08-26 Omar Elawady

它很大程度上取决于如何实现'string :: find（）'。我会看看以下内容：https://stackoverflow.com/questions/3183582/what-is-the-fastest-substring-search-algorithm – Frank

@Frank我搜索了很多，以了解它如何在gcc中实现。但我找不到标准或类似的东西，我不明白源代码。但没有人 - 我发现 - 说它使用了先进的算法，只有改进的天真方法。 –

嗯，是的。运行时库比天真的方法更有效地执行'比较'。您提供的测试数据对于朴素算法来说几乎是最糟糕的情况，对于像Boyer-Moore和Knuth-Morris-Pratt这样的东西来说，这几乎是最好的例子。因为's2'以'c'结尾，并且's1'中只有两个'c'的实例，所以这些算法最终只需要进行两次字符串比较。 –

正如以上评论中回答的那样。

该程序在非优化的调试版本中运行，切换到释放模式后时间缩短到只有3秒。

剩下的差异可能是因为运行时库使用了一些类似memcmp的方法，与逐个循环和比较字符相比，它经过了大量优化。

来源

2017-08-26 22:48:04

STL字符串比较方法和手动写入方法之间的巨大时间差

回答

相关问题