Boyer-Moore für Unicode

[Schorschi5566]

Hehe, ich hab's doch gewußt. Na ein Verkünder der "einzigen, reinen Wahrheit", meldet sich halt immer zu Wort. Hat ja oft schon religiöse Züge. Und viele der Verkünder verwenden hemmungslos Break, Exit und try-except-Blöcke (am besten über drei Bildschirmhöhen hinweg).

Zitat:

Habs gerade nochmal angeschaut (echt gruselig), macht vermutlich aber doch das, was du haben möchtest (leider!, macht es das)

Wieso leider und gruselig? Effizient, würde ich sagen. 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. (Da war doch noch ein dummes "break" drin, das auf ein Goto gesprungen ist, was logischerweise 2 Jumps bedeutet, wo nur einer nötig ist und wurde prompt von mir durch ein Goto ersetzt. )

Zitat:

weil Goto nunmal unstrukturiert ist

Strukturier's halt ohne Gotos, wenn dir das mit der gleichen Performance und in zehn Zeilen gelingt. Viel Spaß.

Ich bin auch gegen Gotos (aber ich erzähl's nicht jedem bei jeder Gelegenheit) und musste erstmal nachsehen, wie das in Delphi überhaupt geht aber wohl dosiert und wenn es sinnvoll ist habe ich kein Problem dieses Sprachelement einzusetzen.

Im Übrigen gibt es diese Diskussion hier doch schon mehrfach und du musst niemanden bekehren.

[omata]

Zitat von Schorschi5566:

Im Übrigen gibt es diese Diskussion hier doch schon mehrfach und du musst niemanden bekehren.

Tue ich auch nicht. Entschuldigung, dass ich was gesagt habe. ich bereue es schon.

[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.

[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.