Boyer Moore Algorithmus

[Amateurprofi]

Zitat von Horst_:

Hallo,

@Amateurprofi:
Du hat Deine CPU aber noch nicht die Frequenz hochgeschraubt..
Wenn ich nur Test aufrufe, kommt 6684 / 6660 raus->delta = 24
Wenn ich in Test nach der Festlegung auf CPU1 eine rechneintensive Schleife einbaue ~1 Sekunde dann habe 1700/1694-> delta= 6 ( recht genau 3.2/0.8 [Ghz/Ghz]
Hier gibt es auch schon eine Variante mit REPNE SCASB
http://www.delphipraxis.net/51284-te...n-zaehlen.html
Lazarus will es nicht kompilieren und wenn ich EAX und EDX wieder einsetze statt &S und EAX um 1 statt 65536 erhöhe und shr 16 entferne , zählt das Programm bei 100000 Zeilen "Franz jagt..." nur 85 "Taxi" in nur 209 ms statt über 300 ms für alle anderen.

Gruß Horst

Hallo Horst,
Zu "Frequenz hochgeschraubt"
Sorry, aber da sehe ich keinen Zusammenhang.
Ich messe ja nicht Zeit, sondern CPU-Ticks.
Da sollte es doch völlig egal sein, ob die CPU nun 3G-Takte/s macht, oder 1 Takt pro Stunde.
Es sei denn, die Frequenzerhöhung würde bewirken, dass dann die CPU pro Takt mehr Befehle abarbeitet, aber das kann ich mir nicht vorstellen. Sie macht eben bei hoher Frequenz mehr pro Zeiteinheit, jedoch nicht mehr pro Takt.
Wie auch immer, wenn auch geringfügig, ist REPNE SCASB langsamer als das konventionelle Zählen.

Zu "&S"
Versuche es mal ohne das "&", könnte sein, dass es dann verstanden wird.

Zu EAX um 1 statt um $10000 erhöhen.
Ja klar, kommt dann kein richtiges Ergebnis.
Das was Du als 85 x gefunden interpretierst ist nicht die Anzahl gefundener Taxis sondern der Buchstabe "U".

Mit XOR EAX,EAX und dann MOV AL,[ESI] wird das erste Zeichen des zu suchenden Textes in AL gestellt, und die oberen 3 Bytes in EAX genullt. (Ich hätte das XOR EAX,EAX weggelassen und mit MOVZX EAX, [ESI].Byte das gleiche erreicht).

Wenn du nach "Taxi" suchst, steht beim ersten Durchlauf in AL $54 = "T".
Wird dann das erste Mal "Taxi" gefunden, und du erhöhst EAX um 1, dann steht in AL nicht mehr $54 = "T" sondern $55 = "U" und es wird nicht mehr nach "Taxi" sondern nach "Uaxi" gesucht.
Das wird nicht gefunden, also steht am Schluss in EAX $55 = "U" = 85, dass dann als vermeintliche Anzahl Fundstellen zurückgegeben wird.

Ich hätte ohnehin nicht im Hi-Word von EAX gezählt, sondern lieber in EBP gezählt, natürlich am Anfang ein PUSH EBP und am Ende ein POP EBP.
So wie es ist, wird ohne jede Not die maximale Anzahl der Fundstellen auf 65536 limitiert, mit dem unschönen Effekt, dass bei mehr als 65536 Fundstellen 65536 zurückgegeben wird - was zu Fehlinterpretationen führen kann.