> "Even long-winded users won't write Moby Dick into your <textarea>"
Which has most cases already much longer than those where the setup costs of BM are larger than the gain if the match is found on average halfway in to the text.
Typically you hit that point when the 'haystack' is about 2,000 characters and the 'needle' is longer than about 4 to 5, longer 'needles' or longer 'haystacks' would increase the advantage.
So the HTTP header one is probably one situation where you'd be quicker using brute force but in those other two instances it is very well possible that BM is already faster.
This assumes that you are going to the trouble of initializing your skip table once and re-using it. Now you have state to maintain beyond the life of the function call, or else your performance is slower than brute-force. That, in addition to probably needing to write the function in the first place, means you've got all sorts of bugs to find and fix.
And anyway, what are you doing searching HTTP headers in anything more than a one-off script? More likely, you are parsing the whole header and sticking it in a hash table. So, not only aren't you searching, but even if you were, that's not the hard part. And even that is dwarfed by the application that's going to service the HTTP request. (Unless you are Google, in which case you don't need my advice.)
Searching HTTP headers is not your bottleneck. Use your language's built in string search. Premature optimization makes code slower.
Comments
His next line was "But most of us aren't searching Moby Dick, but rather a HTTP header, some user input, or a paragraph of a document."
A HTTP header is several orders of magnitude shorter than Moby Dick.
Followed by:
> "Even long-winded users won't write Moby Dick into your <textarea>"
Which has most cases already much longer than those where the setup costs of BM are larger than the gain if the match is found on average halfway in to the text.
Typically you hit that point when the 'haystack' is about 2,000 characters and the 'needle' is longer than about 4 to 5, longer 'needles' or longer 'haystacks' would increase the advantage.
So the HTTP header one is probably one situation where you'd be quicker using brute force but in those other two instances it is very well possible that BM is already faster.
The chances of analyzing just one HTTP header in an application are almost nil. Use a boyer-moore skip table.
This assumes that you are going to the trouble of initializing your skip table once and re-using it. Now you have state to maintain beyond the life of the function call, or else your performance is slower than brute-force. That, in addition to probably needing to write the function in the first place, means you've got all sorts of bugs to find and fix.
And anyway, what are you doing searching HTTP headers in anything more than a one-off script? More likely, you are parsing the whole header and sticking it in a hash table. So, not only aren't you searching, but even if you were, that's not the hard part. And even that is dwarfed by the application that's going to service the HTTP request. (Unless you are Google, in which case you don't need my advice.)
Searching HTTP headers is not your bottleneck. Use your language's built in string search. Premature optimization makes code slower.