3 ms·
(OP here.) You're correct that for short patterns there's little advantage over the brute-force algorithm, and in fact the brute-force algorithm should actually
by jo3_l 21d ago
(OP here.) You're correct that for short patterns there's little advantage over the brute-force algorithm, and in fact the brute-force algorithm should actually be faster in many cases. Indeed the per-iteration comparison against the pattern in the brute-force algorithm is essentially a memcmp, which is vectorized and runs very fast on modern hardware. Consequently all mainstream programming languages that I know of just use the brute-force algorithm as a fallback when the pattern is short, as opposed to something more complicated like bitap.
I tried to be fairly careful to not overstate the performance benefits in the original post for this reason.
- jqpabc123 21d agoOk, so why not use a fast memcmp on the first 4-8 chars of the pattern to identify any potential match and once found, work from there to verify if a full match exists? This is essentially what I have have been doing for years and it is very simple. I'm sure it is not always the fastest but it's not too shabby either in the real world.
- MattPalmer1086 21d agoProbably very effective for shorter patterns. Two reasons to use more complex algorithms for longer patterns: 1. Linearity - the naive approach is quadratic on worst case data (imagine searching for 100 0's in a text of 0's). 2. Sublinearity - sublinear search algorithms skip over text that cannot match. They typically have the somewhat counter-intuitive property that they get much faster the longer the pattern is. So long patterns will be faster using a sub linear search algorithm.
- jqpabc123 21d agoYes but longer patterns are kind of an outlier. Most of the everyday searching and parsing that I end up doing involves relatively short patterns. Maybe I am an outlier :-)