Programming Pearls, Second Edition
Author: Jon Bentley
Publisher: ACM Press / Addison Wesley
Price: $24.95 US
Reviewer: Harvey Friedman
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.
Harvey Friedman can be reached via e-mail at email@example.com.
Fast/Flexible Linux OS Recovery
On Demand Now
In this live one-hour webinar, learn how to enhance your existing backup strategies for complete disaster recovery preparedness using Storix System Backup Administrator (SBAdmin), a highly flexible full-system recovery solution for UNIX and Linux systems.
Join Linux Journal's Shawn Powers and David Huffman, President/CEO, Storix, Inc.
Free to Linux Journal readers.Register Now!
- Download "Linux Management with Red Hat Satellite: Measuring Business Impact and ROI"
- Client-Side Performance
- Tibbo Technology's Tibbo Project System
- Sony Settles in Linux Battle
- Peppermint 7 Released
- Libarchive Security Flaw Discovered
- July 2016 Issue of Linux Journal
- The Giant Zero, Part 0.x
- Maru OS Brings Debian to Your Phone
- Profiles and RC Files
With all the industry talk about the benefits of Linux on Power and all the performance advantages offered by its open architecture, you may be considering a move in that direction. If you are thinking about analytics, big data and cloud computing, you would be right to evaluate Power. The idea of using commodity x86 hardware and replacing it every three years is an outdated cost model. It doesn’t consider the total cost of ownership, and it doesn’t consider the advantage of real processing power, high-availability and multithreading like a demon.
This ebook takes a look at some of the practical applications of the Linux on Power platform and ways you might bring all the performance power of this open architecture to bear for your organization. There are no smoke and mirrors here—just hard, cold, empirical evidence provided by independent sources. I also consider some innovative ways Linux on Power will be used in the future.Get the Guide