Bookshelf Classic: Beautiful Code

This book is what you get when you ask 38 top software developers "What is beautiful code?"  An open ended question, you get diverging answers such as a deep dive into a regular expression matcher from Brian Kernighan, an optimization of population counts from Henry S. Warren Jr. (for bit-heads, not sociologists), and a treatise on why code is better treated as an essay from Yukihiro "Matz" Matsumoto.

For this post though, I want to focus on Jon Bentley's contribution, curiously titled "The Most Beautiful Code I Never Wrote."  Elaborating, Bentley writes

In software, the most beautiful code, the most beautiful functions, and the most beautiful programs are sometimes, not there at all.

He then uses the Quicksort algorithm to illustrate his point, first reviewing the code, instrumenting it with counters, and optimizing it along the way.  But the pressing question he tries to answer is: "How many comparisons does Quicksort make, on average, for a random array of size n?"

One could generate large samples of random data, make several trial runs, and get an average, but Bentley takes a different route, a code-less path that crosses into mathematical proofs.  I didn't find it easy to follow, and got help from a talk he gave to Google in 2007: Three Beautiful Quicksorts.

In the end, Bentley derives a completely mathematical analysis of Quicksort's behavior.  It's wonderful.  It's frustrating.  It reminds me of an old joke:

A hungry man walks into a diner and sees the special is a Ham Sandwich.  "Nothing would be better than a ham sandwich!"  

The waitress returns with an empty plate.  "What's this?" the man asks.

She replies, "You said 'Nothing would be better than a ham sandwich.'  So I gave you Nothing."

The piece doesn't fill the belly, but it does move the mind.

For more on Bentley's work, see my review of his book More Programming Pearls.


Popular posts from this blog

Bookshelf: UNIX A History and a Memoir

Bookshelf Classic: The C Programming Language