Jon Bentley
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.
1 Must have (even if you are experienced).
Programming Pearls is one of the very few books that looks at the problems that we as programmers all have, and keep on having day in and day out. It strives for solutions to problems that are compact, efficient and fast. It questions thinking and makes you think about programming.
The book is comprised of a series of articles focused on a topic which you can read in any order you like. This is one of my favorite programming books, as I always find something 'new' just by browsing it. Unlike some other books on similar topics, the delivery of the information is concise and pallatable. I love this book.
2 Great mental warm-up
With tight schedules it is often easy to forget to ask the question "Why do you want this?" If you help other coders solve problems like I do, you are often approached with a solution that "needs to go faster." This book has paid for itself with just the fact it reminds me to ask this question.
If you are a very experienced programmer you probably won't find much new, but you might find lending it to other people allows you to get more done. Teach a person to fish...
3 Makes you think harder
Programming pearls is a compendium of 15 columns previously published in Communications of the ACM. The columns cover a wide range of topics related to programming: from requirements gathering to performance tuning. The focus is primarily on coding techniques and algorithms.
Each column has been reorganized as a chapter. Chapters usually start with the presentation of a practical problem. Then various solutions are presented and are used as lessons to be learned. The writing style is clear and fun.
Programming Pearls is not a usual book teaching new programming concepts. Although it contains good and sometimes quite novel ideas, the aim of the book is not to teach something new. For example, the search and sort algorithms presented are well-known. The aim is to remind programmers to think hard before starting writing code. The book has great chapter on back-of-the-envelope computation for example which is useful when comparing various solutions. The easy solutions to the column's problems are usually very slow. The `good' solutions are lightening fast but require thinking hard about the problems. I would recommend having a book about algorithms nearby when reading Programming Pearls.
The book is full of little (and some not so little) exercises that are given throughout the chapters. Solutions or hints are given at the end. The exercises usually take a few hours to do properly and are a great resource. Again the emphasis is on making the reader think.
If you consider programming a repetitious activity, Programming Pearls will provoke you into thinking harder about finding elegant solutions. I recommend this book.
4 Back to Basics... Still a Valuable Book
I bought the 2nd edition of the book.
This book takes you to the Basics of Programming: Problem definition, Algorithm design , choosing the correct data structures, Assertions, Performance considerations during Design and coding, Code Tuning, Squeezing the space.
Though the examples are mainly based on searching and sorting and other primitive programming problems, the fundamental concepts and conclusions at the end of each column, are still valuable and hold true as they are 2 decades ago.
The examples and the exercises are challenging and enjoyable. But, don't expect things related to modern programming like related to High Level Programming languages or Databases, this is purely a Basics book focussing on techniques of solving the problems the simplest and the best way.
Some of the gem quotes or conclusions from the book are:
"Coding skill is just one small part of writing correct programs. The majority of the task is problem definition, algorithm design and data structure selection."
"Defining the problem is about ninety percent of the battle"
Characteristics of a good Aircraft(or a good program) - "Simple, few parts, easy to maintain, very strong"
"A designer knows he has arrived perfection not when there is no longer anything to add, but when there is no longer anything to takeaway."
"Good programmers sit back and wait for an insight rather than rushing forward with their first idea"
"A proper view of data does indeed structure programs. Before writing code good programmers thoroughly understand the input, the output and the intermediate data structures around"
5 Wow!
This book is amazing! Its a true classic on algorithims.
I would place this on my list of the top 5 programming books of all time. A must read for every who calls themselves a "programmer".
6 If you're at all experienced, seek other reading.
I only have 2 years of programming experience. I read an awful lot of programming texts. Right now I have 10 books just on C itself. Not to mention all the java and C++ books... My point to saying this is, if you've already read as many books as I have, this book will do nothing for you. I read this book over the weekend and was just astonished with how simple minded it all was. I constantly said "Duh..." throughout the entire book. The pseudo code in this book was the worst I've ever seen. I have never returned a book before except for "Linux Socket Programming". I returned this one today.
The reason I did give this book 3 stars was because I can see it being extremely great for uneducated newbies. It will teach them a great deal and have them think about efficiency and general good programming practices.
I was amazed at all of the great reviews I saw with this book. Everyone that gave a review must of been new to computer programming. I was personally expecting a few more advanced topics such as real C and C++ code. Not the .... pseudo code that this author insisted on using.
Overall, this is a great book for neophytes. If you're new to programming, get this book and give it a good once over. Don't pay attention to his style though... As he stated in the book, it's due to the constraints on space and the fact he didn't want to write a 1200 page book. However, if you have gotten to the point where you've studied advanced data structures and algorithms and know what a linked list is and a binary tree and you understand the concepts behind a heap, priority queues and such, I'd go for another book that is going to advance your knowledge, not bring it back a step.
7 Book of stories
The book wa interesting to me as the collection of stories about programming and problems that programer can meet in his work. the solutions in the book are brilliant.
On the other hand, I don't lik that book treats some very specific problem areas, which are unconnecet mutually. Secondly, there are many things in this book which are completely out of date. I don't want to say that they are completely unimportant, but there are things in modern programming that are much more important and in wich you can improve your program much more.
I read this book, as I said before, as collection of funny and interesting stories.
8 The how-to for profile-based tuning
Bentley's classic, "Programming Pearls", makes an important point, namely that you won't get good performance without careful coding and profile-based tuning. And it's made clearly, concisely and with compelling examples. The choice of language (C), and the choice of problems (those from computer science 101 we all think we know cold) betrays the sophistication of Bentley's analyses.
Suppose, for the sake of argument, that you have a binary search that's holding up your loop. Or your Huffman coding just isn't snappy enough? "How is that possible?", you might say, fresh out of computer-science 201, "Didn't we just prove these algorithms are optimal?" Well yes, asymptotically up to an arbitrary constant multiplier. But this is the real world, and your code needs to go faster. If this sounds like your predicament, pull up a chair and read "Programming Pearls"; if it's not, you might wonder what all the fuss is about.
Next, fire up your favorite hardware (Sparc or x86 or PowerPC), favorite language (Perl, Java, or even C), favorite release of that language, along with your favorite interpreter or compiler (Hotspot or standard? GCC or Visual C++). And you'll need a profiler; might as well treat yourself to a good one if you're serious. Then fire up your code with a representative range realistic test data and observe what happens. Function by function, byte by byte. Then try to be as clever as Bentley in (a) figuring out why, (b) trying a range of alternatives, and (c) making it all go faster with minor tuning. Typically, you'll find a single bottleneck taking an order of magnitude more time than everything else, and work on that. Repeat until fast enough.
As well as this simple, yet surprisingly effective and realistic methodology, Bentley provides a range of concrete tips on making things go faster, from tweaking data structures to unfolding loops (especially precomputing low-order cases) to using accumulators and caching, all with an eye to underlying memory, communication and CPU resources.
Real code that has to run fast, like the code that we write at my current company for signal processing, speech recognition and speech synthesis, typically looks like the end-product of Bentley's refactorings. And it gets that way following exactly the path he lays out: analyze the problem, choose the right algorithm (or the right few to evaluate), and then tune it up using profiling.
"Programming Pearls" is the beginning of the road. You will need to look elsewhere for topics such as compression for memory saving, numerical algorithms, effective concurrency and memory sharing, efficient buffered I/O, garbage collection, and the wide range of dynamic programming and heuristic techniques.
9 wait for insight and THEN start coding
for programming to be effective it is to be divided into 3 stages.in the first stage a clear formulation of the problem and the expected perfomance is laid out.inthe 2nd stage a suitable programming language is selected.in the 3rd stage coding is done.bentley stresses the need for search for the context under which the problem can be solved.it requires a cultivated laziness to outline solution ,which is akin to having an insight.there are no sure fire formulae to get this quickly.
10 Makes a programmer think
I have programmed for 20 years, and there are references in this book older than that. However, this touches on the principles and that can make you think more about how you code and the impact it will have on performance. The writing style of the book can be confusing at times, and that is probably why I would not give this 5 stars. It seems like these were supposed to have been articles in some Computer periodical and put together as a book. If you are looking for a book on programming as a craft this would be a book to own.
11 Advice that will never be outdated
I consider this book a classic. Written in 1986, Bentley engages in some of the best deconstruction and explanation of programming problems that I have ever seen. While it is true that the constraints he discusses are in the distant past, his methods of finding solutions will forever remain part of the programmer's toolbox.
Programmers who have been raised on larger memory units and faster processors tend to ignore concepts such as frugal memory usage and efficient code. When I was a commercial coder, some of the newbies were encountering a bug they could not find. The memory bounds were being exceeded and they simply could not comprehend that they were running out of memory. Forced to fit the data within bounds, it took a great deal of effort to teach them some of the "old-style" techniques of memory management and program efficiency. To prepare for my explanations, I went back and consulted this book to brush up on some of the ideas.
The topics covered are: finding efficient algorithms by solving general problems rather than specific instances, how to verify the correctness of programs, using "back of the envelope calculations" to quickly verify the effectiveness of code, how to squeeze space and some examples of programs. Bentley also refers to the book ,"How To Solve It" by George Polya, a book that should be required reading for all developing programmers.
Bentley is a very good explanatory writer and I can understand why he has received awards for excellence in teaching. Until we develop intelligent robots that will write code for us, the ideas in this book will continue to be useful.
12 Um grande livro!
Eu j‡ havia lido os dois volumes da primeira ediŤ‹o, os quais considero de alto n’vel. A segunda vers‹o est‡ impec‡vel. Tenho usado na preparaŤ‹o de aulas para cursos de graduaŤ‹o e recomendo a sua leitura a todos que se interessam por programaŤ‹o.
13 A classic that will always be readable
This book is timeless because it discusses recurring problem situations with elegance, clarity, and insight. The book is about thinking and problem-solving more than it is about the particular circumstances it discusses.
For instance, the very first chapter ("Cracking the Oyster") would seem to be about the problem of sorting on disk: surely an archaic concern in these days of 1+GB RAM and 100 GB online media on PCs. But that would entirely miss the point, which Bentley clearly summarizes for us in the "principles" section of this chapter:
* "Defining the problem was 90 percent of this battle..."
* Select an appropriate data structure
* Consider multiple-pass algorithms
* A simple design: "a designer knows he has arrived at perfection not when there is no longer anything to add, but when there is no longer anything to take away." -- St. Exupery
This advice might look like a string of old, worn-out chestnuts as set forth above. But within the context of the specific problem, we can see how the design challenges and solutions follow each other, through several iterations, culminating in a pretty solution, nicely illustrating the principles, and suggesting their relevance to other problems, too.
A thoughtful programmer, no matter whether her domain is machine language or OODBMSes, will come away from any chapter in this book full of new ideas and inspiration.
Problems (good ones) after each section encourage the kind of rumination that is necessary to derive the most from this book. Every few years I take it (and its companion, "More Programming Perals") off the shelf and dip into it again, and always come away enlightened.
14 doesn't get much better
this is a thinking man's book. Lots of puzzles to get you thinking about proper data structure design, choice of alrogithm, and optimization. I like how it doesn't 'dumb down' and explain every last detail. Bentley is also an entertaining writer. There are answers to select questions that appear at the end of each chapter.
15 Out of date
This book was useful in 1983, when professional programmers were still coding in assembler, and there was a need to get high-performance software into a small space (like 12K!).
But the world has moved on. Performance will always be a key issue, but the performance problems of the modern world typically do NOT lie in the areas which this author is enthusiastic about: the choice of sort algorithms. A lot of software doesn't do any sorting at all, but retrieves records from a relational DB pre-sorted by the SQL statement. (In this world, the DB vendor will be acutely aware of sort performance!)
But software has grown huge since 1983. Various techniques have evolved to handle this hugeness: structured analysis, modular design, and object-oriented techniques most recently. Most professional software engineers spent a LOT more time defining interfaces (and repairing them, or migrating them) then they will ever spend tweaking a sort algorithm.
After all, as the wise old programmer said, if you're only sorting a dozen things (or even two dozen), a bubble sort is the way to go: easy to code, easy to understand, a little slow, but with machines running at 2 gigahertz it all happens in less than a millisecond anyway.
I think you would be much better advised to read "Rapid Development" by Steve McConnell. That book is an excellent overview of modern software engineering issues and practices, and discusses dozens of essential things not even mentioned in this book (source code control, development cycles, release management, coding to requirements, and so on and on and on!)
16 A classic
One of a few books I'd suggest every programmer read. For two reasons:
o the technical material is well-chosen and well-explained o the writing style is worthy of emulation
Overall, it's worthy of your bookshelf's space.
17 A course in how to think like an experienced programmer
The thirteen columns in this book appeared in the Communications of the ACM between 1983 and 1985. There can't be more than a couple of technical books on computing from that era that are still worth reading. Kernighan & Ritchie's book, "The C Programming Language", is one that springs to mind; this book is definitely another, and will probably outlast K&R as it has almost no ties to existing or past hardware or languages.
What Bentley does in each of these columns is take some part of the field of programming--something that every one of us will have run into at some point in our work--and dig underneath it to reveal the part of the problem that is permanent; that doesn't change from language to language. The first two parts cover problem definition, algorithms, data structures, program verification, and efficiency (performance, code tuning, space tuning); the third part applies the lessons to example pseudocode, looking at sorting, searching, heaps, and an example spellchecker.
Bentley writes clearly and enthusiastically, and the columns are a pleasure to read. But the reason so many people love this book is not for the style, it's for the substance--you can't read this book and not come away a better programmer. Inefficiency, clumsiness, inelegance and obscurity will offend you just a little more after you've read it.
It's hard to pick a favourite piece, but here's one nice example from the algorithm design column that shows how little the speed of your Pentium matters if you don't know what you're doing. Bentley presents a particular problem (the details don't matter) and multiple different ways to solve it, calculating the relationship between problem size and run time for each algorithm. He gives, among others, a cubic algorithm (run time equal to a constant, C, times the cube of the problem size, N--i.e. t ~ CN^3), and a linear algorithm with constant K (t ~ KN). He then implemented them both: the former in fine-tuned FORTRAN on a Cray-1 supercomputer; the latter in BASIC on a Radio Shack TRS-80. The constant factors were as different as they could be, but with increasing problem size the TRS-80 eventually has to catch up--and it does. He gives a table showing the results: for a problem size of 1000, the Cray takes three seconds to the TRS-80's 20 seconds; but for a problem size of 1,000,000, the TRS-80 takes five and a half hours, whereas the Cray would take 95 years.
The book is informative, entertaining, and will painlessly make you a better programmer. What more can you ask?
18 The Pearls Still Glitter After a Decade
Without any doubt, my favorite article in _Communications of the ACM_ in the 1980's was the regular `Programming Pearls' articles by Jon Bentley. When the first edition of these collected gems was published, I read it with great delight. Now, over a decade later, a second edition has been published, containing the same problems with additional modifications and notations. Given the enormous changes in programming since the mid 80's, your first reaction might be that this book is dated and therefore irrelevant. Nothing could be further from the truth.
Elegant solutions to complex programming problems are free from the rot of time. Programming is a thought process largely independent of the notation used to write it down. The solutions are sketched and explained rather than coded, and the solutions are complete. There is a certain mystique about taking a complex problem, finding an initial solution and then refining it down until it kicks some big time. There are some major lessons in program refinement explained in these solutions.
Coding a binary search is covered quite extensively, which may seem like a waste of space, as this problem was solved decades ago. However, that solution took decades to get right, and this is one of those "separates the coders from the key bangers" type of problem. Other problems examined include performance tuning, squeezing space and program correctness. While the improvement in the performance of the hardware has been astounding since these solutions were written, that does not make them obsolete. The complexity of the programs that we now build has risen even faster, so performance and space considerations are just as critical.
Some problems were here at the beginning and will still be here at the end. Even though there may be canned code to handle them, these problems are generic enough that the solutions can be applied elsewhere, so we must learn how to solve them. Understanding these problems and their solutions will give you a fundamental skill set that will serve you well for a long time.
19 Packed with programming wisdom
It's great to see they've come out with an update to this book. The essays in this book are easy to read and touch on many valuable things, such as tuning and optimization of algorithms, using mini languages to provide robust tools, doing back-of-the-envelope calculations, and much more. I have recommended this book to several beginning programmers that I know as an excellent introduction to thinking effectively about the challenges of software engineering.
20 Best book about how to "think" for software engineering
Great book for those who are interested in the thought that goes behind the problem solving skills that are used by great programmers. Does not matter which language or progamming method you use, this book can teach you something. If all programmers read this book, we would have much better software in this world
21 A manual with hacker spirit!
This book goes into what is overlooked and should be taught in "computer science" classes. Instead of focusing on conspiracy-driven "good programming practices" with trite and bloated algorithms, this book focuses on efficient, simple, and creative solutions to problems. This emphasizes on creating solutions that work well on COMPUTERS (albeit dated computers) and not abstract turing machines with no disk or memory limitations! Programming Pearls is easy to read, with lots of little excersizes to get your brain thinking for FUN and PROFIT. This book truly has SLACK.
22 Jon Bentley's small book is itself a pearl...
This slender volume is one of the all-time classics for programmers. Each chapter is an essay from Bentley's wide-ranging programming column dealing with an algorithm, an engineering principle or some more general technique of reasoning. Beginners and experienced professionals alike will be delighted. This is one of the few books for serious programmers which can also be read with pleasure by the non-expert, even by the non-programmer. You'll find the techniques of thinking explained in this book popping up again and again whether you are coding or reading the newspaper. I have owned and loaned I don't know how many copies; nobody ever returns it.
23 A Gem!
There are not many books on advanced computer programming that you actually want to read. Usually, the subject is so dry and full of theory that you have to force yourself. This book is the exception. Bentley's easy-to-read style makes this book a pleasure to read. His theoretical analysis is impeccable, but he presents complex topics in a chatty format that makes you remember the joy you felt the first time you wrote a program, and lets you know he still feels that way
