Programming Pearls (Second Edition)

SEGV has continued his tradition of excellent reviews with an examination of Jon L. Bentley's Programming Pearls (Second Edition), recently released by Addison-Welsey. One of the classics of programming, the new version continues the first edition's heritage of excellence. Click below to read more. Programming Pearls (Second Edition) author Jon L. Bentley pages 239 publisher Addison-Wesley, 10/1999 rating 10/10 reviewer SEGV ISBN 0-201-65788-0 summary A classic revised.

Choice and Precious

One definition of pearl is something "very choice or precious." Like the programming pearls it describes, Bentley's collection of essays has itself transcended the ordinary to achieve pearl status.

Originally published in Bentley's "Programming Pearls" column in Communications of the ACM, these fascinating essays were collected and revised in book form in 1986. Now revised 14 years later, this material has definitely stood the test of time. The first edition remains #2 on McConnell's Code Complete Reading List, and is listed favourably in an article on Great Books in Computer Science.

A Sense of Wonder

It was directly because of McConnell's Code Complete reading list that I, a few years ago, purchased and read Programming Pearls and its sequel, More Programming Pearls. Despite McConnell's effusive praise and corroboration from a colleague, I was not fully prepared for the experience.

I say experience, because that's what it was. It reminded me of reading Alice's Adventures in Wonderland [1] or Godel, Escher, Bach [2] (perhaps not coincidentally, also on the above list of great books in computer science). It filled me with a sense of wonder that is difficult to describe. It confirmed my love for computer science.

I believe that I am not alone in this regard.

What's New?

Twelve of the thirteen columns in the first edition have been edited substantially for this edition, and three new columns have been added. The new columns are on the topics of testing & debugging & timing, set representations, and string problems. This new edition is about 25 percent longer.

Although the first edition had been getting a little long in the tooth, the revisions once again place the essays in the modern world. Discussions of performance take into account modern hardware, caches, and instruction-level parallelism. Modern languages (C++, Java) are compared and contrasted where appropriate. Modern books (such as McConnell's Code Complete and Musser & Saini's STL Tutorial and Reference Guide [3]) are referenced and recommended.

Like Meeting an Old Friend

Re-reading this book was like meeting an old friend. Notwithstanding the major revisions, it has changed in subtle ways. Some anecdotes have been updated, some material reorganized. But it's still the same book. All of the energy and fun remains, youthful as ever.

I'm pleased to see that Bentley is still happy working at Bell Labs / AT&T / Lucent. Perhaps that's why this book is so great. There's a lot of intelligent people working there, and they put out some fine books. Bentley produces a Markov text generator in column 15, and compares it favourably to his colleagues' (Kernighan and Pike) version in the recent book The Practice of Programming [4].

Supporting Material

I must say that the supporting web site for this book (URL below) is excellent. It has all the information on why this book was updated, along with exactly what was revised. There the curious reader will find excerpts from columns, some problems and their solutions, and many other parts of the book available online.

All of the source code is available and free for use. Relevant web sites are linked and annotated. I love the Java applet that demonstrates sorting algorithms (source available!). Bentley even provides some overhead transparencies for use in teaching.

Recommendation

This is a no-brainer. I've always recommended reading this classic, and even re-reading it. The second edition is merely an excuse to purchase and (re-)read a revised copy. The time spent is well worth it. (Remember, only one column per sitting!)

I also recommend scrounging a copy of the sequel, which is out of print [5].

Purchase this book at fatbrain.

Links

Programming Pearls (Second Edition) Official Site

Programming Pearls (Second Edition) at Addison-Wesley

Programming Pearls (First Edition) at Addison-Wesley

More Programming Pearls: Confessions of a Coder at Addison-Wesley

Table of Contents

Part I: Preliminaries
1. Cracking the Oyster
2. Aha! Algorithms
3. Data Structures Programs
4. Writing Correct Programs
5. A Small Matter of Programming
Part II: Performance
6. Perspective on Performance
7. The Back of the Envelope
8. Algorithm Design Techniques
9. Code Tuning
10. Squeezing Space
Part III: The Product
11. Sorting
12. A Sample Problem
13. Searching
14. Heaps
15. Strings of Pearls
Epilog to the First Edition
Epilog to the Second Edition
Appendix 1: A Catalog of Algorithms
Appendix 2: An Estimation Quiz
Appendix 3: Cost Models for Time and Space
Appendix 4: Rules for Code Tuning
Appendix 5: C++ Classes for Searching
Hints for Selected Problems
Solutions for Selected Problems
Index

Notes

[1] Why do people (book sellers, web sites, bibliographies, etc.) insist on incorrectly calling this book Alice in Wonderland? It's not just for kids; Lewis Carroll was a mathematician, and it abounds in metaphor, puzzles, hidden treats. Read it. Accept only the John Tenniel illustrations!

[2] Godel, Escher, Bach: An Eternal Golden Braid is subtitled A Metaphorical Fugue on Minds and Machines in the Spirit of Lewis Carroll. It was reviewed on Slashdot: Godel, Escher, Bach (Review).

[3] However, use this book instead: Austern's Generic Programming and the STL.

[4] I reviewed this book for Slashdot: The Practice of Programming (Review).

[5] Why? I don't understand why some classics go out of print. I'm still trying to find copies of Artificial Life II, On Numbers and Games, Computation: Finite and Infinite Machines, and a host of others.

Comments

Read this programming classic!

[RNG]

Programming Pearls is very cool. The nice thing about it is that really explains in detail some of the thought processes which lead to a programming being written the way it is; it very nicely shows the tradeoffs involved in choosing one approach over another.

The other cool thing is, that this really is a book for programmers. I appreciate Donald Knuth as much as the next guy, but his books are so mathematical, that I found myself skipping over more of the material, than I thought was good. Programming Pearls is the opposite: it clearly lays out the algorithms involved and often has nice drawings of the actual datastructures used. For a book of it's deapth it's pleasanly short, sparse in math and to the point. Read it, think about it for a while, program for a while and then read it again ... it'll be worth your time ...

Aha! Books...

[Logos]

I bought the 1st edition of this book not too terribly long ago, and before I had read a third of the way through it, I was using its insights in my code.

I was working on a series of General Ledger reports, and the first one? Well let's just say that I won't win any design awards. Somewhere in there I started reading this book and my code cleaned up dramatically. I can't say that the next report in the series will win any awards either, but I found myself sitting and waiting a bit before coding, and it has paid off. By the end of the project, my programs were almost elegant. I enjoy looking at them--and they aren't a nightmare for mods.

Just an example: The report before reading the book and the one right after are both variations of Income Statements. I needed to make a change that would affect both. Some of the code was in a joint library file, but some was in each report. The first report required at least a dozen places of change, the second required THREE LINES!

Granted, better design ideas from other sources were at work, and these were some of my first commercial programs, but this book definitely had an impact.

Buy this book, and take the time to ingest it. Work the programs--even if you think you understand them. It will pay off nicely.

At least it did for me.

More info

[Zoltar]

Check out the books website for lots of little snippets from the book

Programming Pearls

Re:(wildly offtopic) Regarding Alice

[Ed Avis]

As Alan J. Perlis said:

The best book on programming for the layman is "Alice in Wonderland", but that's because it's the best book on anything for the layman.

All geeks should take Bentley's Estimation Quiz!

[King Babar]

While I was checking out the website for Programming Pearls, second edition, I stumbled across what turns out to be the complete text of Appendix 2, which is a quiz that tests your estimation ability.

Whether or not you buy the book, and whether or not you think of yourself as a programmer, if you consider yourself a thinking person, you should take this quiz. If you can't do back-of-the-envelope calculations, you should find this out as soon as possible, and fix the problem while you still can.

Re:All geeks should take Bentley's Estimation Quiz

[sde1000]

Whether or not you buy the book, and whether or not you think of yourself as a programmer, if you consider yourself a thinking person, you should take this quiz. If you can't do back-of-the-envelope calculations, you should find this out as soon as possible, and fix the problem while you still can.

The problem I had with this quiz was that a lot of the questions assume American units and places. For example, I don't have a really good mental model of what weight a pound is, I don't know where Mississippi or Missouri are, and I've only heard of the Golden Gate bridge - I've never seen it.

How about some alternative questions:

• January 1, 2000, population of the United Kingdom in millions
• Length of the Thames in miles
• Weight of a Mini Metro in tonnes
• Length in metres of the span of the Humber bridge
• Weight in kilograms of a barrel of beer
• Length of Hadrian's Wall in miles

Not Estimation - Trivia

[DragonHawk]

This is a simple trivia quiz, not an estimation quiz.

Estimation is the process of making reasonable assumptions based on incomplete or limited data. You need to have some data to base your estimates on, however.

I could perhaps estimate the length of the Golden Gate Bridge or the weight of a Boeing 747, but only if I had a frame of reference. As I have only seen the GGB in artistic visuals not intended to give a sense of scale, and I have only seen a 747 in Hollyweird movies, I couldn't provide a worthwhile estimate for those.

I happened to know that the Shuttle orbits in about 90 minutes, and that roughly 50 people signed the Declaration of Independence, so I did well on those. But the significant factor here my knowledge of trivia, not estimation skills.

A true test of estimation would be to give you various pictures of things, with a known quantity for scale, and ask you to figure out dimensions, weight, volume, etc.

Re:Not Estimation - Trivia

[King Babar]

This is a simple trivia quiz, not an estimation quiz.

I have to disagree. There are specific facts that can be helpful to you to get exact answers, but half of the battle is in knowing what to do with information that is more shaky. And we certainly agree that people are not likely to know the exact answers here (that would be trivia).

Estimation is the process of making reasonable assumptions based on incomplete or limited data. You need to have some data to base your estimates on, however.

Yup. But it's surprising how close you can come with very little data. And if you know you're not going to be close at all, you should learn how to widen your confidence intervals.

I could perhaps estimate the length of the Golden Gate Bridge or the weight of a Boeing 747, but only if I had a frame of reference. As I have only seen the GGB in artistic visuals not intended to give a sense of scale, and I have only seen a 747 in Hollyweird movies, I couldn't provide a worthwhile estimate for those.

The estimate doesn't have to be especially worthwhile. It just has to have confidence bounds that include the true value. Yes, smaller intervals mean something, too, but that wasn't the explicit point of the exercise. Interestingly, I fell into that trap a bit myself, which is why I suggested that people try this out.

So, let's do the Golden Gate Bridge. I've only seen it once or twice myself; how in the heck should I know how long the main span is? On the other hand, I do know that the big deal about that bridge is that it does have a very impressive main span. So how long does a bridge have to be to be impressive for this? A mile, within a factor of 2? That's a confidence interval of like 2500 to 10000 feet. Yes, it's pretty broad, but it's also correct. Or maybe you know that 10000 feet is right out, because that would mean the main towers would have to be too tall to have the nice shape they have. Fine; then reduce that end of the estimate, to, oh, 6000 feet? That's still a covering interval, and a shorter one. Maybe that's the best that you can do, but give yourself credit for getting that far from almost nothing.

Again, let's do the weight of a 747. Like I have any idea what that is. Fine; the guess will be pretty wild, then. I think a 747 holds a lot of people. At least 300, probably less than 600? Fine. I can work with that. How much does a plane weigh? Well, how much does a car weigh? A big SUV might weigh 6000 pounds and carries 6 people, so that's 1000 pounds per person. Oh yeah: the person weighs 200 pounds, and they have 50 pounds of baggage. So what does that give us? 375,000 to 750,000 pounds. Anything I'm leaving out? Ah: fuel. The SUV gets 15 miles per gallon to haul those 6 people, or like .01 gallons per person mile. I suppose a jet aircraft could be worse, but I'm not sure how much worse. Now, a 747 can go at least across the Pacific without refueling; I bet that's oh, 6000 miles. 6000 miles * .01 gallons/person/mile*600 people = 36000 gallons of fuel. I know water weighs 8 pounds a gallon, and gasoline (or jet fuel) is rather lighter; maybe 5 pounds per gallon? So that's 90,000 to 180,000 pounds of fuel, for a total wild ass guess of 465,000 to 930,000 pounds. I'm pretty sure that the low end is below, but the high end might not be high enough; I'd be willing to go to 1.3 million or so to be comfortable.

And, as it turns out, the actual weight is in both ranges. In both cases, you could have treated the questions as trivia questions, but then you would have missed the point of the quiz.

I happened to know that the Shuttle orbits in about 90 minutes, and that roughly 50 people signed the Declaration of Independence, so I did well on those. But the significant factor here my knowledge of trivia, not estimation skills.

But one person's trivia is another person's estimation problem.

Take the Declaration of Independence signing. You know that representatives of 13 colonies signed the things, and that each state had one or more delegates. So the minimum number has to be greater than 13. For the maximum number, I suppose you might choose low. I figured 5 would be generous, so my estimate was [20,65], which includes the real value.

Now take the space shuttle. That's trivia for you, but I had to figure it out. First, I took out my trusty notepad, pretended it was a decent pendulum, and estimated its period. About 1 second; how convenient. The pad is 11/12 of a foot, and there are 5280 feet in a mile. I guessed that the shuttle orbits like 200 miles above the surface, or about 4200 miles above the center of the earth. Now, I know that the period of a pendulum depends only on the acceleration due to gravity, and the length of the bob; in fact it's proportional to (a/l)^.5. Gravity is (4000/4200)^2 weaker in orbit than on earth, so putting all this together, I get an estimate of 86 minutes, which I'll gather is good to within plus or minus 20%. So my interval is [70,102] minutes. Got it again... And this is the whole point: the exact answer is a trivia question, but the ability to get the answer to within an order of magnitude or a factor of 2, and to know how loose your confidence interval is, depends on your estimation ability.

Being John Malkovich?

[Christopher B. Brown]

Would you be thinking of the movie Being John Malkovich maybehaps?

John Markovich is a photographer based in Minneapolis, MN...

Alice in wonderland - one problem

[tilly]

Charles Lutwidge Dodgson (better known as Lewis Carroll) did not make up Alice. Alice was a real girl, full name of Alice Pleasance Liddell, and Dr Dodgeson is widely believed to be a paedophile.

There is no evidence that he ever consummated his relationship with young Alice, he was quite proper about it and all, but you can judge his interest from the fact that he took pictures of female children (including Alice) as scantily clad as he could arrange and eventually proposed marriage to Alice.

For some reason this gets glossed over in a lot of places...

Regards,
Ben

Of course not

[tilly]

Although it does make reading the book a very different experience.

The book is based on short stories that he told Alice + other female friends to keep them interested in him. Alice (at the age of 7) is the person the story is being told to. The Red Queen appears to be based on the chaperone. So on and so forth.

So while you can read the book without knowing the background, the background definitely affects how you interpret the book!

Regards,
Ben

Re:Regarding Alan Perlis

[Ed Avis]

Not my page... interesting mistake, though.