Différence de temps énorme entre la méthode de comparaison de chaîne STL et écrite manuellement

La tâche du programme est de vérifier si une chaîne s2 est une sous-chaîne d'une autre chaîne (s1 + s1) donnée s1 et s2 de longueur égale. Par exemple: [s1, s2] = ["abc", "bca"] devrait retourner true alors que [s1, s2] = ["abc", "bac"] devrait retourner false.Différence de temps énorme entre la méthode de comparaison de chaîne STL et écrite manuellement

et les limites de la longueur des deux chaînes est de 10^5.

en utilisant (s1+s1).find(s2) == string::npos a pris environ 0,1 seconde pour terminer.

Je l'ai implémenté dans une approche naïve avec une complexité de O (n * m) et cela a pris 30 secondes !!

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

Je pensais que C++ utilisé un algorithme comme KMP mais je trouve qu'il est l'implémentation defind et GNU gcc utilisée seule l'approche naïve avec quelques améliorations.

Mais ce n'est même pas le plus gros problème. lorsque j'ai remplacé la boucle interne par s1.compare(i, s2.size(), s2), il a fallu environ la même heure que la méthode STL find .1 second.

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

}

Les compilateurs C++ implémentent-ils de la même façon la comparaison?

Et quelles sont les améliorations de la méthode utilisée par les compilateurs C++ pour dépasser l'approche naïve de 300 fois tout en utilisant la même complexité?

NOTE: Le test j'ai utilisé pour les codes précédents est

s1 = "ab" * 50000 + "ca"

s2 = "ab" * 50000 + "ac"

Source

2017-08-26 Omar Elawady

Cela dépend beaucoup de la façon dont 'string :: find()' est implémenté. Je voudrais regarder ce qui suit: https://stackoverflow.com/questions/3183582/what-is-the-fastest-substring-search-algorithm – Frank

@Frank J'ai beaucoup cherché pour savoir comment il est implémenté dans gcc. Mais je ne pouvais pas le trouver dans une norme ou quelque chose comme ça et je n'ai pas compris le code source. Mais personne - je l'ai trouvé - a dit qu'il utilisait un algorithme avancé, seulement l'approche naïve avec des améliorations. –

Eh bien, oui. Les bibliothèques d'exécution implémentent 'compare' plus efficacement que l'approche naïve. Les données de test que vous avez fournies sont presque un pire cas pour l'algorithme naïf, et presque un meilleur pour des choses comme Boyer-Moore et Knuth-Morris-Pratt. Parce que 's2' se termine par' c', et qu'il n'y a que deux instances de 'c' dans' s1', ces algorithmes ne doivent effectuer que deux comparaisons de chaînes. –

Comme répondu dans les commentaires ci-dessus.

Le programme a été exécuté dans une version de débogage non optimisée et le temps a été réduit à seulement 3 secondes après le passage en mode de libération. La différence restante pourrait être parce que la bibliothèque d'exécution utilise une méthode comme memcmp qui est fortement optimisée par rapport à la boucle et en comparant les caractères un par un.

Source

2017-08-26 22:48:04

Différence de temps énorme entre la méthode de comparaison de chaîne STL et écrite manuellement

Répondre

Questions connexes