Summary:
"The first edition of Programming Pearls was one of the
most influential books I read early in my career, and many of
the insights I first encountered in that book stayed with me
long after I read it. Jon has done a wonderful job of
updating the material. I am very impressed at how fresh the
new examples seem." --Steve McConnell When programmers list
their favorite books, Jon Bentley's collection of programming
pearls is commonly included among the classics. Just as
natural pearls grow from grains of sand that irritate
oysters, programming pearls have grown from real problems
that have irritated real programmers. With origins beyond
solid engineering, in the realm of insight and creativity,
Bentley's pearls offer unique and clever solutions to those
nagging problems. Illustrated by programs designed as much
for fun as for instruction, the book is filled with lucid and
witty descriptions of practical programming techniques and
fundamental design principles. It is not at all surprising
that Programming Pearls has been so highly valued by
programmers at every level of experience.In this revision,
the first in 14 years, Bentley has substantially updated his
essays to reflect current programming methods and
environments. In addition, there are three new essays on /
testing, debugging, and timing / set representations / string
problems All the original programs have been rewritten, and
an equal amount of new code has been generated.
Implementations of all the programs, in C or C++, are now
available on the Web. What remains the same in this new
edition is Bentley's focus on the hard core of programming
problems and his delivery of workable solutions to those
problems. Whether you are new to Bentley's classic or are
revisiting his work for some fresh insight, the book is sure
to make your own list of favorites. 0201657880B04062001 Fourteen years after it was first issued, C++ expert Jon
Bentley reinvents a true classic with the second edition of
his
Programming Pearls. Completely revised and brought
up to date with all new code examples in C and C++, this book
remains an exceptional tutorial for learning to
think like a programmer. The "pearls" in question center not only on choosing the
right algorithms (like binary searches, sorting techniques,
or sparse arrays) but also on showing how to solve problems
effectively. Each chapter frames a particular programming
task--such as sorting numbers, creating anagrams, or counting
the words in a block of text--many drawn from Bentley's
experiences in his long career as a developer. The book
traces the process of arriving at a fast, efficient, and
accurate solution, along with code profiling to discover what
works best. After refining the correct answer, each chapter
enumerates programming principles that you can use on your
own. The author also challenges you to think like an engineer,
and each chapter ends with about a dozen problems to get you
thinking creatively about design issues. (Sidebars on such
historical topics as the first computer solutions to computer
chess, spell-checking, and even architectural design help
create a perspective on successful problem solving and make
for a truly educational and enjoyable tour of how to become a
better programmer.) Bentley also asks the reader to think
analytically about the world with "back of the envelope"
estimation techniques drawn from engineering. Appendices list
the algorithms and code rules covered in the book, plus some
sample solutions. Fans of the first edition of this title will be pleased to
see this favorite computer text brought up to date for
today's faster hardware. Whether you want to improve your
command of algorithms or test your problem-solving skills,
the new version of
Programming Pearl is a challenging, instructive, and
thoroughly entertaining resource.
--Richard Dragan
Topics covered: Programming and
problem-solving tutorial, sorting algorithms, merge sort, bit
vectors, binary searches, program correctness and testing,
improving performance, engineering and problem-solving
techniques, performance estimates, designing for safety,
divide-and-conquer and scanning algorithms, tuning code, tips
for more efficient memory usage, insertion sort, quicksort
algorithms, sparse arrays, searching algorithms, binary
search trees, heaps, priority queues, searching text, and
generating random text. Computer programming has many faces. Fred Brooks paints
the big picture in The Mythical Man Month; his essays underscore the crucial
role of management in large software projects. At a finer grain, Steve
McConnell teaches good programming style in Code Complete. The topics in those books are the
key to good software and the hallmark of the professional programmer.
Unfortunately, though, the workmanlike application of those sound engineering
principles isn't always thrilling -- until the software is completed on time and works
without surprise. About the Book
programming pearls whose origins lie beyond solid
engineering, in the realm of insight and creativity. Just as natural pearls grow
from grains of sand that have irritated oysters, these programming pearls have
grown from real problems that have irritated real programmers. The programs are
fun, and they teach important programming techniques and fundamental design principles.
Most of these essays originally appeared in my
''Programming Pearls'' column in Communications of the Association for Computing
Machinery. They were collected, revised and published as the first edition of
this book in 1986. Twelve of the thirteen pieces in the first edition have
been edited substantially for this edition, and three new columns have been added.
The only background the book assumes is programming
experience in a high-level language. Advanced techniques (such as templates in C++)
show up now and then, but the reader unfamiliar with such topics will be able to
skip to the next section with impunity.
Although each column may be read by itself, there is a
logical grouping to the complete set. Columns 1 through 5 form Part I of the
book. They review programming fundamentals: problem definition, algorithms, data
structures and program verification and testing. Part II is built around the theme of
efficiency, which is sometimes important in itself and is always a fine springboard into
interesting programming problems. Part III applies those techniques to several
substantial problems in sorting, searching and strings.
One hint about reading the essays: don't go too fast. Read
them carefully, one per sitting. Try the problems as they are posed --
some of them look easy until you've butted your head against them for an hour or
two. Afterwards, work hard on the problems at the end of each column: most of
what you learn from this book will come out the end of your pencil as you
scribble down your solutions. If possible, discuss your ideas with friends and
colleagues before peeking at the hints and solutions in the back of the book. The
further reading at the end of each chapter isn't intended as a scholarly
reference list; I've recommended some good books that are an important part of my personal
library.
This book is written for programmers. I hope that the
problems, hints, solutions, and further reading make it useful for individuals. The
book has been used in classes including Algorithms, Program Verification and
Software Engineering. The catalog of algorithms in Appendix 1 is a reference for
practicing programmers, and also shows how the book can be integrated into classes
on algorithms and data structures.
The Code
but I was the only person to see the real code. For this
edition, I have rewritten all the old programs and written about the same amount of
new code. The programs are available at this book's web site. The code includes
much of the scaffolding for testing, debugging and timing the functions. The site
also contains other relevant material. Because so much software is now
available online, a new theme in this edition is how to evaluate and use software
components.
The programs use a terse coding style: short variable
names, few blank lines, and little or no error checking. This is inappropriate in
large software projects, but it is useful to convey the key ideas of algorithms.
Solution 5.1 gives more background on this style. The text includes a few real C
and C++ programs, but most functions are expressed in a pseudocode that takes
less space and avoids inelegant syntax. The notation for i = 0, n) iterates i
from 0 through n-1. In these for loops, left and right
parentheses denote open ranges (which do not include the end values), and
left and right square brackets denote closed ranges (which do include the end
values). The phrase function(i, j) still calls a function with parameters i
and j, and arrayi, j still accesses an array element.
This edition reports the run times of many programs on
''my computer'', a 400MHz Pentium II with 128 megabytes of RAM running Windows NT
4.0. I timed the programs on several other machines, and the book reports the few
substantial differences that I observed. All experiments used the highest
available level of compiler optimization. I encourage you to time the programs on your
machine; I bet that you'll find similar ratios of run times.
To Readers of the First Edition
is, ''This sure looks familiar.'' A few minutes later, I
hope that you'll observe, ''I've never seen that before.''
This version has the same focus as the first edition, but
is set in a larger context. Computing has grown substantially in important
areas such as databases, networking and user interfaces. Most programmers should be
familiar users of such technologies. At the center of each of those areas,
though, is a hard core of programming problems. Those programs remain the theme
of this book. This edition of the book is a slightly larger fish in a much
larger pond.
One section from old Column 4 on implementing binary
search grew into new Column 5 on testing, debugging and timing. Old Column 11 grew and
split into new Columns 12 (on the original problem) and 13 (on set
representations). Old Column 13 described a spelling checker that ran in a 64-kilobyte
address space; it has been deleted, but its heart lives on in Section 13.8. New
Column 15 is about string problems. Many sections have been inserted into the
old columns, and other sections were deleted along the way. With new
problems, new solutions, and four new appendices, this edition of the book is 25
percent longer.
Many of the old case studies in this edition are
unchanged, for their historical interest. A few old stories have been recast in modern
terms.
Acknowledgments for the First Edition
of the ACM column was originally conceived by Peter
Denning and Stuart Lynn. Peter worked diligently within ACM to make the column
possible and recruited me for the job. ACM Headquarters staff, particularly Roz
Steier and Nancy Adriance, have been very supportive as these columns were published
in their original form. I am especially indebted to the ACM for encouraging
publication of the columns in their present form, and to the many CACM
readers who made this expanded version necessary and possible by their
comments on the original columns.
Al Aho, Peter Denning, Mike Garey, David Johnson, Brian
Kernighan, John Linderman, Doug McIlroy and Don Stanat have all read each column with
great care, often under extreme time pressure. I am also grateful for the
particularly helpful comments of Henry Baird, Bill Cleveland, David Gries, Eric
Grosse, Lynn Jelinski, Steve Johnson, Bob Melville, Bob Martin, Arno Penzias,
Marilyn Roper, Chris Van Wyk, Vic Vyssotsky and Pamela Zave. Al Aho, Andrew
Hume, Brian Kernighan, Ravi Sethi, Laura Skinger and Bjarne Stroustrup provided
invaluable help in bookmaking, and West Point cadets in EF 485 field tested
the penultimate draft of the manuscript. Thanks, all.
Acknowledgments for the Second Edition
McConnell, Doug McIlroy, Rob Pike, Howard Trickey and
Chris Van Wyk have all read this edition with great care. I am also grateful for
the particularly helpful comments of Paul Abrahams, Glenda Childress, Eric Grosse,
Ann Martin, Peter McIlroy, Peter Memishian, Sundar Narasimhan, Lisa Ricker,
Dennis Ritchie, Ravi Sethi, Carol Smith, Tom Szymanski and Kentaro Toyama. I
thank Peter Gordon and his colleagues at Addison-Wesley for their help in
preparing this edition. 0201657880P04062001
Amazon.com Review
From the Inside Flap
The columns in this book are about a more glamorous
aspect of the profession:
The pseudocode programs in the first edition of the
book were all implemented,
I hope that your first response as you thumb through
this edition of the book
I am grateful for much support from many people. The
idea for a Communications
Dan Bentley, Russ Cox, Brian Kernighan, Mark Kernighan,
John Linderman, Steve