5 ms·

Jon Bentley's Programming Pearls: 25 years old, still brilliant

136 points by MikeTaylor 16y ago

ultrasaurus 16y ago
When I interviewed at Microsoft, they recommended reading this book -- I doubt it helped at all, but it's a great read (as is the sequel) if you haven't read it. There's a real sense of history too, some of the problems illustrate how far we've come: like talking about transferring a whole megabyte several miles as a challenge.
- enneff 16y ago
  When people ask me how they should prepare for the Google interviews, I always tell them to work through the problems in this book.
michaelcampbell 16y ago
I, by pure luck alone, happened across this book early in my career, and I still go over it from time to time. I will probably die with it in my "keep forever" library.
- dguaraglia 16y ago
  Ha! Me too! I asked a librarian at my university to fetch me "whatever they had on Perl" (this was my first incursion into the interpreted language world) and the librarian came back to me with this. Imagine my surprise when I started reading the book over the weekend (only then I noticed the title said 'Pearls' not 'Perl'). Forward 10 years, I have a copy in my bookshelf and read a chapter every now and then just to keep myself real. I've completely (and happily) forgotten everything about Perl though.
  - rodh257 16y ago
    whenever I'd seen this book mentioned in 'best programming books' lists, on Stack Overflow and the like I'd figured it was a cutely named book to do with Perl and skipped over it.
- kragen 16y ago
  Me too. I read it, and its sequels, in a bookstore, around 1998. Looks like Bentley's retired, sadly: http://www.research.avayalabs.com/gcm/usa/en-us/people/all/bentley.htm http://www.research.avayalabs.com/gcm/usa/en-us/people/all/b...
deleted 16y ago
[deleted]
noeleon 16y ago
Great book, I reference it all the time. Article made me very hungry though.
ludwigvan 16y ago
Bentley's articles on acm : http://portal.acm.org/author_page.cfm?id=81100143310&query=(Author:81100143310)%20&srt=meta_published_date%20dsc&role=Author&perpage=all&termshow=matchboolean&CFID=18592091&CFTOKEN=68573972 http://portal.acm.org/author_page.cfm?id=81100143310&que... It might require a subscription, though. It seems to contain the articles from the book, starting with those from 1983.
- ludwigvan 16y ago
  "I cannot describe the excitement I felt when my own first article "Multidimensional Binary Search Trees Used for Associative Searching" was published in September 1975. It received second place in the 1975 Forsythe Student Paper Competition. Back then, original research papers were viewed as within the reach of undergraduate students (truth be told, I tied with a high school student) and of interest to the general ACM community. I wrote my paper (under the guidance of Donald Knuth) explicitly for the Competition; had it not existed, I would not have written it. It remains to this day my most cited research paper. (And because I’m sure that your inquiring mind wants to know, I’ll point out that first place went to a lad by the name of Guy Steele, who I’m betting turned out okay." This excerpt is from his most recent article on acm, "In the realm of insight and creativity".
melling 16y ago
From his book: "It is faster to make a four-inch mirror and then a six-inch mirror than to make a six-inch mirror." This is one of my favorite programming quotes. I haven't seen it used much over the years.
- MikeTaylor 16y ago
  That one is a quote from Ken Thompson, the inventor of (among much else), Unix and UTF-8. It is quoted in _Programming Pearls_, though -- I think, in the sequel rather than the original.
- cafard 15y ago
  As noted, a quotation from Ken Thompson. It appears in the chapter "Bumper Sticker Computer Science" in _More Programming Pearls" along with many other fine aphorisms.
kylec 16y ago
I know it's the author's thing, but I've really grown to hate the pictures of food in his articles. I might feel differently if it were done well, but there needs to be more of a reason to include a picture of food than simply wanting a visual break in the article.
- hartror 16y ago
  I find it strange that is for sure.
- deleted 16y ago
  [deleted]
- sliverstorm 16y ago
  I'm sure the author has a reason. I can't help but think that reason is the author is incredibly preoccupied with food.
  - MikeTaylor 16y ago
    Yes, it really is that simple. I am preoccupied by food in general and sushi in particular. Sorry that there is no deeper, allegorical reason for the pictures.
    - barrkel 15y ago
      I adblock the images in your articles because I find them highly distracting and slightly repulsive (I'm not a fan of sushi). I did so the first time your articles came up here on HN (and I remarked upon it then), and I had to do so again yesterday, as I've had a new machine since then.
      - MikeTaylor 15y ago
        Nice solution! I'll recommend it to others who complain about the images, thanks for the tip.
jswinghammer 16y ago
I think the most valuable parts of this book for me were the stories that involved solving problems within constraints. If you work with a large enough dataset or management that won't allow you to buy the hardware to just make your problems go away constraints are still a big part of software development.
enneff 16y ago
See also: Jon's great Google Tech Talk "Three Beautiful Quicksorts". http://www.youtube.com/watch?v=aMnn0Jq0J-E http://www.youtube.com/watch?v=aMnn0Jq0J-E
dfan 16y ago
Bentley's book "Writing Efficient Programs" is also really super. Unfortunately, it's been out of print for a long time. If you ever see it, snap it up.
terhechte 16y ago
I love this book. I have it next to my bed and read in there from time to time before I fall asleep. Makes you dream up great algorithms (at least I try to belief that ;)
rdmlx 15y ago
Read it online here: http://www.cs.bell-labs.com/cm/cs/pearls/ http://www.cs.bell-labs.com/cm/cs/pearls/
cygwin98 15y ago
As brilliant as the algorithms listed in the book are, I find them less and less interesting in and out of themselves nowadays. Those data structures and search algorithms have really become basics. I just don't understand why people still blindly worship this book and the way it was and are still trying to replicate it during interviews. If you want to test a developer, don't force them to do bitwise manipulations in C. Why not step up a bit further and try to ask them to apply those data structures and algorithms into a server cluster or a server cloud and see how they come up with a solution. That is more likely the case they will encounter nowadays. All right, enough of rants. Here is my take on this book. This is one of my favorite books. Great things like this book, in the same way as Unix, C and other oldies, can last for a really long time. One thing of the book that intrigued me was the way those old great hackers managed to conquer seemingly impossible problems, despite the severe constraints such as limited memory space, in a extremely resourceful manner. The bit sort in chapter one and the chapter how Ken Thompson squeezed storage space for his chess program are two of my favorite read. The other thing I think may be even more useful is the back of the envelope estimation, which encourages out of the box thinking or street smart (though those kinds of questions got abused and became notorious in technical interviews). Constraints still exist as we begin to attack harder and bigger problems, such as "web-scale" applications. New metrics for the back of the envelope estimation came into beings such as network latency, database queries. I really hope someone of our times can come up with a similar book in the same spirit, but addressing the issues we face nowadays.

136 points by MikeTaylor 16y ago

When I interviewed at Microsoft, they recommended reading this book -- I doubt it helped at all, but it's a great read (as is the sequel) if you haven't read it. There's a real sense of history too, some of the problems illustrate how far we've come: like talking about transferring a whole megabyte several miles as a challenge.

enneff 16y ago
When people ask me how they should prepare for the Google interviews, I always tell them to work through the problems in this book.

michaelcampbell 16y ago

I, by pure luck alone, happened across this book early in my career, and I still go over it from time to time. I will probably die with it in my "keep forever" library.

dguaraglia 16y ago
Ha! Me too! I asked a librarian at my university to fetch me "whatever they had on Perl" (this was my first incursion into the interpreted language world) and the librarian came back to me with this. Imagine my surprise when I started reading the book over the weekend (only then I noticed the title said 'Pearls' not 'Perl'). Forward 10 years, I have a copy in my bookshelf and read a chapter every now and then just to keep myself real. I've completely (and happily) forgotten everything about Perl though.
- rodh257 16y ago
  whenever I'd seen this book mentioned in 'best programming books' lists, on Stack Overflow and the like I'd figured it was a cutely named book to do with Perl and skipped over it.
kragen 16y ago
Me too. I read it, and its sequels, in a bookstore, around 1998. Looks like Bentley's retired, sadly: http://www.research.avayalabs.com/gcm/usa/en-us/people/all/bentley.htm http://www.research.avayalabs.com/gcm/usa/en-us/people/all/b...

deleted 16y ago

[deleted]

noeleon 16y ago

Great book, I reference it all the time. Article made me very hungry though.

ludwigvan 16y ago

Bentley's articles on acm : http://portal.acm.org/author_page.cfm?id=81100143310&query=(Author:81100143310)%20&srt=meta_published_date%20dsc&role=Author&perpage=all&termshow=matchboolean&CFID=18592091&CFTOKEN=68573972 http://portal.acm.org/author_page.cfm?id=81100143310&que... It might require a subscription, though. It seems to contain the articles from the book, starting with those from 1983.

ludwigvan 16y ago
"I cannot describe the excitement I felt when my own first article "Multidimensional Binary Search Trees Used for Associative Searching" was published in September 1975. It received second place in the 1975 Forsythe Student Paper Competition. Back then, original research papers were viewed as within the reach of undergraduate students (truth be told, I tied with a high school student) and of interest to the general ACM community. I wrote my paper (under the guidance of Donald Knuth) explicitly for the Competition; had it not existed, I would not have written it. It remains to this day my most cited research paper. (And because I’m sure that your inquiring mind wants to know, I’ll point out that first place went to a lad by the name of Guy Steele, who I’m betting turned out okay." This excerpt is from his most recent article on acm, "In the realm of insight and creativity".

melling 16y ago

From his book: "It is faster to make a four-inch mirror and then a six-inch mirror than to make a six-inch mirror." This is one of my favorite programming quotes. I haven't seen it used much over the years.

MikeTaylor 16y ago
That one is a quote from Ken Thompson, the inventor of (among much else), Unix and UTF-8. It is quoted in _Programming Pearls_, though -- I think, in the sequel rather than the original.
cafard 15y ago
As noted, a quotation from Ken Thompson. It appears in the chapter "Bumper Sticker Computer Science" in _More Programming Pearls" along with many other fine aphorisms.

kylec 16y ago

I know it's the author's thing, but I've really grown to hate the pictures of food in his articles. I might feel differently if it were done well, but there needs to be more of a reason to include a picture of food than simply wanting a visual break in the article.

hartror 16y ago
I find it strange that is for sure.
deleted 16y ago
[deleted]
sliverstorm 16y ago
I'm sure the author has a reason. I can't help but think that reason is the author is incredibly preoccupied with food.
- MikeTaylor 16y ago
  Yes, it really is that simple. I am preoccupied by food in general and sushi in particular. Sorry that there is no deeper, allegorical reason for the pictures.
  - barrkel 15y ago
    I adblock the images in your articles because I find them highly distracting and slightly repulsive (I'm not a fan of sushi). I did so the first time your articles came up here on HN (and I remarked upon it then), and I had to do so again yesterday, as I've had a new machine since then.
    - MikeTaylor 15y ago
      Nice solution! I'll recommend it to others who complain about the images, thanks for the tip.

jswinghammer 16y ago

I think the most valuable parts of this book for me were the stories that involved solving problems within constraints. If you work with a large enough dataset or management that won't allow you to buy the hardware to just make your problems go away constraints are still a big part of software development.

enneff 16y ago

See also: Jon's great Google Tech Talk "Three Beautiful Quicksorts". http://www.youtube.com/watch?v=aMnn0Jq0J-E http://www.youtube.com/watch?v=aMnn0Jq0J-E

dfan 16y ago

Bentley's book "Writing Efficient Programs" is also really super. Unfortunately, it's been out of print for a long time. If you ever see it, snap it up.

terhechte 16y ago

I love this book. I have it next to my bed and read in there from time to time before I fall asleep. Makes you dream up great algorithms (at least I try to belief that ;)

rdmlx 15y ago

Read it online here: http://www.cs.bell-labs.com/cm/cs/pearls/ http://www.cs.bell-labs.com/cm/cs/pearls/

cygwin98 15y ago

As brilliant as the algorithms listed in the book are, I find them less and less interesting in and out of themselves nowadays. Those data structures and search algorithms have really become basics. I just don't understand why people still blindly worship this book and the way it was and are still trying to replicate it during interviews. If you want to test a developer, don't force them to do bitwise manipulations in C. Why not step up a bit further and try to ask them to apply those data structures and algorithms into a server cluster or a server cloud and see how they come up with a solution. That is more likely the case they will encounter nowadays. All right, enough of rants. Here is my take on this book. This is one of my favorite books. Great things like this book, in the same way as Unix, C and other oldies, can last for a really long time. One thing of the book that intrigued me was the way those old great hackers managed to conquer seemingly impossible problems, despite the severe constraints such as limited memory space, in a extremely resourceful manner. The bit sort in chapter one and the chapter how Ken Thompson squeezed storage space for his chess program are two of my favorite read. The other thing I think may be even more useful is the back of the envelope estimation, which encourages out of the box thinking or street smart (though those kinds of questions got abused and became notorious in technical interviews). Constraints still exist as we begin to attack harder and bigger problems, such as "web-scale" applications. New metrics for the back of the envelope estimation came into beings such as network latency, database queries. I really hope someone of our times can come up with a similar book in the same spirit, but addressing the issues we face nowadays.