Beautiful Code [11]
Example 3-1. Quicksort function
void quicksort(int l, int u)
{ int i, m;
if (l >= u) return;
swap(l, randint(l, u));
m = l;
for (i = l+1; i <= u; i++)
if (x[i] < x[l])
swap(++m, i);
swap(l, m);
quicksort(l, m-1);
quicksort(m+1, u);
}
This code sorts a global array x[n] when called with the arguments quicksort(0, n-1). The two parameters of the function are the indexes of the subarray to be sorted: l for lower and u for upper. The call swap(i, j) exchanges the contents of x[i] and x[j]. The first swap randomly chooses a partitioning element uniformly selected between l and u.
Programming Pearls contains a detailed derivation and proof of correctness for the quicksort function. Throughout the rest of this chapter, I'll assume that the reader is familiar with Quicksort to the level presented in that description and in most elementary algorithms textbooks.
If you change the question to, "What is the most beautiful piece of code that you've written that was widely used?" my answer is again a Quicksort. An article I wrote with M. D. McIlroy ("Engineering a sort function," Software–Practice and Experience, Vol. 23, No. 11) describes a serious performance bug in the venerable Unix qsort function. We set out to build a new C library sort function, and considered many different algorithms for the task, including Merge Sort and Heap Sort. After comparing several possible implementations, we settled on a version of the Quicksort algorithm. That paper describes how we engineered a new function that was clearer, faster, and more robust than its competitors—partly because it was smaller. Gordon Bell's sage advice proved true: "The cheapest, fastest, and most reliable components of a computer system are those that aren't there." That function has now been widely used for over a decade with no reports of failure.
Considering the gains that could be achieved by reducing code size, I finally asked myself a third variant of the question that began this chapter. "What is the most beautiful code that you never wrote?" How was I able to accomplish a great deal with very little? The answer was once again related to Quicksort, specifically, the analysis of its performance. The next section tells that tale.
Finding Things > On Time
4. Finding Things
Tim Bray
Computers can compute, but that's not what people use them for, mostly. Mostly, computers store and retrieve information. Retrieve implies find, and in the time since the advent of the Web, search has become a dominant application for people using computers.
As data volumes continue to grow—both absolutely, and relative to the number of people or computers or anything, really—search becomes an increasingly large part of the life of the programmer as well. A few applications lack the need to locate the right morsel in some information store, but very few.
The subject of search is one of the largest in computer science, and thus I won't try to survey all of it or discuss the mechanics; in fact, I'll only consider one simple search technique in depth. Instead, I'll focus on the trade-offs that go into selecting search techniques, which can be subtle.
4.1. On Time
You really can't talk about search without talking about time. There are two different flavors of time that apply to problems of search. The first is the time it takes the search to run, which is experienced by the user who may well be staring at a message saying something like "Loading…". The second is the time invested by the programmer who builds the search function, and by the programmer's management and customers waiting to use the program.
Correct, Beautiful, Fast (in That Order): Lessons from Designing XML Verifiers > The Role of XML Validation
5. Correct, Beautiful, Fast (in That Order): Lessons from Designing XML Verifiers
Elliotte Rusty Harold
This is the story of two routines that perform input verification for XML, the first in JDOM, and the second in XOM. I was intimately involved in the development of both, and while the two code