Leistung std :: strstr vs. std :: string ::

Question

Mögliche Duplizieren finden:
C++ string::find complexity

Vor kurzem fand ich heraus, dass die Funktion std::string::find eine Größenordnung langsamer als die Funktion std::strstr - in meiner Umgebung mit GCC 4.7 unter Linux. Der Leistungsunterschied hängt von den Längen der Strings und von der Hardwarearchitektur ab.

Allerdings gibt es einen einfachen Grund für den Unterschied: std::string::find im Grunde ruft std::memcmp in einer Schleife - mit Zeitkomplexität O(m * n). Im Gegensatz dazu ist std::strstr stark für die Hardwarearchitektur optimiert (z. B. mit SSE-Anweisungen) und verwendet einen komplizierteren String-Matching-Algorithmus (anscheinend Knuth-Morris-Pratt).

Ich war auch überrascht, nicht die Zeit Komplexität dieser beiden Funktionen in den Sprachdokumenten zu finden (d. H. Entwürfe N3290 und N1570). Ich habe nur Zeitkomplexitäten für char_traits gefunden. Aber das hilft nicht, denn es gibt keine Funktion für die Teilstringsuche in char_traits.

Ich würde erwarten, dass std::strstr und memmem ähnliche Optimierungen mit fast identischer Leistung enthalten. Und bis vor kurzem nahm ich an, dass std::string::find intern memmem verwendet.

Die Fragen sind: Gibt es einen guten Grund, warum std::string::find nicht std::memmem nicht verwendet? Und ist das bei anderen Implementierungen anders?

Die Frage ist nicht: Was ist die beste Implementierung dieser Funktion? Es ist wirklich schwierig, für C++ zu argumentieren, wenn es langsamer als C ist. Es wäre mir egal, ob beide Implementierungen langsam wären. Es ist der Leistungsunterschied, der wirklich schmerzt.

Answer 1

Zuerst, was ist memmem? Ich kann dies weder im C++ - Standard noch im Posix-Standard finden (der alle Standard-C-Funktionen enthält).

Zweitens hängen alle Messwerte von den tatsächlichen Daten ab. Bei Verwendung von wird zum Beispiel KMP in vielen Fällen eine Pessimierung sein; wahrscheinlich die meisten Fälle, in denen die Elementfunktionen von std::string verwendet werden; Die Zeit zum Einrichten der erforderlichen Tabellen ist oft mehr als die Gesamtzeit des direkten Algorithmus. Dinge wie O(m*n) bedeuten nicht viel, wenn die typische Länge der Zeichenfolge kurz ist.