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.
> 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.
"If a mathematician is a machine for turning coffee into theorems, a computer scientist is a machine for converting caffeine into algorithms."
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.
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.
More info: http://www.linuxatemyram.com/index.html
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).