www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - Boyer Moore template

reply Derek Parnell <derek psych.ward> writes:
In you are interested, here is a template implementation of the Boyer-Moore
Fast Find algorithm. It can find substrings in text much faster than a
plain scan.

http://svn.dsource.org/svn/projects/build/trunk/Source/util/BMscanner.d

You can delete the line "private import util.bmscanner_bn;" if you aren't
interested in the Build utility's automatic build numbering facility. And
you might have to change the module's package name to suit your own
directory structure.

-- 
Derek Parnell
Melbourne, Australia
http://www.dsource.org/projects/build/ v1.19 released 04/Apr/2005
http://www.prowiki.org/wiki4d/wiki.cgi?FrontPage
6/04/2005 5:11:50 PM
Apr 06 2005
parent Norbert Nemec <Norbert Nemec-online.de> writes:
Nice work! Would be interesting to check under which conditions this 
algorithm is faster than plain scan. For short strings, the overhead 
will probably outweigh the speedup. (Especially considering that 
searching one fixed byte in a block of data can be done very efficiently 
in assembler.)

Would certainly be interesting to do some benchmarking.

Derek Parnell schrieb:
 In you are interested, here is a template implementation of the Boyer-Moore
 Fast Find algorithm. It can find substrings in text much faster than a
 plain scan.
 
 http://svn.dsource.org/svn/projects/build/trunk/Source/util/BMscanner.d
 
 You can delete the line "private import util.bmscanner_bn;" if you aren't
 interested in the Build utility's automatic build numbering facility. And
 you might have to change the module's package name to suit your own
 directory structure.
 

Apr 07 2005