Boyer-Moore für Unicode

[mkinzler]

Ein Versuch wäre bei dir ja, wie man sieht, eh sinnlos.

[Schorschi5566]

Bin guten Argumenten gegenüber immer aufgeschlossen.

Aber vorhandenen, funktionierenden Code der schönen Struktur wegen zu verlangsamen oder unnötig auszuweiten, widerstrebt mir.

[jbg]

Hast du die Warnungen des Compiler deaktiviert? Denn "i" ist nach der Schleife undefiniert. Und nur weil der aktuelle Compiler hier die Schleife nicht optimiert, funktioniert das. Zukünfige Compiler könnten da aber schon mal Hand ansetzen. Eine C-for-Schleife muss nicht immer unbedingt in eine Pascal-for-Schleife umgewandelt werden.

Hast du auch die $STRINGCHECKS deaktiviert? Denn die fressen die Performance auf. Da ist dein "ein JMP gespart" belanglos, was es ohnehin dank Jump-Optimierung seitens Delphi bereits ist. Delphi erkennt, dass du mit "break" auf ein "goto" springst, und leitet den Sprung direkt weiter ohne den Zwischenstopp. (Einfach mal den Assemblercode im CPU-View anschauen).

Zudem könnte man die Subtraktion aus der inneren Schleife nehmen, indem man auf zwei PChar umstellt und beide mit Dec() rückwärts laufen lässt ("- k"). Und wenn man schon dabei ist, kann man auch gleich noch die if-Abfrage in der inneren Schleife entfernen und dafür die for-Schleifen-Grenze anpassen.
Außerdem kann man sich den j=0 Durchlauf sparen, da dort für all i (und k) überhaupt nichts geschieht, außer ein vollständiger unnötiger i-Durchlauf.

[jbg]

Du kannst auch noch einen Speicherzugriff einsparen, wenn du das FBadTable dynamische Array direkt als "array[0..65535] of Integer" deklarierst. Da entfällt eine Speicher-Indirektion und du brauchst keinen eigenen Konstruktor mehr.

[Deep-Sea]

Zitat von Schorschi5566:

Delphi-Quellcode:

[...]
            if (Pattern[iPLen - k + 1] <> Pattern[i - k + 1]) then
              Goto NextTryFwd;
          end;
          Goto MatchedFwd;
NextTryFwd:
        end;
MatchedFwd:
        FGoodTable[j] := iPLen - i;
      end;
    end
[...]

Kommt mir bekannt vor:

Code:

[...]
                if (p[plen - k] != p[i - k]) {
                    goto nexttry;
                }
            }
            goto matched;
nexttry:
            ;
        }
matched:
        next[j] = plen - i;
    }
[...]

Quelle: Wikipedia

[Schorschi5566]

@Deep-Sea:

Zitat von Schorschi5566:

Aber ich will mich nicht mit fremden Federn schmücken. Der Teil ist aus den einschlägigen Beispielen für Boyer-Moore entnommen und von mir lediglich an Delphi und die Rückwärtssuche angepaßt worden.

@jbg:

Zitat:

Da ist dein "ein JMP gespart" belanglos, was es ohnehin dank Jump-Optimierung seitens Delphi bereits ist. Delphi erkennt, dass du mit "break" auf ein "goto" springst, und leitet den Sprung direkt weiter ohne den Zwischenstopp. (Einfach mal den Assemblercode im CPU-View anschauen).

Danke, das war mir neu.

@all:
Ich hab mal den "goto-verseuchten" Teil umgeschrieben.

Delphi-Quellcode:

      // Good-Suffix-Table vorwärts
      FGoodTable[0] := 1;
      j := 1;
      i := iPLen - 1;
      k := 0;
      bMatch := False;
      while j < iPLen  do
      begin
        while (i > 0) and (k <> j) do
        begin
          while (k < j) and (i - k > 0) and (Pattern[iPLen - k] = Pattern[i - k]) do
          begin
            bMatch := True;
            inc(k);
          end;
          if (k < j) then // kein ganzes Suffix gefunden
          begin
            if i-k <= 0 then
              i := 0 // Maximal-Skip
            else
            begin
              if bMatch then  // kein Match mit dieser Länge...weitersuchen
              begin
                k := 0; // wieder von vorn
                bMatch := False;
              end;
              Dec(i);
            end;
          end;
        end;
        FGoodTable[j] := iPLen - i;
        inc(j);
      end;

[himitsu]

goto NextStep; => Continue (das Gegenstück zum Break)

Ansonsten ist diese Schleife, mit dem exit am ende vollkommen vermurkst, wenn das Exit immer die Schleife beendet, ist das schonmal ein guter Hinweis, daß da was nicht stimmt.
Aber wurde ja nun schon umgeschrieben.

PS: Mit goto kann man auch rückwärts springen, was dann das Exit-while-Goto durch ein goto ersetzt hätte.

[Schorschi5566]

Hallo Himitsu,

da hast du aber übersehen, dass Goto Nextstep an das Ende der äußeren Schleife springt, oder?

[Deep-Sea]

Zitat von himitsu:

[...] wenn das Exit immer die Schleife beendet, ist das schonmal ein guter Hinweis, daß da was nicht stimmt.

Naja, bei einer Suche ist das aber fast die Regel
Beispiel:

Delphi-Quellcode:

function FindeEtwas(const AName: String): String;
var
  I: Integer;
begin
  For I := 0 to EineListe.Count - 1 do
  begin
    If EineListe[I].Name = AName then Exit(EineListe[I].Wert);
  end;
  Result := '< Nicht gefunden >';
end;

Wenn ich nicht mit Exit gehen dürfte, müsste ich das "Nicht gefunden" ggf. sinnlos am Anfang zuweisen und dann bei Erfolg einen Block aufmachen und einmal Result zuweisen und Break aufrufen. Imho komplizierter - zumindest seit es das verbesserte Exit gibt *es liebe*

[himitsu]

Das IF liegt aber nicht direkt in der Schleife, sondern in dem IF.

Delphi-Quellcode:

For I := 0 to EineListe.Count - 1 do
begin
  ...
  Exit(...);
end;

Und was sagst du dazu?

PS: Sowas ist oben in den beiden drei verschachtelten Schleifen auch drin, die Mittlere wird niemals durchlaufen, da sie anscheinend (falls ich das richtig seh) immer gleich im ersten Durchgang abgebrochen wird.