5 ms·

I tested string searching algorithms a few years ago[0][1], and Brute Force was surprisingly performant, enough that picking a string searching algorithm become

I tested string searching algorithms a few years ago[0][1], and Brute Force was surprisingly performant, enough that picking a string searching algorithm becomes an engineering tradeoff. It found a sentence fragment at the end of Moby Dick within 8ms, 7 times slower than Boyer-Moore. But most of us aren't searching Moby Dick, but rather a HTTP header, some user input, or a paragraph of a document. Even long-winded users won't write Moby Dick into your <textarea>. Most languages and libraries use brute force for this reason - initializing and using Boyer-Moore may be slower than brute-forcing the text. Sometimes "practically nothing" is just a brute-force search. But Boyer-Moore is the perfect choice for Grep! The likely inputs on Unix are all huge: log files, entire directory trees, output pipes from loud programs, etc. The cost of initializing a small skip table is overwhelmed by the cost of I/O and the potential volume of text. It's not surprising that they've gone to some lengths to optimize the core inner loops and the I/O in that context. [0] http://www.jakevoytko.com/blog/2007/12/11/fun-with-string-searching/ http://www.jakevoytko.com/blog/2007/12/11/fun-with-string-se... I've declared bankruptcy on broken TeX and code examples... WordPress mangles them every few updates. [1] http://www.lysium.de/blog/index.php?/archives/201-Fun-With-String-Searching.html http://www.lysium.de/blog/index.php?/archives/201-Fun-With-S... A few improvements to the code in my post

deleted 16y ago
[deleted]
- jemfinch 16y ago
  The fact that computers use instructions in our universe? 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.)
- jakevoytko 16y ago
  Searching for "b" in "ab". Just two comparisons, compared to allocating, zeroing, and initializing a lookup table, and then doing a brute force search anyways. There's a fuzzy point where one becomes better than the other. Implementations written to be fast may brute-force length=1 strings, and implementations written for simplicity may not.
- jacquesm 16y ago
  > --somebody-- wrote: >> 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?
  - jemfinch 16y ago
    Because he was probably downmodded (appropriately) for his comment, and considered it an embarrassment. 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.
    - pmjordan 16y ago
      Retracting just the owner means you basically allow anonymous posting (except the mods still know who wrote it, and anyone who read it before the username got wiped). That opens up a whole new can of worms.
      - jemfinch 16y ago
        People can create an account with just a username and password; we're already effectively allowing anonymous posting.
fhars 16y ago
Moby Dick is very short compared to a normal server logfile.
- astine 16y ago
  Or rather, compared to a server log file that hasn't been properly rotated. I wrote a program a while back to incrementally parse a daily log file which was never rotated. It got say that it would take twenty minutes for for the program to just skip the lines that had been parsed previously. When those who had the power to do so started rotating the file, things speed up tremendously.
  - jonknee 16y ago
    Why didn't you split it?
    - fr0sty 16y ago
      Sparing that, why not use fseek() and do a binary search to get to where you wanted to go? Even better, save the prior offset somewhere and jump there immediately on T+1?
      - sigil 16y ago
        I used this trick the other day -- compute byte range partitions on a large file and use fseek when processing each. Is there a standard unix program that can output an arbitrary byte range from a seekable input? At first blush dd(1) looked like the ticket, but block-oriented operation means extra invocations to deal with a byte range that's not necessarily block-aligned.
        jacquesm 16y ago
        tail -c offset [input] | head -c length will do the job.
        pmjordan 16y ago
jacquesm 16y ago
> Brute Force was surprisingly performant, enough that picking a string searching algorithm becomes an engineering tradeoff. It found a sentence fragment at the end of Moby Dick within 8ms, 7 times slower than Boyer-Moore. 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.
- nostrademons 16y ago
  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.
  - jacquesm 16y ago
    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.
  - fleitz 16y ago
    The chances of analyzing just one HTTP header in an application are almost nil. Use a boyer-moore skip table.
    - adamtj 16y ago
      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.
matwood 16y ago
I thought this sort of thing was common knowledge? Searching and sorting a certain number of items under a threshold is fastest through brute force. The problem is figuring out what that threshold might be and then have the sorting and searching programs make use of it. I remember this topic being discussed back in undergrad.

deleted 16y ago

[deleted]

jemfinch 16y ago
The fact that computers use instructions in our universe? 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.)
jakevoytko 16y ago
Searching for "b" in "ab". Just two comparisons, compared to allocating, zeroing, and initializing a lookup table, and then doing a brute force search anyways. There's a fuzzy point where one becomes better than the other. Implementations written to be fast may brute-force length=1 strings, and implementations written for simplicity may not.
jacquesm 16y ago
> --somebody-- wrote: >> 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?
- jemfinch 16y ago
  Because he was probably downmodded (appropriately) for his comment, and considered it an embarrassment. 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.
  - pmjordan 16y ago
    Retracting just the owner means you basically allow anonymous posting (except the mods still know who wrote it, and anyone who read it before the username got wiped). That opens up a whole new can of worms.
    - jemfinch 16y ago
      People can create an account with just a username and password; we're already effectively allowing anonymous posting.

fhars 16y ago

Moby Dick is very short compared to a normal server logfile.

astine 16y ago
Or rather, compared to a server log file that hasn't been properly rotated. I wrote a program a while back to incrementally parse a daily log file which was never rotated. It got say that it would take twenty minutes for for the program to just skip the lines that had been parsed previously. When those who had the power to do so started rotating the file, things speed up tremendously.
- jonknee 16y ago
  Why didn't you split it?
  - fr0sty 16y ago
    Sparing that, why not use fseek() and do a binary search to get to where you wanted to go? Even better, save the prior offset somewhere and jump there immediately on T+1?
    - sigil 16y ago
      I used this trick the other day -- compute byte range partitions on a large file and use fseek when processing each. Is there a standard unix program that can output an arbitrary byte range from a seekable input? At first blush dd(1) looked like the ticket, but block-oriented operation means extra invocations to deal with a byte range that's not necessarily block-aligned.
      - jacquesm 16y ago
        tail -c offset [input] | head -c length will do the job.
      - pmjordan 16y ago

jacquesm 16y ago

> Brute Force was surprisingly performant, enough that picking a string searching algorithm becomes an engineering tradeoff. It found a sentence fragment at the end of Moby Dick within 8ms, 7 times slower than Boyer-Moore. 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.

nostrademons 16y ago
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.
- jacquesm 16y ago
  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.
- fleitz 16y ago
  The chances of analyzing just one HTTP header in an application are almost nil. Use a boyer-moore skip table.
  - adamtj 16y ago
    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.

matwood 16y ago

I thought this sort of thing was common knowledge? Searching and sorting a certain number of items under a threshold is fastest through brute force. The problem is figuring out what that threshold might be and then have the sorting and searching programs make use of it. I remember this topic being discussed back in undergrad.