Warum delphi lahmer als c++?

[alzaimar]

Zitat von Olli:

Zitat von alzaimar:

Gegenbeispiel:
Boyer-Moore Pattern Matching (ca. 30 Zeilen) vs. naives Suchen (3 Zeilen)... Boyer-Moore ist viel viel schneller.

Wie funzt denn "naives Suchen" nach alzaimar in 3 Zeilen?

Z.B. so (Suche die 'Needle' im 'Haystack'):

Delphi-Quellcode:

For i:=1 to length (Haystack)-Length(Needle)+1 do
  For j:=1 to Length (Needle) do
    If Haystack[i+j-1] = Needle[j] Then 
      Found := True;

Entschuldigung, sind 4 Zeilen. In C, Fortran, ASM etc. ist der Code nicht wesentlich komplexer.

"Naives Suchen" (oder Brute Force) ist eine gängige Bezeichung für dieses Verfahren. Ein Weiteres nennt sich übrigens "Not so naive".

Hier z.B. ein Pattern-Matching ("Reverse-Factor") der einem die Kinnlade runterklappen lässt , die Implementierung einer Graph-Klasse ist noch nichtmal dabei)... Aber schnell ist er trotzdem:
(Aus "Charras & Lecroq, Exact String Matching Algorithms")

Code:

void buildSuffixAutomaton(char *x, int m, Graph aut) {
   int i, art, init, last, p, q, r;
   char c;
  
   init = getInitial(aut);
   art = newVertex(aut);
   setSuffixLink(aut, init, art);
   last = init;
   for (i = 0; i < m; ++i) {
      c = x[i];
      p = last;
      q = newVertex(aut);
      setLength(aut, q, getLength(aut, p) + 1);
      setPosition(aut, q, getPosition(aut, p) + 1);
      while (p != init &&
             getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, p, c, q);
         setShift(aut, p, c, getPosition(aut, q) -
                             getPosition(aut, p) - 1);
         p = getSuffixLink(aut, p);
      }
      if (getTarget(aut, p, c) == UNDEFINED) {
         setTarget(aut, init, c, q);
         setShift(aut, init, c,
                  getPosition(aut, q) -
                  getPosition(aut, init) - 1);
         setSuffixLink(aut, q, init);
      }
      else
         if (getLength(aut, p) + 1 ==
             getLength(aut, getTarget(aut, p, c)))
            setSuffixLink(aut, q, getTarget(aut, p, c));
         else {
            r = newVertex(aut);
            copyVertex(aut, r, getTarget(aut, p, c));
            setLength(aut, r, getLength(aut, p) + 1);
            setSuffixLink(aut, getTarget(aut, p, c), r);
            setSuffixLink(aut, q, r);
            while (p != art &&
                   getLength(aut, getTarget(aut, p, c)) >=
                   getLength(aut, r)) {
               setShift(aut, p, c,
                        getPosition(aut,
                                    getTarget(aut, p, c)) -
                        getPosition(aut, p) - 1);
               setTarget(aut, p, c, r);
               p = getSuffixLink(aut, p);
            }
         }
      last = q;
   }
   setTerminal(aut, last);
   while (last != init) {
      last = getSuffixLink(aut, last);
      setTerminal(aut, last);
   }
}


char *reverse(char *x, int m) {
   char *xR;
   int i;
 
   xR = (char *)malloc((m + 1)*sizeof(char));
   for (i = 0; i < m; ++i)
      xR[i] = x[m - 1 - i];
   xR[m] = '\0';
   return(xR);
}
 
 
int RF(char *x, int m, char *y, int n) {
   int i, j, shift, period, init, state;
   Graph aut;
   char *xR;
 
   /* Preprocessing */
   aut = newSuffixAutomaton(2*(m + 2), 2*(m + 2)*ASIZE);
   xR = reverse(x, m);
   buildSuffixAutomaton(xR, m, aut);
   init = getInitial(aut);
   period = m;
 
   /* Searching */
   j = 0;
   while (j <= n - m) {
      i = m - 1;
      state = init;
      shift = m;
      while (i + j >= 0 &&
             getTarget(aut, state, y[i + j]) !=
             UNDEFINED) {
         state = getTarget(aut, state, y[i + j]);
         if (isTerminal(aut, state)) {
            period = shift;
            shift = i;
         }
         --i;
      }
      if (i < 0) {
         OUTPUT(j);
         shift = period;
      }
      j += shift;
   }
}

Ich habe tatsächlich überlesen, das Du Schleifen explizit ausklammerst...

Egal: Natürlich benötigen 10000 Op-codes i.R. länger als 3