Welche Funktion ist schneller: strcmp oder strlen?

c11 schrieb:

c nicht c++ schrieb:

ich programmiere in c!!! nix mit c++

lol c ist doch völlig veraltet!!

nö.

darum gehts hier aber auch nicht.

otze

@tntnet quark. Wlchen Algorithmus in der STL würdest du denn für das Problm verwenden?

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

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.

dot

3. Hash Table

Rein aus interesse: Aus welchem Grund musst du denn um jeden Preis C verwenden?

dot schrieb:

3. Hash Table

Rein aus interesse: Aus welchem Grund musst du denn um jeden Preis C verwenden?

Weil ich eben in C programmiere und nicht in C++.

Hashalgorithmen wurden schon vorgeschlagen.

dot

schnapsdrossel schrieb:

Hashalgorithmen wurden schon vorgeschlagen.

Wunderbar, dann hast du deine Antwort ja schon...

dot schrieb:

schnapsdrossel schrieb:

Hashalgorithmen wurden schon vorgeschlagen.

Wunderbar, dann hast du deine Antwort ja schon...

Nein.

Meine uprsprüngliche Frage, nämlich welche Funktion (strlen oder strcmp) schneller ist, wurde nicht wirklich beantwortet.

nein,wie kommst du darauf schrieb:

dot schrieb:

schnapsdrossel schrieb:

Hashalgorithmen wurden schon vorgeschlagen.

Wunderbar, dann hast du deine Antwort ja schon...

Nein.

Meine uprsprüngliche Frage, nämlich welche Funktion (strlen oder strcmp) schneller ist, wurde nicht wirklich beantwortet.

Dann teste das doch einfach selbst, oder googel.

z.B. hier: http://www.gnu.org/software/m68hc11/examples/bench-string.html

tntnet

Ich weiß, dass Du in C programmierst. Du (nehme ich mal an - Du bist ja leider nicht registriert) sagst ja selbst, dass Du die Sache nicht maximal komplizieren willst (auch wenn das eine merkwürdige Ausdrucksweise ist, aber dennoch verständlich).

Worauf ich hinaus wollte, dass es in C++ ein leichtes ist, die Strings in ein std::set zu packen oder in C++11 in eine std::unordered_set. Da findest Du die Strings dann doch sehr schnell, ohne dass Dein Code komplex wird. In C kannst Du das natürlich auch so machen, nur hast Du da nicht so was einfaches direkt zur Verfügung. Aber prinzipiell ist das der Weg, womit Du Performance bekommst und nicht strlen statt strcmp. Das hat ja auch der Benutzer "reinfall" gesagt.

Wobei ich Deine Problemstellung natürlich zu wenig kenne, um zu beurteilen, ob eine hashtable wirklich die geeignete Methode ist.

Und die Verwendung von C++ war ein Vorschlag, um Dein Problem einfacher zu lösen. Das ist kein Grund, sich darüber zu echauffieren. Wenn der Vorschlag nicht passt, dann sag doch einfach, dass das nicht machbar ist, statt Dich darüber aufzuregen, dass jemand C++ vorschlägt.

dot

Diese beiden Funktionen tun aber etwas völlig anderes, sind daher im Allgemeinen nicht einfach so vergleichbar, die Frage an sich macht also schon von vorn herein keinen Sinn und ist für die Lösung deines Problems wohl auch unerheblich, denn wenn du es tatsächlich mit einer großen Anzahl von Strings zu tun hast, dann ist eine lineare Suche sowieso elendslahm, auch wenn du einzelne Strings noch so schnell vergleichen kannst...

Eine Alternative zur Hash Table wäre z.B., die Strings sortiert zu halten und dann Binärsuche drauf zu machen. Wenn du wirklich viele Strings hast, wird eine gute Hash Table aber vermutlich auch wesentlich schneller sein als das...

Mechanics

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.

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.