The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster!
To quote Majikthise: "Bloody hell, now that is what I call thinking."...
Another interesting bit of trivia: In the first chapter of my thesis I present a string matching algorithm with almost exactly the same asymptotic running time as BM -- but where BM performs exact matching using no precomputed index, my algorithm performs matching with mismatches using an index.
With an index, of course, exact matching is O(log N) time -- in a peculiar way, the "cost" of inexact matching is one index worth of efficiency.
[EDIT: On second thought, this last comment meaningful at all? I'm not sure, but it's almost 4AM so I'm not going to figure it out now.]
I'd like to read that.
Yes, http://www.daemonology.net/papers/thesis.pdf
I'd like to read that.
I recommend skipping the proofs. They're not very informative and the calculus gets rather tedious.
"If a mathematician is a machine for turning coffee into theorems, a computer scientist is a machine for converting caffeine into algorithms."
> I recommend skipping the proofs. They're not very informative and the calculus gets rather tedious.
And besides that is well over my head anyway, but I should be able to follow your main line of reasoning.
What I wouldn't give to infuse that sense in to present day programmers. (writing this on a box with 12G ram, pretty much maxed out).
http://www.gnu.org/prep/standards/html_node/Reading-Non_002d...
Space and speed will always be conflicting goals during optimizations (unless you're very lucky), and for practical use the sweet spot is usually somewhere in between the two extremes.
To blindly optimize for speed will result in very wasteful behaviour when it comes to memory usage, to blindly optimize for space will result in terrible performance.
Smart software realizes when the space is available and free for the taking and will use it to find an increase in speed, it will also realize when space is at a premium and economize on it's usage.
On another note, accessing all that memory costs cycles and is almost certainly going to trash your cache, chances are that if you manage to reduce your memory footprint eventually you'll find that instead of losing speed you're gaining speed.
Open Office started up with a blank word processor document uses 83 Megs of RAM, something tells me that could be a whole lot less without sacrificing functionality or speed.
One of the more major reasons of GNU developing the habit of writing utilities that were significantly different in their implementation was to make sure no UNIX/BSD code could leak in, since at the time the project was underway, BSD was stuck in that whole USL vs BSDi suit, and BSD's code was tentatively deemed 'non-free'.
One also needs to account for the time period these utilities were written, and for what computer system they were originally written for. Both memory and speed were expensive. Writing these utilities probably required much more thought to the smaller details than one would think about today when writing say a word processor, even though one could benefit by doing so.
Serious question: what are you using 12G of RAM on? My workstation is pretty modest (core 2 duo, 4G RAM) and I'm rarely able to utilize more than 1G.
More info: http://www.linuxatemyram.com/index.html
I'm not even testing stuff with VMs right now, as soon as I get in to that I have to shut down the IDE at a minimum or I'll hit the swap.
I also know people who work with fluid dynamics and the new workstations they bought for work have 48 gigs of RAM.
I'm not sure that either video editing or fluid dynamics count as bloatware in my book, because the problems are inherently complex. Word processing, however...
I haven't tried a lot of video editing software today (since I no longer pirate software like I used to), but what I have used is not huge progress from what I did in the late 90s. The only big step is that you can work with compressed streams directly, which is nice, but expected since even a modest machine today is expected to be able to decompress the latest MPEG spec in realtime.
That's about it.
For anyone else who skimmed the article and doesn't know the algorithm, check it out at http://en.wikipedia.org/wiki/Boyer-Moore. It's a very quick read to get the basic idea, and it's as good as jacquesm cracks it up to be.
http://www.ics.uci.edu/~goodrich/dsa/11strings/demos/pattern...
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sear...
(BM is especially cute because the basic idea is so simple: do it backwards. Quicksort is very clever. Arithmetic coding is mindbendingly cool, but the algorithm isn't simple enough - for this old brain anyway.)
But BM stands out for me because it is taking the opposite approach where that was entirely non-obvious in spite of lots of people having looked at that problem for a very long time (and plenty of those people were anything but stupid).
Deleted comment
And in spite of all that I think I can make the above statement in confidence, that algorithm has something very unique and it exhibits a level of thinking that goes beyond the ordinary world of programming.
> I'd say thinking up Boyer-Moore is nothing special. It's just a logical progression of ideas. If you think about the problem long enough, you would come up with the same solution, or maybe even a better one.
What's stopping you?
I'm sure we'd love to see the Palish algorithm that beats MB by a significant margin and that does not build upon it.
HN should not allow you to delete a post once it has a child comment. I find that people sometimes delete entire stacks of comments that have children (as in this case) when they don't seem to like how the argument is going. (This is not super-common, but it happens often enough that I've noticed it.) It's enormously frustrating for readers - not to mention childish on the part of the deleters.
Now, as for the rest of you kids, get off my lawn.
It seems to be something that has been 'figured out' and is now spreading. I'll theorize that it has to do with people that are afraid of the down-mod mob to avoid their karma taking a hit after posting something silly or they're afraid of being found in a decade by a google search from some prospective employer.
I could restore the deleted bits (without naming the author) if that's desired?
- put foot in mouth
- drunk in charge of keyboard
- 4 am
- the cat did it
- sincerely regret writing that
Deleted comment
There are people that are simply better at this stuff than I am, I'm not going to belittle my own work by paying homage to theirs. That does not mean that I can't improve relative to where I am today though, and I strive very hard to do so. Maybe one day I will be that good.
It's the difference between arrogance and objectivity.
I'm more than happy creating the stuff I do, every now and then I come up with something that is new (at least, new to me, see http://news.ycombinator.com/item?id=1353259), but that does not mean that I'm going to see this as anything other than the stroke of genius that it was.
If it really was that easy we could all improve on every major algorithm out there just by staring at it long enough and that's exactly why BM is so neat, it wasn't just a simple incremental improvement on someone else's code.
So, I challenge you, come up with an improvement on the status quo prior to BM that does not use the principles as exposed in BM and that performs on par or better, and that are not part of the current literature.
I'll tip you $250 if you manage to do that, that should be easy money for you. And I'm good for the cash.
You will probably get a nice wikipedia entry to boot.
Deleted comment
Just like hearing Jehudi Menuhin play should not cause you to burn your violin but to practice.
I'm not putting algorithms on a pedestal, I'm putting that particular example of all the algorithms available up as the one that I ran in to which taught me that I (still!) have a lot to learn.
When jacquesm is in awe of some developer, I find it inspirational, to think: hey, he's a mortal, maybe I can be that good too one day.