6 ms·
Ok, 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
by jqpabc123 5d ago
Ok, 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 5d 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 4d 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 :-)