By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,292 Members | 1,354 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,292 IT Pros & Developers. It's quick & easy.

Fast sorting algorithm

P: n/a
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
Nov 17 '05 #1
Share this Question
Share on Google+
2 Replies


P: n/a
Peter Schmitz wrote:
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?


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
Nov 17 '05 #2

P: n/a
Carl Daniel [VC++ MVP] wrote:
Peter Schmitz wrote:
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?


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.


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
Nov 17 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.