Fast sorting algorithm

[Peter Schmitz]

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]]

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

[Carl Daniel [VC++ MVP]]

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