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字符串比較方法和手動寫入方法之間的巨大時間差

回答

相關問題