Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsFree MagazinesWhite PapersSubmit Content
Discussion GroupsASP.NETWindows FormsLanguages.NET FrameworkVisual Studio.NET
Articles.NET FrameworkASP.NETToolsWindows Forms
.NET DirectoryOpen Source ProjectsUser GroupsWeb Resources
Related Topics
Visual Basic 6SQL ServerMS AccessOther DB ProductsMS Server ProductsMore Topics ...

.NET Forum / Languages / Managed C++ / September 2004

Tip: Looking for answers? Try searching our database.

Fast sorting algorithm

Thread view: 
Enable EMail Alerts  Start New Thread
Thread rating: 
Peter Schmitz - 12 Sep 2004 14:21 GMT
Hi again,

I just need to write the following function to search in a binary buffer for
a given pattern:

BOOL CheckBufferForPattern(BYTE *buffer,int bufferlen,BYTE *pattern, int
patternlen, BOOL casesensitive).

What's the best/fastest algorithm for a usual buffer size of 1500bytes or
so? Is there any source code available for this?

thanks a lot
Peter
Carl Daniel [VC++ MVP] - 12 Sep 2004 15:42 GMT
> Hi again,
>
[quoted text clipped - 6 lines]
> What's the best/fastest algorithm for a usual buffer size of
> 1500bytes or so? Is there any source code available for this?

1500 bytes is actually a pretty small buffer by today's standards.
Depending on the buffer contents, the length of the pattern, and the number
and length of "false starts" (prefixes of the pattern that appear in the
buffer), any one of several different algorithms might be the best/fastest.

The first-order solution is to use the strstr() library function, but that
will only work if your buffer doesn't contain embedded nulls.

If you really do need a high-end algorithm, do some searching for the
Boyer-Moore algorithm or the Knuth-Morris-Pratt algorithm.  Both are well
described in online resources and source code implementations are available
if you do some hunting.  For the size of your buffer, it's entirely possible
that a brute-force search will be as fast as these fancy algorithms, so you
should code up the brute-force solution (or use strstr) for comparison and
keep whichever gives the best performance on your particular data.

-cd
Carl Daniel [VC++ MVP] - 12 Sep 2004 17:13 GMT
>> Hi again,
>>
[quoted text clipped - 23 lines]
> solution (or use strstr) for comparison and keep whichever gives the
> best performance on your particular data.

And I forgot to mention:  there's always std::find with a suitable
predicate.  That's likely to be a brute-force implementation, but it's
always possible that std::find might have an optimized version that uses
Boyer-Moore or another high-end searching algorithm.

-cd

Free Magazines

Get these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.