strstr - naiver algorithmus?
-
hallo,
welcher algorithmus steckt hinter strstr? ist das ein sogenannter einfacher/naiver, oder steckt ein höherwertiger dahinter?
-
Das kommt wohl auf die Implementierung der Standard-Bibliothek an. Evtl. gibt der Standard eine gewisse Laufzeit vor, das kann ich mir aber nicht vorstellen.
MfG SideWinder
-
VS 2008 implementiert es offenbar naiv.
MfG SideWinder
-
weiß nicht ob ich jetzt das richtige snippet erwischt hab die datei .../arch/x86/lib/strstr_32.c hält folgendes bereit...
denke das größte problem das strstr() hat ist das es ja mit festem speicher arbeiten muß, und fast alle "höheren" algos müßen ja eine vorberechnung bzw. sprung tabelle erstellen und bräuchten dafür malloc oder einen weiteren parameter? aber nicht auf jedem system gibts malloc() aber auf jedem gibt es strstr()
das ist meine erklärung wieso strstr() naiv implementiert ist...
und ein punkt wo java wieder bischen zeit gut machen kann
#include <linux/string.h> char *strstr(const char *cs, const char *ct) { int d0, d1; register char *__res; __asm__ __volatile__( "movl %6,%%edi\n\t" "repne\n\t" "scasb\n\t" "notl %%ecx\n\t" "decl %%ecx\n\t" /* NOTE! This also sets Z if searchstring='' */ "movl %%ecx,%%edx\n" "1:\tmovl %6,%%edi\n\t" "movl %%esi,%%eax\n\t" "movl %%edx,%%ecx\n\t" "repe\n\t" "cmpsb\n\t" "je 2f\n\t" /* also works for empty string, see above */ "xchgl %%eax,%%esi\n\t" "incl %%esi\n\t" "cmpb $0,-1(%%eax)\n\t" "jne 1b\n\t" "xorl %%eax,%%eax\n\t" "2:" : "=a" (__res), "=&c" (d0), "=&S" (d1) : "0" (0), "1" (0xffffffff), "2" (cs), "g" (ct) : "dx", "di"); return __res; }schaut spontan auch nach einem naiven aus
lg lolo
-
http://google.com/codesearch?q=strstr+lang%3Ac+libc&hl=en&btnG=Search+Code
zB in der libc von android/openBSD scheint es recht naiv implementiert zu sein
http://google.com/codesearch/p?hl=en#XAzRy8oK4zA/libc/string/strstr.c&q=strstr lang:c libc&sa=N&cd=2&ct=rc
in einer älteren glibc version dagegen ein bisschen aufwendiger und angeblich ziemlich schnell
http://google.com/codesearch/p?hl=en#5ge3gHPB4K4/gnu/glibc/glibc-2.2.4.tar.gz|FX0JnlXCtGc/glibc-2.2.4/sysdeps/generic/strstr.c&q=strstr lang:c libc package:"http://ftp.gnu.org/gnu/glibc/glibc-2.2.4.tar.gz"
-
^^ 'naiv' ist das einfachste und wohl auch ausreichend für die meisten fälle, in denen 'strstr' benutzt wird. schnellere suchalgos lohnen sich ja erst bei richtig langen strings.
