ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng)/ProfitPress-MegaCDROM2.B6I/PROG/PASCAL/POSBM.ZIP/POSBM.PAS

Pascal/Delphi Source File | 1989-06-14 | 5.4 KB | 193 lines

{Benchmark program to demonstrate the speed difference
 between the POS() in Turbo Pascal 4 or 5 brute-force
 and the Boyer-Moore method function POSBM()
 Program Author:  Costas Menico (Dr. Dobbs, Jul 89

 And a new function (posCh) added by Toad Hall
 for when you just want to find a single char in a string.

 Courtesy of David Kirschbaum, Toad Hall
 (with a slight tweak to show the elapsed time
  in a more understandable form)
}

PROGRAM Search;

uses  Dos,Crt;

{Link in the POSBM Boyer-Moore function }

{$F+}
{$L POSBM}

FUNCTION posBM(Pat,S : STRING) : BYTE; EXTERNAL;

{and the posCh function}
{$L POSCH}

FUNCTION posCh(Ch : CHAR; S : STRING) : BYTE; EXTERNAL;

{$F-}


VAR
  Pat,S : STRING;
  Ch : CHAR;
  i,j : INTEGER;
  elapsed : WORD;   {TH}

CONST
  LONGLOOP = 2000;
  STARTFLAG = TRUE;
  FINISHFLAG = FALSE;

{Prints benchmark timing information }

PROCEDURE Tick;
  {Wait until the DOS timer has just ticked a new second.
   This kinda insures we don't get any "second" wraparound.
  }
  VAR
    regs : registers;
    thissec : BYTE;
  BEGIN
    regs.ah := $2C;                      {get current time}
    MsDos(regs);
    thissec := regs.dh;                  {remember this second}
    REPEAT
      regs.ah := $2C;                    {get current time}
      MsDos(regs);
    UNTIL regs.dh <> thissec;            {until a new second}
  END;  {of Tick}

PROCEDURE ShowTime(Start : BOOLEAN);
  {v1.1 Rewritten to
      (1) Use Boolean parm to indicate whether Start or Finish time.
      (2) Use local regs.
      (3) Display elapsed time (in decisecs) if Finish.
      (4) Insure we have a "fresh" second before starting.
  }
  VAR  regs : registers;
  BEGIN
    IF Start THEN Tick;                  {wait for a new second}

    regs.ah := $2C;                      {get start time}
    MsDos(regs);
    regs.ax := (regs.dh * 100) + regs.dl;  {seconds*100 + deciseconds}

    IF Start THEN BEGIN
      Write ('Start ... ');
      elapsed := regs.ax;               {remember start}
    END
    ELSE BEGIN
      elapsed := regs.ax - elapsed;     {elapsed time}
      WriteLn('Finished, decisecs: ', elapsed:6);
    END;
  END;  {of ShowTime}


BEGIN  {main}
  ClrScr;

  {Create a random string of length 255}

  Randomize;
  FOR i := 1 TO 255 DO
    S[i] := CHR(Random(255)+1);
  S[0] := CHR(255);

  {Initialize a pattern string with the last five characters
   in the random string as the pattern to search for.
  }
  Pat := Copy(S,251,5);


  {First do a search with the regular POS function}

  Writeln('String Search using Brute-Force Method');

  ShowTime(STARTFLAG);                  {show Start time,
                                         remember current decisecs}

  FOR j := 1 TO LONGLOOP DO
    i := POS(Pat,S);                    {do the search a few times Brute-force}

  ShowTime(FINISHFLAG);                 {get finish time,
                                         display elapsed decisecs}
  Writeln('Pattern found at: ', i);     {show string psn}

  {Now do search with the POSBM() (Boyer-Moore) function}

  Writeln('String Search using Boyer-Moore Method');

  ShowTime(STARTFLAG);                  {show Start time,
                                         remember current decisecs}

  FOR j := 1 TO LONGLOOP DO
    i := posBM(Pat,S);                  {do search a few times Boyer-Moore}

  ShowTime(FINISHFLAG);                 {get finish time,
                                         display elapsed decisecs}

  Writeln('Pattern found at: ', i);     {show string psn}


  {Now to test our posCh function against both the normal
   Pascal POS() and the posBM functions.
  }

  FillChar(S[1],255,'a');
  Ch := 'z';
  S[254] := Ch;
  S[0] := CHR(255);

  {First do a character search with the regular POS function}

  Writeln('Character Search using Brute-Force Method');

  ShowTime(STARTFLAG);                  {show Start time,
                                         remember current decisecs}

  FOR j := 1 TO LONGLOOP DO
    i := POS(Ch,S);                    {do the search a few times Brute-force}

  ShowTime(FINISHFLAG);                 {get finish time,
                                         display elapsed decisecs}
  Writeln('Character found at: ', i);   {show string psn}

  {Now do character search with the POSBM() (Boyer-Moore) function}

  Writeln('Character Search using Boyer-Moore Method');

  ShowTime(STARTFLAG);                  {show Start time,
                                         remember current decisecs}

  FOR j := 1 TO LONGLOOP DO
    i := posBM(Ch,S);                  {do search a few times Boyer-Moore}

  ShowTime(FINISHFLAG);                 {get finish time,
                                         display elapsed decisecs}

  Writeln('Character found at: ', i);     {show string psn}


  {Now do character search with the posCh() function}

  Writeln('Character Search using Toad Hall posCh function');

  ShowTime(STARTFLAG);                  {show Start time,
                                         remember current decisecs}
  FOR j := 1 TO LONGLOOP DO
    i := posCh(Ch,S);                  {do search a few times}

  ShowTime(FINISHFLAG);                 {get finish time,
                                         display elapsed decisecs}

  Writeln('Character found at: ', i);     {show string psn}

  Writeln;
  Writeln('DONE .. PRESS ENTER');
  ReadLn;
END.