AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Thema durchsuchen
Ansicht
Themen-Optionen

Boyer Moore Algorithmus

Ein Thema von Ginko · begonnen am 4. Jun 2013 · letzter Beitrag vom 9. Jun 2013
 
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#34

AW: Boyer Moore Algorithmus

  Alt 9. Jun 2013, 09:10
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
  Mit Zitat antworten Zitat
 


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:40 Uhr.
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-2025 by Thomas Breitkreuz