Boyer Moore Algorithmus

[Amateurprofi]

Hab ich mal, so wie in #12 von Horst vorgegeben getestet.
Also 'Point Line Square Point Point Triangle Line PointPoint Line Square PointPoint>>'
in einen String mit 1G Zeichen gefüllt, und dann gezählt, wie oft bestimmte Texte darin vorkommen.

"Straight forward, ohne BM etc."

Und das kam raus:

Code:

"Point"      :  88,607,594 Mal gefunden, Zeit :  920 ms
"Line"       :  37,974,684 Mal gefunden, Zeit :  905 ms
"Square"     :  25,316,456 Mal gefunden, Zeit :  967 ms
"Triangle"   :  12,658,228 Mal gefunden, Zeit :  874 ms
"Point Lin"  :  25,316,456 Mal gefunden, Zeit : 1201 ms
"P"          :  88,607,594 Mal gefunden, Zeit :  905 ms
"L"          :  37,974,684 Mal gefunden, Zeit : 1045 ms
"S"          :  25,316,456 Mal gefunden, Zeit :  936 ms
"T"          :  12,658,228 Mal gefunden, Zeit :  842 ms
"i"          : 139,240,506 Mal gefunden, Zeit :  905 ms

Delphi-Quellcode:

PROCEDURE TMain.Test;
const
   T='Point Line Square Point Point Triangle Line PointPoint Line Square PointPoint>>';
   MaxLen=1000000000;
   ST:Array[0..9] of String=('Point','Line','Square','Triangle','Point Lin',
                             'P','L','S','T','i');
var S,SF,SI:string;  I,LS,N,len:integer; PS,PSI:PChar; Tick,Ticks:Cardinal;
begin
   S:=T;
   PS:=PChar(S);
   LS:=Length(S);
   SetLength(SI,MaxLen);
   PSI:=PChar(SI);
   for I:=0 to MaxLen div LS do begin
      Move(PS^,PSI^,LS*SizeOf(Char));
      Inc(PSI,LS);
   end;
   N:=MaxLen Mod LS;
   if N>0 then Move(PS^,PSI^,N*SizeOf(char));
   reResults.Clear;
   for I:=0 to High(ST) do begin
      SF:=ST[i];
      Tick:=GetTickCount;
      N:=CountStr(SF,SI);
      Ticks:=GetTickCount-Tick;
      reResults.Lines.Add('"'+SF+'" : '+IntToStr(N)+' Mal gefunden, Zeit : '+
                          IntToStr(Ticks)+' ms');
   end;
end;

32 Bit Version

Delphi-Quellcode:

FUNCTION CountStr(const SearchFor,SearchIn:string):Integer;
const sz=SizeOf(Char);
asm
               test     eax,eax
               je       @Ret                 // SearchFor leer
               mov      ecx,[eax-4]          // Length(SearchFor)
               push     ebp
               push     ebx
               push     edi
               push     esi
               push     0                    // Anzahl Zeichen
               test     edx,edx
               je       @End                 // SearchIn leer
               mov      ebp,ecx              // Length(SearchFor)
               mov      ebx,[edx-4]          // Length(SearchIn)
               sub      ebx,ecx              // Length(SearchIn)-Length(SearchFor)
               jc       @End                 // SearchFor länger als SearchIn
               lea      esi,[eax+ecx*sz]     // Hinter SearchFor
               lea      edi,[edx+ecx*sz]     // Hinter SearchIn[Length(SearchFor)]
               neg      ecx
               jmp      @Entry
@NextStart:    sub      ebx,1
               jc       @End                 // Alles durchsucht
               add      edi,sz               // Nächste Startposition
@Entry:        mov      edx,ecx              // Count
@CharLoop:     mov      ax,[esi+edx*sz]      // SearchFor[edx]
               cmp      ax,[edi+edx*sz]      // SearchIn[edx]
               jne      @NextStart
@NextChar:     add      edx,1                // Count
               jl       @CharLoop            // nächstes Zeichen prüfen
               add      [esp],1              // Anzahl Fundstellen
               lea      edi,[edi+ebp*sz]     // Um Length(SearchFor) weiter
               sub      ebx,ebp              // Anzahl verfügbarer Zeichen
               jnc      @Entry               // Noch Zeichen da
@End:          pop      eax                  // Anzahl Zeichen
               pop      esi
               pop      edi
               pop      ebx
               pop      ebp
@Ret:
end;

64 Bit-Version

Delphi-Quellcode:

FUNCTION CountStr(const SearchFor,SearchIn:string):Integer;
const sz=SizeOf(Char);
asm
               xor      rax,rax              // Anzahl Zeichen
               test     rcx,rcx
               je       @Ret                 // SearchFor leer
               xor      r8,r8
               mov      r8d,[rcx-4]          // Length(SearchFor)
@Work:         test     rdx,rdx
               je       @Ret                 // SearchIn leer
               mov      r9,r8                // Length(SearchFor)
               xor      r10,r10
               mov      r10d,[rdx-4]         // Length(SearchIn)
               sub      r10,r8               // Length(SearchIn)-Length(SearchFor)
               jc       @Ret                 // SearchFor länger als SearchIn
               push     r12
               lea      r11,[rcx+r8*sz]      // Hinter SearchFor
               lea      r12,[rdx+r8*sz]      // Hinter SearchIn[Length(SearchFor)]
               neg      r8
               jmp      @Entry
@NextStart:    sub      r10,1
               jc       @End                 // Alles durchsucht
               add      r12,sz                // Nächste Startposition
@Entry:        mov      rdx,r8               // Count
@CharLoop:     mov      cx,[r11+rdx*sz]      // SearchFor[rdx]
               cmp      cx,[r12+rdx*sz]      // SearchIn[rdx]
               jne      @NextStart
@NextChar:     add      rdx,1                // Count
               jl       @CharLoop            // nächstes Zeichen prüfen
               add      rax,1                // Anzahl Fundstellen
               lea      r12,[r12+r9*sz]      // Um Length(SearchFor) weiter
               sub      r10,r9               // Anzahl verfügbarer Zeichen
               jnc      @Entry               // Noch Zeichen da
@End:          pop      r12
@Ret:
end;