Good Stuff
Robert Sedgewick, evangelizer of Quicksort and other fun fare, once said, “Algorithms are the Stuff of Computer Science.” Nowadays I suppose he would have quite a fight on his hands to convert the teeming hordes that claim that objects are the Right Stuff. I’m an ardent believer and proselytizer for objects, but I must confess that I find great satisfaction in facing the intellectual intrigue of finding just the right algorithm for a particular task, or of squeezing a bit more performance out of procedures in existing code.
To wit, just the other day I ran across a curious algorithm that claims to break the O(n log n) barrier for general-purpose sorting. It’s a quirky sort of function, hard to follow at first. Nonetheless, I ran it through those proverbial Hoops and found it to live up to its claims. Here is a table representing the number of comparisons it took to sort random sequences of large strings, for various sequence sizes (n). (For want of a better name, I call it QuirkSort.)
N QuickSort MergeSort QuirkSort 1,000 3,162 3,047 2,019 100,000 512,340 622,501 99,532 100,000,000 811,587,042 889,602,117 123,456,789 Amazing, isn’t it? Unfortunately, there is not enough room left on this page to give a suitable explanation of this algorithm, so I’ll leave that to another time.
On a lighter note, I just got wind that the Rogue Knave Poet is at it again. Herewith is the latest contribution of H. P. Typecraft (not his/her real name, of course).
Not the JVM (with apologies to Bob Dylan)
How many languages must a programmer try
Before you call him a man?
How many versions can vendors create
And claim that a standard is planned?
How many times must hype marketing fly
Before it’s forever banned?
The answer, my friend, is not the JVM
The answer is not the JVM
How many years can a program exist
Before it abuses the heap?
How many years can some objects exist
Before they’re allowed to be freed?
How many times can a man write his code
And pretend that he just doesn’t C?
The answer, my friend, is not the JVM
The answer is not the JVM
How many docs must a man look up
A consistent answer to find?
How many tools must one manager have
Before his developers cry?
How many crashes will it take till he knows
That too many servers have died?
The answer, my friend, is not the JVM
The answer is not the JVM
— H. P. TypecraftChuck Allison
Senior Editor
cda@freshsources.com