Welche Funktion ist schneller: strcmp oder strlen?

Hallo,

ich habe einen String und muss ihn aus einer großen Masse von anderen Strings finden.

Meine Idee: jedes Element mit strcmp mit dem gegebenen String vergleichen.

besser?: zuerst strlen, damit fallen alle strings, die nicht genausolang wie der gegebene ist, raus

1. strcmp(suchbegriff,listenbegriff)
wenn 0 -> begriff gefunden.

2. wenn strlen(suchbegriff) == strlen(listenbegriff), dann
strcmp(suchbegriff,listenbegriff), wenn 0 -> begriff befunden

ich würde mir so überflüssige strcmps sparen.

Was haltet ihr davon?

ach ja, ich programmiere in C, d.h. wir reden von strlen und strcmp aus der stdlibc

und methode 2 bring natürlich nur was, wenn strlen schneller als strcmp ist.

ist das der fall?

Beides scheisse. strlen ist sogar noch scheissiger, selbst wenn strlen(suchbegriff) nur einmal berechnet wird (ausser in speziellen Umständen). Besser wird das, wenn du für jeden String auch noch die Länge mitspeicherst, aber selbst das ist dann immer noch eine verkappte Hashfunktion.

Wenn es dir wirklich um Geschwindigkeit geht bekommst du diese nicht durch Feintunen der Implementierung sondern durch Verbesserung des Algorithmus. qsort + bsearch wäre ein erster Schritt, der nächste wäre ein Upgrade auf C++11 und unordered_set.

reinfall schrieb:

Beides scheisse. strlen ist sogar noch scheissiger, selbst wenn strlen(suchbegriff) nur einmal berechnet wird (ausser in speziellen Umständen). Besser wird das, wenn du für jeden String auch noch die Länge mitspeicherst, aber selbst das ist dann immer noch eine verkappte Hashfunktion.

Wenn es dir wirklich um Geschwindigkeit geht bekommst du diese nicht durch Feintunen der Implementierung sondern durch Verbesserung des Algorithmus. qsort + bsearch wäre ein erster Schritt, der nächste wäre ein Upgrade auf C++11 und unordered_set.

warum wird strlen(suchbegriff) nur einmal berechnet?
das ist doch ein vorteil. es ändert sich nur der listenbegriff.

zu den algorithmen: danke für den vorschlag, aber ich will die sache nicht maximal kompilizieren. für den anfang brauch ich das nciht.

tntnet

Also wenn Du Dir Gedanken um die Komplexität machst, dann ist der Geschwindigkeitsunterschied zwischen strlen und strcmp völlig unbedeutend. Überhaupt ist der Unterschied verschwindend gering.

Wenn Du 2 Strings vergleichen willst ist natürlich strcmp schneller als strlen. Aber wenn Du Dir wirklich Gedanken um die Geschwindigkeit machst, dann brauchst Du bessere Algorithmen. Das bedeutet entweder mehr Komplexität oder die Verwendung von C++, dessen Standarbibliothek komplexe Algorithmen hinter einem einfachen Interface verbirgt. Und das gilt nicht erst seit C++11.

Ich bekommen in letzter Zeit hier immer öfters den Eindruck, als wäre C++ vor C++11 unbrauchbar gewesen. Sicher ist C++11 ein Fortschritt, aber davor was C++ auch schon sehr gut.

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

c nicht c++ schrieb:

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

lol c ist doch völlig veraltet!!

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.