I think that line of thinking is actually symptomatic of producing the kind of software that eats up our present day powerhouses and makes them dog slow.

A HTTP header is several orders of magnitude shorter than Moby Dick.

> "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.

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.

I happen to agree with your preference, but most people don't seem to.

A much better solution is to write things in the easiest way for coders to change - that way, when something is found to be the actual cause of slowness, anyone can easily go in and optimise it or move it to a background thread. Optimising EVERYTHING in the hopes of obtaining speed is a fool's errand - due to the 90/10 rule, 90% of the code you optimise will never be the bottleneck.

-- Ayjay on Fedang/coding

I'd prefer it your way too. One other thing, we're assuming good programmers and that's not something I'd bet on at most places.

will do the job.

I remember this topic being discussed back in undergrad.

>> initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search.

> and you are basing this claim on…?

Think of it as an up-front cost that you expend before doing any actual work. So BM is slower in some cases, and faster in others. In most short cases the cost of setting up outweighs the advantages of the more complex algorithm and then you're better off to brute-force it.

The Moby-Dick example, however is not such a case.

Just like it takes longer to prepare an offset press to make a single copy of a page compared to just slapping it in to the photo-copier. But if you need a million copies, you can't beat (rotary) offset.

edit: I've re-constructed the original comment this replied to because I'm not happy about the recent trend in comment deletions (see below), that's the fourth time in a few days that I come across this. To the author of the parent of this comment (you know who you are), why did you delete your comment after receiving 3 serious replies?

I'm not fond of such deletions, but I think it's good for people to be able to retract their statements when they realize they don't reflect well on themselves.

Perhaps a better solution would be to allow the original comment to be "retracted" such that the author information is removed but the comment remains, so people can still understand the thread of the conversation.

Seriously, if you don't understand what he's basing his claim on, it's because you don't understand the Boyer-Moore algorithm. If you know how Boyer-Moore works, the reason is obvious. Instead of snarkily replying, why don't you take the same amount of time to read the wikipedia article on Boyer-Moore and see why brute force may be faster in some cases.

(Since you've already shown yourself to be lazy, however, I'll explain it: Boyer-Moore constructs two alphabet-sized integer arrays based on the "needle" you're looking for; if your haystack is smaller than twice your alphabet size, and it frequently is, then Boyer-Moore is practically guaranteed to take more time than brute force.)