Programming Pearls (Second Edition) 47
| 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.
PERL? (Score:1)
'Programming PERL'.
I guess i should read a tad slower, huh?
--
(wildly offtopic) Regarding Alice (Score:1)
I agree wholeheartedly. Reading Carroll changed my life, and I make a point to re-read Alice and Through the Looking-Glass at least once a year. But more than a Mathematician, Carroll was a surrealist. I've found that the abstract thinking involved in understanding surrealisim is really helpful in learning to work with computers (beit admin or programming). Good to see I'm not the only one who sees the Alice/computing connection
Incidentally, they're making a pc game based on Alice, but it's a first person shooter about a goth chick. Sigh. *whacks head on desk*
Alice in Wonderland (Score:1)
Jeroen Nijhof
Markoff Text Generator (Score:1)
The Markoff Text Generator should make interesting reading. This was the basis of a program that won first prize in the annual Turing Test competition a couple of years ago.
I'd post the URL but I think its gone to the great bookmark file in the sky
Note [1] (OT) (Score:1)
Btw, A version in the UK has some wonderful surrealist illustrations by Antony Browne (leading children's illustrator/author with a surreal twist)
Briefly on topic - any book written well, with enthusiasm for the subject matter tends to instil enthusiasm in those who read it. I just wish more coding authors realised this....
Alice game..... (Score:1)
Read this programming classic! (Score:3)
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
Aha! Books... (Score:2)
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.
Illustrating Alice (Score:1)
I have a reproduction of a 1907 limited printing of Alice's Adventures in Wonderland that was illustrated by Arthur Rackham.
Rackham's illustrations are quite lovely and contain a certain something that Tenniel lacked.
Here is an except from the "About This Edition":
While I will not assert that color makes one picture superior over another, I do suggest that any fan of the story who hasn't seen Rackham's illustrations take a look. Even the pieces that are not in color have a charm and flair that escape arbitrary placement in the shadow of Tenniel's exemplary work.
Re:Note [1] (OT) (Score:1)
- Grimm's fairy tales have been watered down for generations because the original ones are actually rather gruesome.
- Anything animated is now considered targeted at children. Any of the nine old men will tell you that Bambi wasn't a children's movie. Cartoons shown in theaters ('50s and earlier) contained what the (adult) animators thought was entertaining.
I'm not defending Disney. I'm just saying Disney didn't start it, people who want things simplified so they don't have to think too hard started it.More info (Score:2)
Programming Pearls [programmingpearls.com]
Re:(wildly offtopic) Regarding Alice (Score:3)
asdf (Score:1)
More than once I have seen this book shelved with the perl books at the bookstore...
Sorry, guess I was being too specific... (Score:1)
Re:programming monkeys (Score:1)
All geeks should take Bentley's Estimation Quiz! (Score:3)
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. [bell-labs.com] 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:(wildly offtopic) Being John Markovich (Score:1)
Automated Alice (Score:1)
Read a good book lately?
Re:All geeks should take Bentley's Estimation Quiz (Score:2)
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:
Not Estimation - Trivia (Score:2)
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.
Canucks... (Score:1)
Click Me! [chapters.ca]
BTW - This book cost enough that Chapters'll ship it free. Even better!
Bentley's a great speaker (Score:1)
Being John Malkovich? (Score:2)
John Markovich [iaxs.net] is a photographer based in Minneapolis, MN...
Re:Perfect 10! (Score:1)
--
Re:(wildly offtopic) Being John Markovich (Score:1)
--
Re:All geeks should take Bentley's Estimation Quiz (Score:1)
Alice in wonderland - one problem (Score:2)
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
Re:When will authors start coding securely? (Score:1)
--
Re:Alice in wonderland - one problem (Score:1)
--
Re:Alice in wonderland - one problem (Score:1)
Lewis Carroll is alluded to being a pedophile usually based upon his hobby of photographing young nude girls. That does sound a bit pervy but that doesnt mean it was sexual. Is a painter who draws male nudes a homosexual? The Victorian times were very different, often alien, times. Some of the girls he photogrphed in the nude were watched over by nannies who didnt see anything unusual about it. In the end since there is no direct proof or real implication that he was a perv it doesnt necessarially need mentioned.
William Ewart Gladstone a Victorian British Prime Minister made it a habit of his to go to the seedier parts of town and bring home a prostitute. Sounds a little funny doesnt it. Course, he and his wife (kinky!) then served her tea and try to convince her to repent and take up a more honest trade
John Ruskin, Victorian art critic(most notable after Whistler sued him), married a girl named Effie and on their wedding night he realized that girls arent built quite the way he expected (i suppose he expected her to be made out of marble). He was digusted by her anatomical correctness and never did sleep with her. Eventually she left him, filed for an annulment and then married the painter Millais(who she fell in love with while he was painting her portrait. He was painting Ruskin while the annullment suit was in progress, but Ruskin even though his wife was leaving him for Millais continued to sit for the painting. (see- "stiff upper lip, British") Needless to say the friendship between ruskin and Millais ended.
Ruskin eventually fell in love with a ten year old girl and when she turned 17 asked her to marry him. Apparently her parents objected to his previous marriage and annullment. But doesnt the fact that he waited until she was 17 imply that he was less of a perv and more socially disfunctional
remember not everything needs overanalysis and a different time comes with a different culture.
Of course not (Score:2)
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:Being John Malkovich? (Score:1)
Magical length (Score:1)
Regarding Alan Perlis (Score:1)
Re:When will authors start coding securely? (Score:1)
Still I think its something that more programming books should mention in bold in the
introduction - not tucked away in an appendix..
Steve
---
http://GNUSoftware.com/ [gnusoftware.com]
Re:When will authors start coding securely? (Score:1)
"The programs use a terse coding style: short variable names, few blank lines, and little or no error checking. This is inappropriate in large software projects, but it is useful to convey the key ideas of algorithms."
Much of the "code" is in fact pseudocode. One thing it does include which is a good habit, is scaffolding for testing, debugging, and timing the functions. That's something you don't see everyday.
--
Re:Not Estimation - Trivia (Score:2)
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).
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.
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.
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.
Re:Regarding Alan Perlis (Score:2)