Bookshelf Classic: Beautiful Code

-
Cover
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.









Comments

Post a Comment

Popular posts from this blog

MR2 Check Engine

-
Image
Shown here is the 1991 Toyota MR2. Thanks to the mechanical skills of a family enthusiast, it purrs, growls, and turbo whistles like a dream.   My hardware ability doesn't go much further than oil changes. Rather, my expertise is in software, and I wrote an Android App (iOS version is in progress) to diagnose the flashes of the check engine light. This second generation MR2 predates the OBD2 connector, a standard used to diagnose engine, transmission, and emissions problems quickly and easily. Instead, we have a flashing check engine light which needs some deciphering, followed by a lookup in the service manual. Basically, you count flashes to arrive at fault code number. A short pause (~1.5 seconds) indicates the start of the next digit. A medium pause (~2.5 seconds) indicates start of the next fault code. And a long pause (~4.5 seconds) means the sequence has ended and will repeat. The video below corresponds to the codes 41 and 51. Using the the MR2 Check app and selecting the 3
Read more

Bookshelf: UNIX A History and a Memoir

-
Image
  A man page will give you, in black and white, specific information about UNIX. Brian Kernighan's new book adds color and depth about UNIX you won't find anywhere else. I'm not a gray beard (yet), but I imagine they would plow through the book knowingly, but at the same time, learn a few things. Those new to UNIX -- recent college grads or those experimenting with Raspberry Pi -- would be better off starting with Chapter 8 which describes more relatable events and the descendants of UNIX, including Minux and Linux. It's when they start to ask questions like "Where does UNIX come from?" and "Why is Gamora grep?" that they should start from the beginning: Bell Labs, 1969. Kernighan opens with a birds-eye-view of Murray Hill New Jersey, zooms in on the buildings, the offices, the significance of Center 1127, and offers a brief look at some of the key players there. As I progressed through the book, the two factors that made UNIX not just possible, bu
Read more

Bookshelf Classic: The C Programming Language

-
Image
My first job had me programming in Microsoft BASIC for the IBM PC (DOS).  BASIC worked well enough, but its limitations were clear.  The language was interpreted and therefore slow.  More importantly, it wasn't a modern structured language, and instead, relied on line numbers and the GOTO statement.  Anyone who has read Dijkstra knew  GOTO was a bad thing . Having learned a structured language in college ( PL/I ), using BASIC felt unnatural.  When a C compiler became available for the PC, I saw a chance to improve and modernize our software.  The problem was selling the idea -- a problem made harder because I wasn't fluent in C. "It would be a staffing problem.  Not many people know C, but we can find a lot of programmers who know BASIC," noted one manager. The argument was strong as my knowledge of C was weak.  But I knew that C, by design, was a small language and thus easy to learn.  "It has about 30 keywords," I proffered to another manager. U
Read more