Delphi-PRAXiS
Seite 5 von 5   « Erste     345   

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   FreePascal (https://www.delphipraxis.net/74-freepascal/)
-   -   Boyer Moore Algorithmus (https://www.delphipraxis.net/175187-boyer-moore-algorithmus.html)

Amateurprofi 9. Jun 2013 04:58

AW: Boyer Moore Algorithmus
 
Zitat:

Zitat von Horst_ (Beitrag 1217881)
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.

Horst_ 9. Jun 2013 10:10

AW: Boyer Moore Algorithmus
 
Hallo,

ich habe mal himitsu's Version geändert, welche bei mir nicht übel abschneidet.

Delphi-Quellcode:
function CountString(const S, SubStr: string): integer; assembler;
// Leicht geändert, zählt nicht nur bis 65536
// Siehe www.delphipraxis.net/51284-teil-string-anderem-string-suchen-zaehlen.html
asm
         PUSH   ESI
         PUSH   EDI
         PUSH   EBX
         TEST   EAX, EAX
         JE     @Exit         // S nicht vorhanden
         TEST   EDX, EDX
         JE     @Exit0         // SubString nicht vorhanden
         MOV    ESI, EDX      // EDI Adresse SubString
         MOV    EDI, EAX      // EDI Adresse S

         MOV    ECX, [EDI - 4] // Laenge S
         MOV    EDX, [ESI - 4] // Laenge SubString
         DEC    EDX           // Restlaenge des Substrings, die untersucht werden muss
         JS     @Exit0         // Substring hatte Laenge = 0

         MOV    AL, [ESI]     // Erstes Zeichen des Substrings nach dem gesucht wird
         INC    ESI           // Startpos fuer dahinter weiter vergleichen
         SUB    ECX, EDX      // Differenz der Laengen
         JLE    @Exit0         // Substring laenger als S -> und tschuesz

         MOV    EBX, ECX
         PUSH   Dword 0        // Anzahl Vorkommen auf dem Stack an [ESP]
         @Loop:
         MOV    ECX, EBX
         REPNE  SCASB         // Suche erste Zeichen
         JNE    @Ready          // Suche abgeschlossen
         MOV    EBX, ECX      // Position merken
         PUSH   ESI            // Merken für den naechsten Such-Durchgang
         PUSH   EDI
         MOV    ECX, EDX      // Die noch zu vergleichende Anzahl
         REPE   CMPSB         // Vergleich des Restes des Substrings ab dort
         POP    EDI
         POP    ESI
         JNE    @Loop
         INC    [ESP]         //erhoehe Anzahl Vorkommen
         JMP    @Loop

         @Exit0:
         MOV    EAX,0
         JMP    @Exit
         @Ready:
         POP    EAX
         @Exit:
         POP    EBX
         POP    EDI
         POP    ESI
end;
Der Suchtext besteht aus 100000 Zeilen.Gesamtlänge 6.2 Mio Zeichen
Code:
"Taxi"
Asm       Count: 100000 in 544ms
BMH Count:       100000 in 321ms
SP Search Count: 100000 in 564ms
Std PosEx Count: 100000 in 340ms
himitsu Count:   100000 in 280ms  <---

" Taxi" // Ein häufiger Buchstabe vorne
Asm       Count: 100000 in 819ms
BMH Count:       100000 in 284ms <---
SP Search Count: 100000 in 544ms
Std PosEx Count: 100000 in 1021ms
himitsu Count:   100000 in 745ms

"XTaxi" // Ein nicht vorhandener Buchstabe vorne
Asm       Count: 0 in 519ms
BMH Count:       0 in 244ms
SP Search Count: 0 in 471ms
Std PosEx Count: 0 in 212ms
himitsu Count:   0 in 210ms       <--

// Die fast längste Zeile #13#10 fehlt
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern."
Asm       Count: 100000 in 396ms <---
BMH Count:       100000 in 534ms
SP Search Count: 100000 in 806ms
Std PosEx Count: 100000 in 453ms
himitsu Count:   100000 in 482ms

//Ein nicht vorhandener Buchstabe am Ende eines langen Textes
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern.X"
Asm       Count: 0 in 1189ms
BMH Count:       0 in 69ms <--- auch nur 89 Mb/s
SP Search Count: 0 in 340ms
Std PosEx Count: 0 in 440ms
himitsu Count:   0 in 484ms
Gruß Horst

Ginko 9. Jun 2013 11:49

AW: Boyer Moore Algorithmus
 
Liste der Anhänge anzeigen (Anzahl: 1)
Moin,
Bei mir sieht das ganz anders aus ?! Ich hab mal noch hier den dazu genommen http://www.delphipraxis.net/711182-post1.html, der schlägt sich bei mir bis jetzt am besten (Alles im Anhang).
Code:
"Taxi"
BMH Count:       100000 in 503ms
SP Search Count: 100000 in 785ms
Asm AmatProf:    100000 in 743ms
QSSearch Count:  100000 in 396ms <---
Asm himitsu:     100000 in 1463ms
Std PosEx Count: 100000 in 1559ms

" Taxi" // Ein häufiger Buchstabe vorne
BMH Count:       100000 in 423ms <--
SP Search Count: 100000 in 752ms
Asm AmatProf:    100000 in 1185ms
QSSearch Count:  100000 in 423ms <--
Asm himitsu:     100000 in 3854ms
Std PosEx Count: 100000 in 3643ms

"XTaxi" // Ein nicht vorhandener Buchstabe vorne
BMH Count:       0 in 409ms
SP Search Count: 0 in 666ms
Asm AmatProf:    0 in 405ms
QSSearch Count:  0 in 305ms <--
Asm himitsu:     0 in 1177ms
Std PosEx Count: 0 in 1178ms

// Die fast längste Zeile #13#10 fehlt
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern."
BMH Count:       100000 in 1191ms
SP Search Count: 100000 in 1343ms
Asm AmatProf:    100000 in 592ms <--
QSSearch Count:  100000 in 601ms
Asm himitsu:     100000 in 2353ms
Std PosEx Count: 100000 in 2031ms

//Ein nicht vorhandener Buchstabe am Ende eines langen Textes
"Franz jagt im komplett verwahrlosten Taxi quer durch Bayern.X"
BMH Count:       0 in 103ms
SP Search Count: 0 in 413ms
Asm AmatProf:    0 in 1276ms
QSSearch Count:  0 in 79ms <--
Asm himitsu:     0 in 2455ms
Std PosEx Count: 0 in 2050ms

//Nur ein Buchstabe
"t"
BMH Count:       400000 in 1989ms
SP Search Count: 400000 in 1987ms
Asm AmatProf:    400000 in 841ms <--
QSSearch Count:  400000 in 1289ms
Asm himitsu:     400000 in 2137ms
Std PosEx Count: 400000 in 2677ms

"Franz jagt im komplett"
BMH Count:       100000 in 667ms
SP Search Count: 100000 in 757ms
Asm AmatProf:    100000 in 739ms
QSSearch Count:  100000 in 339ms <--
Asm himitsu:     100000 in 1753ms
Std PosEx Count: 100000 in 1831ms
50 Durchläufe/Test. Datei 100000 Zeilen.

Furtbichler 9. Jun 2013 12:35

AW: Boyer Moore Algorithmus
 
Zitat:

Zitat von Furtbichler (Beitrag 1217482)
Superduperschnell ist es nicht, aber benötigst du unbedingt BM? Und wenn ja, dann vermutlich besser QuickSearch....

Zitat:

Zitat von Ginko (Beitrag 1217924)
Ich hab mal noch hier den dazu genommen

Sag ich doch.:roll:

Horst_ 9. Jun 2013 12:51

AW: Boyer Moore Algorithmus
 
Hallo,

ich bin erstaunt über die großen Unterschiede zwischen meinem AMD Phenom II X4 955 3.2Ghz
// etwas umgestellt zum besseren Vergleich
//50 Durchläufe
Code:
" Taxi" // Ein häufiger Buchstabe vorne
BMH Count:      100000 in 284ms <--- 1091 Mb/s
SP Search Count: 100000 in 544ms
Asm AmatProfi : 100000 in 819ms
himitsu Count:  100000 in 745ms
Std PosEx Count: 100000 in 1021ms
und der unbekannten CPU von Ginko:
Code:
" Taxi" // Ein häufiger Buchstabe vorne
BMH Count:      100000 in 423ms <---  733 Mb/s
SP Search Count: 100000 in 752ms
Asm AmatProf:   100000 in 1185ms
QSSearch Count: 100000 in 423ms <--
Asm himitsu:    100000 in 3854ms
Std PosEx Count: 100000 in 3643ms
Da liegen ja Welten bei BMH /Std PosEx zwischen bei mir 284/1021=0,278 und bei Ginko 423/3643 = 0,116.
Auch BMH/asm himitsu/ ist ja völlig anders:
Bei mir 284/745 = 0,381 gegenüber 284/3854 = 0,0737 ( völlig induskutabel nur 7% von BMH)
Zumal dabei Amateruprofis Version mehr als 3 mal schneller, während es bei mir langsamer ist.
Da beide Sachen in Assembler sind, wird ein der Code identisch umgesetzt, egal welcher Compiler dort am Werk ist.
Ich bin sehr erstaunt über die Größe des Unterschiedes.
Zur Geschwindigkeit an sich, das dort 310 Mb (6.2e6*50) in 69/109 ms abgeklappert werden habe ich vorhin unterschlagen.
Statt 89 Mb/s sind 50*89 = 4.45 Gb/s

Gruß Horst

Ginko 9. Jun 2013 14:29

AW: Boyer Moore Algorithmus
 
Das gute abschneiden der Standard PosEx Funktion bei dir wundert mich schon sehr.
Also bei Post 42.

Meine Daten zum Test:
CPU Typ DualCore Intel Core 2 Duo E6400, 1600 MHz (6 x 267) (StandardMax 2400 Mhz, auf 1600 festgelegt über Energieoptionen)
2 GB Speicher
Win 7 32Bit
Lazarus 1.0.8

@Furtbichler ich hatte auch schon mal einen QS nach Sunday drinnen, der hat aber nicht gut abgeschnitten (deshalb hatte ich ihn auch wieder rausgemacht), die Verbesserung von alzaimar machen scheinbar viel aus.

Horst_ 9. Jun 2013 15:10

AW: Boyer Moore Algorithmus
 
Hallo,

ich habe die tatsächlich die selben Bedingungen.Ob 4 oder 2 Gb Speicher ist ja hier wohl nicht relevant.
Es könnte daran liegen, das diese AMD CPU 6 MB Level III Cache hat, aber dies kann nicht soviel ausmachen, schließlich durchsuchst Du in 103 ms einen nicht vorhandenen String und ich brauche 69 ms, bei doppelter CPU-frequenz.
Müßig darüber nachzudenken, Du hast ja noch etwas schnelleres gefunden.

Gruß Horst
P.S.
Heute morgen bei mir mal http://www.delphipraxis.net/attachme...tring_test.zip getestet, aber die Funktion an eine CPU gekettet.
Das bringt aber fast nichts, die Messwerte schwanken etwas weniger.Ich klicke 4..5 mal schnell auf die Start Test Schaltfläche und nehme die letzte Ausgabe.

Delphi-Quellcode:
procedure TForm1.Button2Click(Sender: TObject); //Test starten
var
  Filestream: TFileStream;
  SuchWort, SuchText: string;
  i, Ergebnis, Durchlaeufe: integer;

  samask, pamask, tamask: NativeUInt;
begin
    // Thread auf 1 CPU fixieren
  GetProcessAffinityMask(GetCurrentProcess, pamask, samask);
  if pamask = 0 then
    exit;
  tamask := 1;
  while tamask and pamask = 0 do
    tamask := tamask shl 1;
  SetThreadAffinityMask(GetCurrentThread, tamask);
..
Ausgabe:
Code:
"Taxi"
BMH Count:        100000 in 313ms
SP Search Count: 100000 in 549ms
Asm AmatProf:   100000 in 444ms
QSSearch Count: 100000 in 280ms
Asm himitsu:      100000 in 273ms
Std PosEx Count: 100000 in 329ms

" Taxi"
BMH Count:        100000 in 275ms
SP Search Count: 100000 in 524ms
Asm AmatProf:   100000 in 638ms
QSSearch Count: 100000 in 248ms
Asm himitsu:      100000 in 729ms
Std PosEx Count: 100000 in 1000ms

zuvor , man sieht Asm Count= Asm Amateur Profi jetzt 20% schneller ist, wie kann das sein, der selbst Code, der selbe Compiler (Laz 1.08/FPC 2.6.2) ?

//" Taxi" // Ein häufiger Buchstabe vorne
//Asm      Count: 100000 in 819ms
// BMH Count:      100000 in 284ms <---
// SP Search Count: 100000 in 544ms
// Std PosEx Count: 100000 in 1021ms
// himitsu Count:  100000 in 745ms


Alle Zeitangaben in WEZ +1. Es ist jetzt 02:16 Uhr.
Seite 5 von 5   « Erste     345   

Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz