Welche Funktion ist schneller: strcmp oder strlen?

hustbaer

just_trie_it schrieb:

otze schrieb:

Einen Trie? genau, einfach #include <trie> wa?

Ein trie braucht etwa 256 mal so viel Speicher wie eine normale map und etwa 500 mal so viel wie ein sortiertes Array. Und ist dementsprechend langsamer bei grossen Listen.

Mit einem Trie kann man sogar Daten komprimieren. Kommt nur darauf was man für Daten hat und wie man den Trie genau implementiert.

@tntnet
was findest du denn an "maximal kompiliziert" komisch?

@dot
Das hatte ich bereits alles im Eingangspost geschrieben.

Sofern strlen schneller als strcmp ist, wäre es besser, zuerst die strlen(stichwort) mit strlen(listeneintrag) zu vergleichen.

wenn != : nächster listeneintrag
wenn == : genaues vergleichen mit strcmp.

mit diesem system würde ich übermäßig viele strcmp sparen (was ein vorteil wäre, wenn es mit strlen schneller gehen würde).

@RonjaRaeuber
danke... für nichts.
Die von dir gepostete Quelle hat irgendwie keine aussagekraft.
dass "strlen length 1" weniger zeit braucht als "strcmp length 33, -1" (was auch immer das -1 bedeutet soll) hätte ich mir irgendwie noch gerade so erschließen können.
google ist halt doch kein wunderheilmittel.

dot

Ohne das konkrete Problem zu kennen, ist es unmöglich eine optimale Lösung für das konkrete Problem anzugeben. Je nachdem, worum es sich beim konkreten Problem genau handelt, wird entweder eine einfache lineare Suche, Binärsuche, Hash Table, ein Trie, ein DAWG oder wer weiß was sonst noch zu bevorzugen sein.

Wenn du eine konkrete Antwort haben willst, dann stell eine konkrete Frage zu einem konkreten Problem. Deine ursprüngliche Frage macht leider zur Hälfte keinen Sinn und die andere Hälfte kann nicht konkret beantwortet werden...

Edit:

ich bins...threadstarter schrieb:

Das hatte ich bereits alles im Eingangspost geschrieben.

Sofern strlen schneller als strcmp ist, wäre es besser, zuerst die strlen(stichwort) mit strlen(listeneintrag) zu vergleichen.

wenn != : nächster listeneintrag
wenn == : genaues vergleichen mit strcmp.

mit diesem system würde ich übermäßig viele strcmp sparen (was ein vorteil wäre, wenn es mit strlen schneller gehen würde).

Du vergisst dabei aber wohl, dass strlen() immer den ganzen String durchlaufen muss, während strcmp() bei der ersten Unstimmigkeit abbrechen kann!? Sofern deine Strings sich also nicht alle nur in den letzten paar Zeichen unterscheiden und dabei gleichzeitig aber auch möglichst alle verschieden lang sind, wirst du damit dann übermäßig viele potentiell schnellere strcmp() sparen und durch effektiv langsamere strlen() ersetzen...

Swordfish

...

ich bins...threadstarter schrieb:

@RonjaRaeuber
danke... für nichts.
Die von dir gepostete Quelle hat irgendwie keine aussagekraft.
dass "strlen length 1" weniger zeit braucht als "strcmp length 33, -1" (was auch immer das -1 bedeutet soll) hätte ich mir irgendwie noch gerade so erschließen können.
google ist halt doch kein wunderheilmittel.

strlen length 33 415 us [830]
strcmp length 33, -1 116 us [232]

Es gibt da ja noch mehr als strlen von 1... und im Quellcode siehst du auch, was das -1 ist, nämlich das Ergebnis von strcmp (strings sind ungleich, bzw string 1 kleiner als der zweite)

dot

Wenn deine Anwendung derart performancekritisch ist, solltest du dir überhaupt mal die Frage stellen, ob nullterminierte Strings denn die richtige Lösung sind. Statt Nullterminierung kann man z.B. auch einfach die Länge des String separat speichern, was viele Dinge unter Umständen wesentlich effizienter gestaltet. Und wenn du schon dabei bist, Entscheidungen zu hinterfragen, dann überleg dir auch das mit C nochmal gut, denn C++ hat gegenüber C wesentliche Vorteile, insbesondere auch was Performance betrifft...

tntnet

threadstarter schrieb:

ich will die sache nicht maximal kompilizieren.

ich bins...threadstarter schrieb:

@tntnet
was findest du denn an "maximal kompiliziert" komisch?

"Komplizieren" gibt es in der deutschen Sprache nicht als Verb. Das ist komisch. "Ich will die Sache nicht maximal kompliziert machen" geht.

Mechanics schrieb:

tntnet schrieb:

Das bedeutet entweder mehr Komplexität oder die Verwendung von C++

Ist ja jetzt nicht so, dass man in C keine Hashes implementieren könnte. Es gibt z.B. die apr Bibliothek, wahrscheinlich auch zig andere.

Natürlich kann man in C Hashtabellen implementieren. Oder fertige von der Stange nehmen. Ich mag halt C++, da man dort solche Sachen in einfache und robuste Interfaces packen kann. Ein einfaches Beispiel wäre auch das qsort in C im Gegensatz zum std::sort in C++. Beides implementiert einen Sortieralgorithmus. Bei C muss ich mit void pointern hantieren und die Größe der Elemente mit geben. Bei C++ bleibt mir das erspart.

Jester

tntnet schrieb:

ich bins...threadstarter schrieb:

@tntnet
was findest du denn an "maximal kompiliziert" komisch?

"Komplizieren" gibt es in der deutschen Sprache nicht als Verb. Das ist komisch. "Ich will die Sache nicht maximal kompliziert machen" geht.

http://www.duden.de/rechtschreibung/komplizieren

dot schrieb:

dann überleg dir auch das mit C nochmal gut, denn C++ hat gegenüber C wesentliche Vorteile, insbesondere auch was Performance betrifft...

Muahuahuahuahua!
Der war gut!
Son Schwachsinn hab ich ja schon lange nicht mehr hier gelesen.

Ethon

Witzigerweise schreiben die GCC Jungs gerade den GCC um, weil C++ im Vergleich zu C Speicher- und Performancevorteile bringt.
Also so daneben ist die Behauptung wirklich nicht, wenn man aufpasst welche Features man verwendet.

tntnet

Jester schrieb:

http://www.duden.de/rechtschreibung/komplizieren

Interessant. Das war mir nicht bewusst. Ich finde die Formulierung befremdlich. "Das kompliziert die Sache" finde ich ok, aber "ich kompliziere maximal" erscheint mir nicht korrekt. Aber ok - ich muss zugeben, dass ich es nicht wirklich weiß.

volkard

tntnet schrieb:

Jester schrieb:

http://www.duden.de/rechtschreibung/komplizieren

Interessant. Das war mir nicht bewusst. Ich finde die Formulierung befremdlich. "Das kompliziert die Sache" finde ich ok, aber "ich kompliziere maximal" erscheint mir nicht korrekt. Aber ok - ich muss zugeben, dass ich es nicht wirklich weiß.

Sehe ich genauso. Komplizieren als verb immer ohne Subjekt, also Passivsätze.

Aktiv nimmt man
http://www.duden.de/suchen/dudenonline/verkomplizieren

Ethon schrieb:

weil C++ im Vergleich zu C Speicher- und Performancevorteile bringt.

noch so einer, der an märchen glaubt, unglaublich.
wer hat euch denn diesen floh bloß ins ohr gesetzt?

du glaubst also auch, dass
wenn mann programme mit c++ schreibt, da ein effizienterer maschinencode raus kommt, als wenn man ein programm mit c schreibt

knivil

Trollor?!

Ich kann nur Stoustrup wiederholen. Beispiel qsort: Wenn alle Typinformationen weggeworfen werden und mit void* gearbeitet wird, dann kann der Optimierer/Compiler diese Information nur schwer benutzen.

volkard

fairy tell believer schrieb:

du glaubst also auch, dass wenn mann programme mit c++ schreibt, da ein effizienterer maschinencode raus kommt, als wenn man ein programm mit c schreibt

Normalerweise nicht, weil viele Programmierer die Effizienz überhaupt nicht mitbeachten.

Aber wenn man sich nur ein wenig Mühe gibt, baut man bei vergleichbarem Aufwand mit C++ immer schnellere Programme als mit C.

knivil schrieb:

Trollor?!
Ich kann nur Stoustrup wiederholen. Beispiel qsort: Wenn alle Typinformationen weggeworfen werden und mit void* gearbeitet wird, dann kann der Optimierer/Compiler diese Information nur schwer benutzen.

ob der compiler das schwer hat oder nicht interessiert doch niemanden.
und wegen einer eventuell möglichen optimierung, wegen eines features gleich auf allgemeine eigenschaften zu schließen ist ein wenig albern, findest du nicht?

volkard schrieb:

Aber wenn man sich nur ein wenig Mühe gibt, baut man bei vergleichbarem Aufwand mit C++ immer schnellere Programme als mit C.

die begründung täte mich doch interessieren sehr.

SeppJ

fairy tell believer schrieb:

ob der compiler das schwer hat oder nicht interessiert doch niemanden.

Doch, das ist sogar ganz entscheidend, denn hier ist Schwer = Unmöglich.

und wegen einer eventuell möglichen optimierung, wegen eines features gleich auf allgemeine eigenschaften zu schließen ist ein wenig albern, findest du nicht?

Wenn es ein entscheidendes Feature ist, das andauernd benutzt wird?

volkard schrieb:

Aber wenn man sich nur ein wenig Mühe gibt, baut man bei vergleichbarem Aufwand mit C++ immer schnellere Programme als mit C.

die begründung täte mich doch interessieren sehr.

Siehe oben. Die Anpassung von allgemeinen Algorithmen auf spezielle Gegebenheiten geht in C++ so einfach, dass man es nicht einmal bemerkt. Dadurch steht eine große Vorauswahl fertiger Algorithmen bereit, die trotzdem auf das konkrete Problem bezogen optimal umgesetzt werden. Dies verringert den Entwicklungsaufwand erheblich, trotzdem wird optimaler Code erzeugt. Um den gleichen optimalen Code zu erzeugen müsste man in C selber Hand anlegen (->großer Aufwand). Für vergleichbar geringen Aufwand müsste man sich hingegen mit suboptimalen Mitteln beim Benutzen von typenunabhängigem Code zufrieden geben (->langsam).

Das war nur ein Feature. Allgemein hat man natürlich noch ganz andere Features, die den Entwicklungsaufwand erheblich verringern, dabei aber zu dem üblichen Vorgehen in C gleichwertigen (oder manchmal sogar besseren: Exceptions) Code erzeugen, so dass man bei gleichem Aufwand mehr Zeit für Optimierungen hat, wohingegen der C-Programmierer noch Zeit verschwenden muss, zu prüfen, ob seine Speicherfreigabestrategie auch wirklich idiotensicher ist.

P.S.: Bitte lerne Englisch!

volkard

fairy tell believer schrieb:

volkard schrieb:

Aber wenn man sich nur ein wenig Mühe gibt, baut man bei vergleichbarem Aufwand mit C++ immer schnellere Programme als mit C.

die begründung täte mich doch interessieren sehr.

Weil es so schnelle Sachen wie std::sort gibt. Oder Strings, die ihre Länge kennen. Die kann man einfach mal nehmen. Und wenn sie nicht passen, nimmt man sie nicht, allerschlimmstenfalls geht man wie in C vor. Und weil man mit Klassen und Templates weiter abstrahieren kann, ganz ohne Ovberhead, da spart man Zeit, macht weniger Fehler, also hat man mehr Zeit und Möglichkeiten, an Performance zu denken. RAII und Exceptions sorgen dafür, daß man nicht mehr 50% des Codes mit Fehlerbehandlung vollballern muss (und Exceptions sind schneller).

Na dann ist doch alles klar.
C++ und geringerer Entwicklungsaufwand: dem stimme ich voll und ganz zu.
C++ Programme performanter als C: no way, weil C++ keinen Maschinencode erzeugt, der performanter ist.

Btw. kann ich mir in C einen Sortieralgo auch selber schreiben, wenn mir qsort zu lahm sein sollte.

volkard

fairy story schrieb:

Btw. kann ich mir in C einen Sortieralgo auch selber schreiben, wenn mir qsort zu lahm sein sollte.

Das ruft nach einem Vergleich.
Sagen wir mal, einen um 1G großen Eingabestrom wortweise lesen (whitspace als trenner). Stoppuhr starten. Sortieren. Stoppuhr stoppen. Doppeleinträge löschen. Anzahl der ubrigen Einträge anzeigen. Sortierzeit anzeigen.