Standard-Implementierung ?

[gugelhupf]

Ich hab mich mal daran versucht eine String-Suche rekursiv zu implementieren.

Was mich nun interessieren würde ist, ob die Funktion nahe an einer (falls es sowas gibt) Standard-Implementation rankommt.

Desweiteren würde ich gern wissen, ob man ohne die Variable index auskommt, die ja nur Function Overhead produziert.

#include <stdio.h>

/* Variables */

char* pszTemplateStr="eHallHAlHallxokdjnesdlkjfklsdjflkjdjfkexoeexexeonexontee";

/* Functions */

int FindStr(const char* pszToFindStr,const char* pszSourceStr)

{

static int index=0;

if(*(pszSourceStr+index)=='\0')

return 0;

if(*(pszToFindStr+index)==*(pszSourceStr+index))

{

if(*(pszToFindStr+index+1)=='\0')

return 1; // String gefunden !

else

{

index++;

return FindStr(pszToFindStr,pszSourceStr); // auf nächste Übereinstimmung suchen

}

}

else

{

index=0;

return FindStr(pszToFindStr,pszSourceStr+1);

}

}

int main()

{

char* test="teer";

if(FindStr(test,pszTemplateStr))

printf("%s gefunden !",test);

else

printf("%s nicht gefunden !",test);

return 0;

}

[gajUli]

Hi gugel,

Standardkonformitaet scheint mir fuer C und C++ gegeben. Die Indexvariable ist wohl auch kein Problem, weil sie static ist, also eigentlich ausserhalb der Funktion lebt.

Aber die Funktion ist suboptimal, weil die Rekursion sich immer und immer wieder mit den selben Parametern aufruft, was den Stack belastet. Im Grunde bedeutet das Speicherverbrauch fuer nichts.

Fazit: Wenn man an eine Rekursivfunktion immer nur die gleichen Parameter weiterreicht, faehrt man mit einer Schleife wahrscheinlich besser.

Danke fuer das Beispiel, mir war dieses Indiz bis jetzt eben selber nicht so deutlich klar.

[gugelhupf]

Das war das Problem, dass wenn man die Zeiger auf die Strings inkrementiert rekursiv übergibt, dass man sie nicht ohne weiteres wieder zurückstellen kann. Beispiel:

Template="HalHHallo";

ToFind="Hallo";

Die Funktion findet nun "Hal" , aber dann muss sie abbrechen. Bei veränderter Parameterübergabe muss man nun die Zeiger wieder "zurückstellen" auf den Ausgangswert. Habe mir gestern den Kopf zerbrochen wie man das ohne eine Hilfsvariable zustande bekommt, aber keine Lösung gefunden !

Insofern gebe ich Dir recht, dass man dies wohl eher Iterativ implementieren sollte. Die meisten Rekursionen übergeben ja auch veränderte Parameter was einfachen Jumps und veränderten Registern entspricht.

Und genau wegen der Variable index macht mir die Funktion auch Sorgen...->deswegen die Frage nach dem Standard

[Crush]

Rekursion dient vor allem der klareren Strukturierung von Programmen - das haben wir glaub einigermaßen einstimmig festgestellt.

Ich finde auch, daß eine normale Schleife für solche Suchfunktionen sinnvoller ist. Schau mal nach dem Thema Radix-Sort, da habe ich (vielleicht etwas schlecht) erklärt, wie man Suchfunktionen mit Tabellen ruckzuck aufbauen kann und so mit ein paar wenigen Zugriffen praktisch auf anhieb gleiche Zeichenketten finden kann.

Aber egal was man programmiert, diese String-Funktionen werden wohl von den meisten Compilern nicht ausreichend Assembler-optimiert, weil es da sogar eine große Palette an Stringfunktionen im Prozessor (CMPS String, String vergleicht z.B. einfach die beiden Strings ohne irgendwelche Hilfsvariablen!!!) schon vorbereitet gibt.

Wenn irgendein Compiler mal in der Lage sein sollte sowas gescheit zu optimieren, dann muß natürlich auch der Source entsprechend aufgebaut sein, d.h. in diesem Fall: Eine Schleifenkonstruktion ist besser. (REP ist für Schleifendurchläufe bei Strings in Asm konzipiert und der braucht dann auch keine Variablen, sondern dem reichen die Prozessor-Flags schon aus).

Schon aus Geschwindigkeitsgründen ist eine stinknormale Schleifenkonstruktion ohne Suchtabellen Standard.

Der rekursive Suchansatz ist der Übersichtlichkeit im Source auf jeden Fall nicht gerade dienlich.

[gajUli]

Crush,

eine Sache versteh ich nicht. Am Anfang schreibst Du, Rekursion wuerde den Code besser strukturieren, am Ende das Gegenteil. Was denn jetzt?

Zur Stringsuche durch Maschinencode ist mir nicht klar, warum der nennenswert schneller sein soll. Das langsame ist doch immer der Speicherzugriff, der immer passieren muss. Ich wage auch bezweifeln, dass RISC-Architekturen sich mit solchen Assemblerfunktionen um ihren guten Ruf bringen moechten.

[Crush]

Hab´mich vielleicht mal wieder etwas ungeschickt ausgedrückt: Ausgerechnet in diesem Sourcecode ist die Rekursion der Übersicht nicht dienlich - in anderen Fällen aber ausgesprochen!!! Das hängt auch sicherlich vom Verwendungszweck ab - eine Schleife wäre hier auf jeden Fall übersichtlicher.

Der Schleifencode für einen kompletten String-Vergleich benötigt in Assembler genau: Einen Befehl, darauf wird nur noch lesend auf die String-Inhalte zugegriffen ohne weitere Variablen ansprechen zu müssen - die Zeiger-Vergleiche im Code oben erzeugen mit der Rekursion (=Stackbelastung), den Hilfsvariablen und der Index-Addition, etc. einen zigfach größeren und zeitintensiveren Code. Gerade in solch einem Beispiel ist der Geschwindigkeitsvorteil von richtigem Assembler-Einsatz extrem viel größer als das was bei C++ rauskommt.

Eigentlich erzeugen die Compiler ja Assembler-Code und dieser wird dann on-the-fly vom eingebauten MASM übersetzt (weshalb Inline-ASM-Code kein Problem ist), soweit ich das mitbekommen habe - und hier ist das Problem: Der Assembler-Code ist einfach gerade im String-Bereich nicht genug optimiert! Du hast ja selber mitbekommen was für einen Mist die teilweise machen, daß selbst Inline-Funktionen noch als Calls eingebaut werden, was absolut überflüssig ist - was soll daran inline sein?

Mich wundert es nicht, daß mit MingW übersetzte C++-Programme im Durchschnitt mindestens 25-30% schneller laufen als Studio - der optimiert halt wesentlich besser.

[hoagi]

Ich denke auch ,das hier die Verwendung eines sich selbst aufrufenden Programs nicht Sinnvoll ist.

Aber im Gegensatz zum Vorpostern denke ich ncht das hier der Knackpunkt die Tatsache ist, das immer der gleiche Parameter übergeben wird, sondern , das durch Verwendung der statischen Variable der Stack der Funktion überhaupt nicht genutzt wird.

Letztendlich entscheidet sich die Frage ob ein iteratives oder rekursives Problem vorliegt daran ob zur Abarbeitung ein Stackstruktur ( last in first out ) benötigt wird.

( vielleicht ein wenig verkürzt dargestellt )

Und tatsächlich kann es durchaus rekursive Funktionen geben bei denen gar keine Parameter übergeben werden.

Zwar sind auch Variblen, die ich einer Fuktion übergebe lokale Variablen ( und es ist wirklich ziemlich langweilig immer wieder die gleiche Werte auf den Stack zu sichern , das liese sich hier auch mit globalen Variablen lösen ) aber die Sache greift ein wenig kurz.

Ich denke um sich die Sache klar zu machen wär es hier nicht schlecht sich die Algorithmen anzusehen die benutzt werden um Baumstrukturen in unterschiedlicher Weise zu traversieren.

Hier gibt es nämlich solche die ein Stackstruktur erfordern ( also rekursiv zu lösen sind ) und solche die eine Warteschlangenstruktur erfordern und bei denen sich selbst aufrufende Funktionen nur mit erhöhtem Programmieraufwand einsetzen lassen.

Hoagi

[gugelhupf]

Da fällt mir auf, dass es bestimmt Interesse an einem Assemblerforum geben könnte. Es muss ja kein speziell eigenes sein, sondern könnte ja im IDE-Compiler untergebracht sein....

Das nur mal so am Rande