Jon Aquino's Mental Garden

Engineering beautiful software jon aquino labs | personal blog

Thursday, February 03, 2011

An Ultracompact Abridgement of "Programming Pearls"

Below is an extreme abridgment of Jon Bentley's popular algorithms book, Programming Pearls. A sentence has been selected from each of its 15 chapters. Interested readers are referred to Bentley's original 173-page work.

Programming folklore and theory abound with time-space tradeoffs; it has been my experience more frequently, though, that reducing a program's space requirements also reduces its run time. Binary search in a sorted table is remarkably efficient and can be used in main memory or on disk; its only drawback is that the entire table must be known and sorted in advance. Let the data structure the program: data can structure a program by replacing complicated code with an appropriate data structure. Deciding which assertions to include in real software is an art that comes only with practice. And write automated tests: the tests would have been dreadfully boring (and therefore error prone) by hand, but they use an insignificant amount of computer time.

When performance problems can't be sidestepped, thinking about design levels can help focus a programmer's effort. And the following reminders can be helpful in making back-of-the-envelope calculations: two answers are better than one; do quick checks; use rules of thumb. Important algorithm design techniques include saving state to avoid recomputation, preprocessing information into data structures, and divide-and-conquer. Code tuning locates the expensive parts of an existing program and then makes little changes to improve its speed; for example, exploiting common cases, exploiting an algebraic identity, and collapsing a procedure hierarchy. We then survey a few important techniques for reducing space: recomputing, sparse structures, information theory, and allocation policies.

The C library qsort is easy and relatively fast; it is slower than handmade Quicksorts only because its general and flexible interface uses a function call for each comparison. Explore the design space: knowledge of the literature is invaluable at this stage of the design process. The importance of space: finely tuned linked lists do half the work of arrays but take twice the time. Why? Arrays use half as much memory per element, and access memory sequentially. Heaps are a data structure that we use for sorting and priority queues. Finally, we examine important data structures used for representing strings: hashing, balanced trees, and suffix arrays.


Post a Comment

<< Home