Programming Pearls, Second Edition

To head off any misconceptions our spelling-challenged readers might have after seeing the title, this book is not about programming in Perl, even though the Perl language is referenced twice. It is a revision of a book published in 1986 that comprised an edited selection of columns Bentley wrote for the journal Communications of ACM. ACM stands for the Association for Computing Machinery, an organization of and for hardware and software professionals and students, formed back before computing technology was as specialized as it is today. As a member in the late 60's and early 70's, I eagerly read Bentley's columns, even though at times I became frustrated at not seeing the solutions he offered until after reading the hints. His first edition of Programming Pearls became an instant classic with examples from the languages C and FORTRAN, but with pseudo-code for the algorithms and solutions so that one could implement in one's favorite language. I used some of the ideas from the book when designing and implementing application access software for relatively large atmospheric science binary data files from a CD-ROM data plate.

Since Bentley works at Bell Labs, he has had the opportunity to consult on many interesting problems, the more interesting of which he uses as examples in this book. There are 15 chapters which he refers to as “columns” (because originally, each was based on a column from CACM). Each includes a discussion of the problem he considers, principles he believes one can derive from that column, and problems for solution and/or further thought. At the end of the book are hints (further questions providing insightful ways of approaching a solution) corresponding to each column's problem set, and outlines of solutions in a section following the hints section. Each column also has a section called “Further Reading”, where he lists books or journal articles related to the column. It was a minor disappointment that there was not a collected bibliography at the end of the book, where all the further reading material was properly referenced with ISBNs where possible.

Finally, some of the chapters have sidebars at the ends; these are well-written narratives with interesting case studies or anecdotes. I was particularly taken by sidebar 13.8, where he presents Doug McIlroy's spelling checker. Fitting a dictionary list of 75,000 English words in the 64KB address space of a PDP-11 computer sounds impossible. Even having Bentley explain the trail of space-compressing techniques used and seeing timings for the 20-year-old “spell” doesn't take away the sense of awe.

To bring the second edition up to date, Bentley uses only C and C++ example programs for his pseudo-code. He rewrote programs for all the pseudo-code in the book, ran them on his 400MHz Pentium II with 128MB of RAM running MS Windows NT 4.0 and presented the timings in the appropriate columns. I would think if he really wanted to be up to date, he would run them on Linux. That might be a good exercise for someone playing with a Linux system who has time on their hands: download Bentley's C and C++ programs, to see how the times compare when run on a similar hardware setup. In Appendix 1, “A Catalog of Algorithms”, Bentley provides college instructors of algorithm courses with ways of presenting the material in his book. Sorting, searching, string algorithms, vector and matrix algorithms, generating pseudo-random integers and numerical algorithms all have one or more sections.

Appendix 2 is a brief, back-of-the-envelope calculation quiz to evaluate one's proficiency at making reasonable numeric guesses. After trying it, I need more practice. Appendix 3 has cost models of time and space; for computers, naturally. Appendix 4, Rules for Code Tuning, comes from his 1982 book Writing Efficient Programs and lists 27 rules. The main categories are space-for-time rules, time-for-space rules, loop rules, logic rules, procedure rules and expression rules. He lists them, then references the section of the book which has examples. Appendix 5, C++ Classes for Searching, is just what it says it is.

This second edition has lost nothing in the rewriting. I only hope a new generation of programmers can appreciate it as much as those of us who learned our approaches to solving programming problems by reading the classic first edition.