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 firstname.lastname@example.org.
Practical Task Scheduling Deployment
July 20, 2016 12:00 pm CDT
One of the best things about the UNIX environment (aside from being stable and efficient) is the vast array of software tools available to help you do your job. Traditionally, a UNIX tool does only one thing, but does that one thing very well. For example, grep is very easy to use and can search vast amounts of data quickly. The find tool can find a particular file or files based on all kinds of criteria. It's pretty easy to string these tools together to build even more powerful tools, such as a tool that finds all of the .log files in the /home directory and searches each one for a particular entry. This erector-set mentality allows UNIX system administrators to seem to always have the right tool for the job.
Cron traditionally has been considered another such a tool for job scheduling, but is it enough? This webinar considers that very question. The first part builds on a previous Geek Guide, Beyond Cron, and briefly describes how to know when it might be time to consider upgrading your job scheduling infrastructure. The second part presents an actual planning and implementation framework.
Join Linux Journal's Mike Diehl and Pat Cameron of Help Systems.
Free to Linux Journal readers.Register Now!
- SUSE LLC's SUSE Manager
- My +1 Sword of Productivity
- Murat Yener and Onur Dundar's Expert Android Studio (Wrox)
- Managing Linux Using Puppet
- Non-Linux FOSS: Caffeine!
- Tech Tip: Really Simple HTTP Server with Python
- Doing for User Space What We Did for Kernel Space
- Parsing an RSS News Feed with a Bash Script
- Rogue Wave Software's Zend Server
- SuperTuxKart 0.9.2 Released
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