Eine Alternative zu der Funktion char * strstr(const char *s1, const char *s2) ?
-
dann solltest du entweder in dem code deiner c-lib, so du daran kommst, nachschauen oder schlicht nachmessen, wie sich das ding verhält.
im zweifelsfall ist die implementierung in der c-lib aber immer ein kompromiss und unterstützt kurze bis mittel lange strings am besten. will heißen: wenn du nur sehr große strings hast, wirst du sicher etwas besseres implementieren können. wenn du nur sehr kleine hast, ist der naive ansatz im zweifelsfall sogar schneller als alle komplexen algorithmen.
-
CStoll schrieb:
Ich weiß nicht genau, was für ein Verfahren strstr() verwendet (aber ich denke schon, daß das nicht der naive Ansatz ist)
Wahrscheinlich schon. Es ist wenig sinnvoll, so eine allgemeine Funktion zu spezialisieren, indem man da einen hochperformanten Algorithmus schreibt, weil sowieso jeder, der hier eine wirklich effiziente Funktion braucht, eh seine eigene schreiben wird. String-Matching ist einfach je nach Anwendungsgebiet zu unterschiedlich.
Sowas zu implementieren ist aber übrigens ne ziemlich gute Übung.
-
Hi,
also ich will nur mal sagen, dass diese "String-in-String"-Suche auch wirklich keine triviale Angelegenheit ist. Selbst mit noch so gut optimierter Suche kann man üblicherweise sehr viel mehr rausholen, wenn man seine Anwendung so umstrickt, dass diese Suche möglichst selten durchgeführt wird.
Gruß,
Simon2.
-
Simon2 schrieb:
Selbst mit noch so gut optimierter Suche kann man üblicherweise sehr viel mehr rausholen, wenn man seine Anwendung so umstrickt, dass diese Suche möglichst selten durchgeführt wird.
Logisch. Man kommt nunmal nicht über eine linear abhängige Laufzeit hinaus, und bei großen Strings dauert das eben.
Aber es gibt genug Anwendungen, wo man um die Stringsuche eben einfach nicht herumkommt, es sei denn, man gibt sich mit Heuristiken zufrieden (z.B. BLAST, wobei BLAST ja noch mehr macht als einfach nur zu suchen).
-
Konrad Rudolph schrieb:
...
Aber es gibt genug Anwendungen, wo man um die Stringsuche eben einfach nicht herumkommt, ...Ebenfalls: Logisch !
Mir ist hier bei "Optimierungsfragen" halt öfter aufgefallen, dass "zu lokal" geschaut wird ("Hilfe, mein Programm verbraucht 87% CPU in Funktionxy - kann ich die irgendwie schneller machen ?").
Da kommen dann bisweilen die krudesten Optimierungstipps ("Funktions-Call oder Speicher schneller machen") ... während das große Optimierungspotential in Wirklichkeit gar nicht darin liegt, diese Funktion zu beschleunigen, sondern sie seltener aufzurufen....
... aber das erfordert bisweilen größere Designklimmzüge und wird deswegen gescheut.Wie immer: Das eine tun und das andere nicht lassen !
Gruß,
Simon2.
-
Die strstr-Funktion sollte eigentlich in Assembler implementiert sein. Zumindest ist es die von MS. Ich behaupte jetzt einfach mal, dass du eine aehnliche Performance mit reinem C++ niemals erreichen wirst, egal welchen Algorithmus du benutzt.
-
Alles eine Frage des verwendeten Algorithmus - QuickSort in "normalem" C++ kann auch schneller sein als BubbleSort in Assembler. (klar, mit Mikro-Optimierungen kann man im Ernstfall noch einige Geschwindigkeitsvorteile herausholen, aber entscheidend ist zunächst einmal die Größenordnung, mit der du dich herumschlagen mußt)
-
Ajaw schrieb:
Die strstr-Funktion sollte eigentlich in Assembler implementiert sein. Zumindest ist es die von MS. Ich behaupte jetzt einfach mal, dass du eine aehnliche Performance mit reinem C++ niemals erreichen wirst, egal welchen Algorithmus du benutzt.
Diese Aussage ist falsch (und zeigt irgendwie ein leichtes Verständnisproblem für Algorithmen). Die Verwendung von Assembler im Vergleich zu C++ bringt hier, bei eingeschalteten Optimierungen und einem modernen Compiler, quasi gar nichts.
Ich habe Implementierungen geschrieben, die gemessen die exakt selbe Geschwindigkeit wie in Assembler geschriebene Routinen hatten. Der vom Compiler produzierte Assembler-Code war sowieso ziemlich ähnlich.
-
Ihr versteht mich falsch.
Vielleicht habe ich mich auch einfach unklar ausgedrueckt. Klar muss C++ nicht per se langsamer sein als Assembler. Ich bezweifle allerdings, dass der von deinem Compiler erzeugt ASM-Code auch nur annaeherend so performant ist wie die existierende strstr-Implementierung. Egal welchen Algorithmus du verwendest. 
-
it depends. sei dir mal nicht so sicher, was die überlegenheit der asm-lösung angeht. das trifft insbesondere zu, wenn die cpu nicht mehr ganz zu der gedachten lösung passt.
auch wenn beide nur auf die gleiche plattform optimieren, ist der unterschied inzwischen sehr gering, was die normalen algorithmen und verfahrensweisen angeht.
-
Ajaw schrieb:
Ihr versteht mich falsch.
Vielleicht habe ich mich auch einfach unklar ausgedrueckt. Klar muss C++ nicht per se langsamer sein als Assembler. Ich bezweifle allerdings, dass der von deinem Compiler erzeugt ASM-Code auch nur annaeherend so performant ist wie die existierende strstr-Implementierung. Egal welchen Algorithmus du verwendest. Ich habe Dich schon verstanden und ich sage Dir: das ist falsch. Eine direkte ASM-Implementierung ist *nicht* schneller als eine gut implementierte und klug optimierte C++-Version.
-
Ajaw schrieb:
Ihr versteht mich falsch.
Vielleicht habe ich mich auch einfach unklar ausgedrueckt. Klar muss C++ nicht per se langsamer sein als Assembler. Ich bezweifle allerdings, dass der von deinem Compiler erzeugt ASM-Code auch nur annaeherend so performant ist wie die existierende strstr-Implementierung. Egal welchen Algorithmus du verwendest. Wenn du von identischen Voraussetzungen ausgehst (sprich: gleicher Algorithmus), könnte die Assembler-Variante einen leichten Vorteil haben (wie groß der ist, hängt von den Fähigkeiten des Autors vs. Compilers ab). Aber was nützt die beste Mikro-Optimierung, wenn du von einem um Größenordnungen langsameren Algorithmus ausgehst? (und da hängt es mitunter von der konkreten Aufabenstellung ab, welcher Algorithmus der "beste" ist - ein klarer Nachteil für strstr(), auf alle Situationen reagieren muß)
-
Konrad Rudolph schrieb:
Ich habe Dich schon verstanden und ich sage Dir: das ist falsch. Eine direkte ASM-Implementierung ist *nicht* schneller als eine gut implementierte und klug optimierte C++-Version.
Was zu beweisen waere.
-
Ajaw schrieb:
Konrad Rudolph schrieb:
Ich habe Dich schon verstanden und ich sage Dir: das ist falsch. Eine direkte ASM-Implementierung ist *nicht* schneller als eine gut implementierte und klug optimierte C++-Version.
Was zu beweisen waere.
Wie gesagt, ich habe entsprechende Performance-Tests bereits gemacht (eine Praktikums-Arbeit handelte von der Optimierung von Stringsuch-Algorithmen) und ich bin beiweitem nicht der einzige, der solche Tests gemacht hat.
Messungen ergeben ganz klar, dass *selbst wenn* ASM schneller sein *sollte*, dann ist dieser Unterschied *so* gering, dass man ihn auf modernen Maschinen *nicht* messen kann!