What do you think?
Rate this book
Programming Pearls
"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, author, Code Complete
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 (1) testing, debugging, and timing; (2) set representations; and (3) 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, this book is sure to make your own list of favorites.
- Steve McConnell, author, Code Complete
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 (1) testing, debugging, and timing; (2) set representations; and (3) 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, this book is sure to make your own list of favorites.
239 pages, Paperback
First published January 1, 1986
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 30 of 91 reviews
January 4, 2016
Indeed Programming Pearls!
Short Summary
Part I: Preliminaries
Column 1: Cracking The Oyster (defining the problem correctly)
Principles: Defining the right problem is critical Problem: How do I sort a large file?
The programmer wanted to sort a large file with limited memory but the critical piece of information was that the numbers are in a specific range (7 digits only) and so the solution was to use a bit vector.
Column 2: AHA! Algorithms (designing the algorithm for the problem)
Principles: Sorting can be used to accomplish tasks that are not related to ordering records for example with grouping anagrams (Problem 3 in the chapter). Binary search is a very important algorithm as well. Good programmers sit and wait for an insight rather than rushing to code. The problems in this chapter are beautiful problems. Find the missing number, rotating an array and finally grouping anagrams. Detailed implementation of each beautiful solution is included.
Column 3: Data Structures Programs (choosing the right data structure)
Principles: Don't write a big program if a little one can do. Don’t write 300 variables if you can use a simple array for example. If you need fancy data structures, use classes. Sometimes solving the general problem for n is easier that targeting a specific case (Inventor’s paradox). Stressing on Data Structures. Data Structures can replace complicated programs.
Column 4: Writing Correct Programs
Don't write programs and fix the bugs later. Sometimes a real understanding of the problem and the solution will lead to correct programs This column studies binary search in details, although it seems trivial, many programmers fail to write binary search correctly from scratch! Use program verification and assertions to make sure your programs are correct!
Column 5: A small matter of programming
Detailed implementation of binary search along with testing it emphasis on using assert.
Part II: Performance
Column 6: Perspective On Performance
If you need to speed up your program, consider first all possible levels and see which level will give you the best speedup but if you need a big speed up you will need to work at each level.
Column 7: The Back of the Envelope
Basic estimation skills are important. Example: struct node { int i; struct node *p; };
will two million such nodes fit in a memory of 128mb?
4 bytes for the int and 4 bytes for the pointer => 2M * 8Bytes = ~ 16MB
Another useful tip is Little’s Law: The average number of things in the system is the product of the average rate at which things leave the system and the average time each one spends in the system.
Example: If you’re waiting in line for a place that holds 60 people, each person spends on average 3 hours at the place then the rate of entering the place is 20 people per hour. If the line has 20 people then the wait will be an hour!
Column 8: Algorithm Design Techniques
This column describes several design techniques used to develop a solution to the problem of find the maximum sum found in any contiguous subarray of the array given. (Hint: Kadane)
The first solution presented was the naive solution which will take n^2. Two techniques are presented at the beginning to reduce the time slightly but not enough to reduce the overall complexity of n^2.
Divide and Conquer is used after that to reduce the complexity (very nice technique here, I should go back to this again and look at it more, page 79). The linear algorithm is presented at the end with a beautiful explanation as well. I should go back to this.
Column 9: Code Tuning
- Profiling can be used to identify the hot spots of the code. Which piece is accessed the most. Once that is known (in the example it was malloc! so caching was implemented) you can find a solution faster.
- Mod in another example was expensive, how to get rid of Mod? There is a nice little trick (k = j + rot); if ( k >= n ) { k -= n; }.
- Another useful thing is to use inline functions for faster access.
- Linear search: for (i = 0; i <= n; i++) { if (a[i] == t) { return i; } return -1. This can be optimized with this magical trick. replace the last element with t. hold = x[n]. x[n] = t. now for (i = 0; ; i++) { …. } now put back x[n] = hold. if i == n return -1 else return i (though shouldn’t we test if hold == t?) from (4.06 nanoseconds to 3.87)
- Further reduction to linear search: (1.70 nanoseconds)
x[n] = t
for (int i = 0; i += 8) {
if (x[i] == t) { break; }
if (x[i+1] == t) { i += 1; break; }
if (x[i+2] == t) { i += 2; break; }
if (x[i+3] == t) { i += 3; break; }
if (x[i+4] == t) { i += 4; break; }
if (x[i+5] == t) { i += 5; break; }
if (x[i+6] == t) { i += 6; break; }
if (x[i+7] == t) { i += 7; break; }
}
- Computing Spherical Distances to find the nearest neighbor example: instead of using longitudes and latitudes, they converted them to coordinates x, y and z and so the distance function became much simpler.
- Binary Search major code tuning
Column 10: Squeezing Space
Do you really need 32 bit for each integer or can you do with 16? Do you really need a matrix representation for the graph? or can a linked list representation work? Many strategies are discussed: recomputing (use a function to test for prime numbers instead of storing all prime numbers) data compression, allocation policies (dynamic allocation instead of static), garbage collection.
Part III: The Product
Column 11: Sorting
Code tuning techniques to speed up insertion sort by a factor of 4 and quick sort by a factor of 2
Column 12: A Sample Problem
Discussion of the problem, given n and m where m < n, choose m random elements from 0 to n - 1. Each element is selected once (no repetition).
Column 13: Searching
A discussion and comparison of five different data structures to represent a set of integers (Sorted Array, Sorted List, Binary Trees, Bins and Bit Vectors).
Column 14: Heaps
Implementation and a discussion of those sexy heaps.
Column 15: Strings of Pearls
First an implementation and a discussion of a hash table. The second part discussed the problem: give a text file, find the longest duplicated substring of characters which is solved by suffix arrays!
Short Summary
Part I: Preliminaries
Column 1: Cracking The Oyster (defining the problem correctly)
Principles: Defining the right problem is critical Problem: How do I sort a large file?
The programmer wanted to sort a large file with limited memory but the critical piece of information was that the numbers are in a specific range (7 digits only) and so the solution was to use a bit vector.
Column 2: AHA! Algorithms (designing the algorithm for the problem)
Principles: Sorting can be used to accomplish tasks that are not related to ordering records for example with grouping anagrams (Problem 3 in the chapter). Binary search is a very important algorithm as well. Good programmers sit and wait for an insight rather than rushing to code. The problems in this chapter are beautiful problems. Find the missing number, rotating an array and finally grouping anagrams. Detailed implementation of each beautiful solution is included.
Column 3: Data Structures Programs (choosing the right data structure)
Principles: Don't write a big program if a little one can do. Don’t write 300 variables if you can use a simple array for example. If you need fancy data structures, use classes. Sometimes solving the general problem for n is easier that targeting a specific case (Inventor’s paradox). Stressing on Data Structures. Data Structures can replace complicated programs.
Column 4: Writing Correct Programs
Don't write programs and fix the bugs later. Sometimes a real understanding of the problem and the solution will lead to correct programs This column studies binary search in details, although it seems trivial, many programmers fail to write binary search correctly from scratch! Use program verification and assertions to make sure your programs are correct!
Column 5: A small matter of programming
Detailed implementation of binary search along with testing it emphasis on using assert.
Part II: Performance
Column 6: Perspective On Performance
If you need to speed up your program, consider first all possible levels and see which level will give you the best speedup but if you need a big speed up you will need to work at each level.
Column 7: The Back of the Envelope
Basic estimation skills are important. Example: struct node { int i; struct node *p; };
will two million such nodes fit in a memory of 128mb?
4 bytes for the int and 4 bytes for the pointer => 2M * 8Bytes = ~ 16MB
Another useful tip is Little’s Law: The average number of things in the system is the product of the average rate at which things leave the system and the average time each one spends in the system.
Example: If you’re waiting in line for a place that holds 60 people, each person spends on average 3 hours at the place then the rate of entering the place is 20 people per hour. If the line has 20 people then the wait will be an hour!
Column 8: Algorithm Design Techniques
This column describes several design techniques used to develop a solution to the problem of find the maximum sum found in any contiguous subarray of the array given. (Hint: Kadane)
The first solution presented was the naive solution which will take n^2. Two techniques are presented at the beginning to reduce the time slightly but not enough to reduce the overall complexity of n^2.
Divide and Conquer is used after that to reduce the complexity (very nice technique here, I should go back to this again and look at it more, page 79). The linear algorithm is presented at the end with a beautiful explanation as well. I should go back to this.
Column 9: Code Tuning
- Profiling can be used to identify the hot spots of the code. Which piece is accessed the most. Once that is known (in the example it was malloc! so caching was implemented) you can find a solution faster.
- Mod in another example was expensive, how to get rid of Mod? There is a nice little trick (k = j + rot); if ( k >= n ) { k -= n; }.
- Another useful thing is to use inline functions for faster access.
- Linear search: for (i = 0; i <= n; i++) { if (a[i] == t) { return i; } return -1. This can be optimized with this magical trick. replace the last element with t. hold = x[n]. x[n] = t. now for (i = 0; ; i++) { …. } now put back x[n] = hold. if i == n return -1 else return i (though shouldn’t we test if hold == t?) from (4.06 nanoseconds to 3.87)
- Further reduction to linear search: (1.70 nanoseconds)
x[n] = t
for (int i = 0; i += 8) {
if (x[i] == t) { break; }
if (x[i+1] == t) { i += 1; break; }
if (x[i+2] == t) { i += 2; break; }
if (x[i+3] == t) { i += 3; break; }
if (x[i+4] == t) { i += 4; break; }
if (x[i+5] == t) { i += 5; break; }
if (x[i+6] == t) { i += 6; break; }
if (x[i+7] == t) { i += 7; break; }
}
- Computing Spherical Distances to find the nearest neighbor example: instead of using longitudes and latitudes, they converted them to coordinates x, y and z and so the distance function became much simpler.
- Binary Search major code tuning
Column 10: Squeezing Space
Do you really need 32 bit for each integer or can you do with 16? Do you really need a matrix representation for the graph? or can a linked list representation work? Many strategies are discussed: recomputing (use a function to test for prime numbers instead of storing all prime numbers) data compression, allocation policies (dynamic allocation instead of static), garbage collection.
Part III: The Product
Column 11: Sorting
Code tuning techniques to speed up insertion sort by a factor of 4 and quick sort by a factor of 2
Column 12: A Sample Problem
Discussion of the problem, given n and m where m < n, choose m random elements from 0 to n - 1. Each element is selected once (no repetition).
Column 13: Searching
A discussion and comparison of five different data structures to represent a set of integers (Sorted Array, Sorted List, Binary Trees, Bins and Bit Vectors).
Column 14: Heaps
Implementation and a discussion of those sexy heaps.
Column 15: Strings of Pearls
First an implementation and a discussion of a hash table. The second part discussed the problem: give a text file, find the longest duplicated substring of characters which is solved by suffix arrays!
August 15, 2012
With the exception of some painfully out of date examples, this book is probably the best practical programming/algorithms book I've read.
The examples aren't untrue, they're just not intuitive to a modern reader. It's nothing that ruins the book, but examples have things that seem slightly silly today like "big" computers with just a meg or two of memory available. Or the practice problem that asks you how you send an image from one place to another. (I first took that to mean I needed to implement TCP/IP, but the sample solution was, no kidding, carrier pidgeons. Which is actually kind of brilliant but also completely unneeded in a world with internet.)
So, if you're a programmer, read it (with some historical context in mind).
The examples aren't untrue, they're just not intuitive to a modern reader. It's nothing that ruins the book, but examples have things that seem slightly silly today like "big" computers with just a meg or two of memory available. Or the practice problem that asks you how you send an image from one place to another. (I first took that to mean I needed to implement TCP/IP, but the sample solution was, no kidding, carrier pidgeons. Which is actually kind of brilliant but also completely unneeded in a world with internet.)
So, if you're a programmer, read it (with some historical context in mind).
November 22, 2013
A good selection of interesting algorithms explained without the terseness that some other books can get into. I felt it is a bit antiquated with all the algorithms written in low level C. I'm not sure that some of the optimizations the author is proposing (manual loop unrolling, moving assignment out of a loop, etc) are still relevant due to the advances in compilers that can do such optimizations automatically while leaving the source code untainted by 'optimizations'. Nevertheless, there is a good selection of interesting algorithms, problem sets, and solutions. The length of the book is also very approachable compared to many other ones since it's only around 200 pages.
January 2, 2018
There should be more programming books like this. It's like an algorithms and data structures text book, but written in such a way that it's actually pleasant to read. The writing is great, the examples are clear, and the book challenges you to solve things incrementally rather than giving you the answer right away.
With most other professions, novices spend a lot of time studying the work of those who came before them: e.g. physicists read physics papers, artists imitate master artists, historians study the existing historiography. But in the field of software, it is very rare for a programmer to dedicate time to studying code written by other programmers. Instead, we all reinvent the wheel, poorly. Books like this provide a gentle and enjoyable way to study how other programmers solve problems, and for that, the book deserves a lot of praise.
The main downsides to the book are that it's a bit dated now. The basic principles the book teaches are largely still correct, but not all the practices have aged well. The obsession with tiny perf optimizations, such as loop unrolling and inlining functions, are unnecessary for 99.9% of programmers today, and perhaps actively harmful, as they are better handled by the compiler or VM anyway.
As always, I jot down my favorite quotes from every book I read:
"We are surrounded by strings. Strings of bits make integers and floating-point numbers. Strings of digits make telephone numbers, and strings of characters make words. Long strings of characters make web pages, and longer strings yet make books. Extremely long strings represented by the letters A, C, G and T are in geneticists' databases and deep inside the cells of many readers of this book."
With most other professions, novices spend a lot of time studying the work of those who came before them: e.g. physicists read physics papers, artists imitate master artists, historians study the existing historiography. But in the field of software, it is very rare for a programmer to dedicate time to studying code written by other programmers. Instead, we all reinvent the wheel, poorly. Books like this provide a gentle and enjoyable way to study how other programmers solve problems, and for that, the book deserves a lot of praise.
The main downsides to the book are that it's a bit dated now. The basic principles the book teaches are largely still correct, but not all the practices have aged well. The obsession with tiny perf optimizations, such as loop unrolling and inlining functions, are unnecessary for 99.9% of programmers today, and perhaps actively harmful, as they are better handled by the compiler or VM anyway.
As always, I jot down my favorite quotes from every book I read:
"We are surrounded by strings. Strings of bits make integers and floating-point numbers. Strings of digits make telephone numbers, and strings of characters make words. Long strings of characters make web pages, and longer strings yet make books. Extremely long strings represented by the letters A, C, G and T are in geneticists' databases and deep inside the cells of many readers of this book."
July 26, 2016
Unlike most other books on programming, this one focuses on fundamental and generic problems, not the easy things, toy problems or technical things.
The book teaches through a thorough discussion of solutions of several problems coming from several domains (algorithms, data structures, probability theory, ...). Some of the things - binary search being the most obvious example - look easy, but the sad truth is that many people can't write a correct implementation, not even speaking about effectivity. There's a discussion of effective implementation of data structures with respect to things like efficiency of storage and efficiency with respect to the speed of memory access, again with many examples.
I'd consider this one of the best programming books I've ever seen.
The book teaches through a thorough discussion of solutions of several problems coming from several domains (algorithms, data structures, probability theory, ...). Some of the things - binary search being the most obvious example - look easy, but the sad truth is that many people can't write a correct implementation, not even speaking about effectivity. There's a discussion of effective implementation of data structures with respect to things like efficiency of storage and efficiency with respect to the speed of memory access, again with many examples.
I'd consider this one of the best programming books I've ever seen.
September 17, 2008
_Programming Pearls_ is a gem. The "pearls" are short essays on a particular topic of programming, grouped together by theme: algorithms, data structures, correctness, implementation, performance, code tuning, etc. The essays are concise and focused, with plenty of code examples. Some of the topics may strike today's programmer as quaintly academic exercies. ("Surely nobody writes Quick Sort anymore!") But the lessons that Bentley extracts from them are always valuable.
The second edition has been updated to reflect current programming practices, with a few oversights. We speak of "templates" today instead of "form letter generators", and "unit tests" instead of "scaffolding". If you aren't a C programmer or possessed of an interest in compiler design you won't learn much from the sections on code tuning. But even after years of all Java, all the time, I learned a lot from his approach.
This book should be on every programmer's shelf!
The second edition has been updated to reflect current programming practices, with a few oversights. We speak of "templates" today instead of "form letter generators", and "unit tests" instead of "scaffolding". If you aren't a C programmer or possessed of an interest in compiler design you won't learn much from the sections on code tuning. But even after years of all Java, all the time, I learned a lot from his approach.
This book should be on every programmer's shelf!
May 20, 2016
Finished the book while preparing for programming interviews. Great delivery of valuable advice in practical use of algorithms. Will recommend it to anyone interested in programming at the cost of being obnoxious.
December 24, 2012
I'm going to complete all of the exercises in this book one day, at which point I will probably no longer be able to carry on conversation with humans.
February 2, 2021
Programming Pearls is basically a collection of tips, tricks and solutions to interesting algorithmic problems. Each chapter, called 'columns' in the book, has a specific theme with a dive into a couple of challenges and how to solve them. Often, solutions are 'built up' over the course of the column, with a less efficient solution shown first, then with some adjustments, a more efficient technique is shown.
There is a section of 'principles' at the end of each column. These are fantastic points that condensed key points that the author made throughout the chapter. I always looked forward to reading these.
The usage of C throughout the examples made some of the code a bit hard to follow, as I have not used C since my uni days! However, code snippets are short and well explained.
The book also provides heaps of problems for the reader to solve. I think this would've been great while I was studying, but I think it will be useful to refer back to when refreshing myself on Computer Science principles.
Overall, a very solid book for algorithmic thinking and programming. Due to the fact that it lacked a bit of take away knowledge for modern software development, I will only rate it 3 stars.
There is a section of 'principles' at the end of each column. These are fantastic points that condensed key points that the author made throughout the chapter. I always looked forward to reading these.
The usage of C throughout the examples made some of the code a bit hard to follow, as I have not used C since my uni days! However, code snippets are short and well explained.
The book also provides heaps of problems for the reader to solve. I think this would've been great while I was studying, but I think it will be useful to refer back to when refreshing myself on Computer Science principles.
Overall, a very solid book for algorithmic thinking and programming. Due to the fact that it lacked a bit of take away knowledge for modern software development, I will only rate it 3 stars.
October 20, 2019
Great way to push yourself, with some good narrative context (i.e. not just a bunch of lifeless problems to solve).
July 11, 2020
A classic that I will have no qualms about recommending to bootcamp grads and interviewees refreshing for algorithms.
May 5, 2015
A good look at some ways to write efficient code. It discusses various algorithms and techniques that can increase performance or reduce memory requirements. One of the problems with the book is that, being an older book, some of the content is less relevant today. You can get most of the algorithms as part of any programming language library, though the book does provide you the information to understand the trade-offs. A better font for the book and C++-style examples (at least for me) would also have helped.
January 26, 2012
...and this book certainly deserves a place among them.
Targeted to experienced programmers, Programming Pearls reminds how important it is to think hard before approaching any problem, and to strive for elegance and efficiency.
Even years after its publication date, this book is full of insightful advice about programming as an art.
It is the best proof that programming languages may become obsolete, but good ideas never get old.
February 28, 2013
AFter reading this book, you would start to think in terms bit and bytes.
December 7, 2015
Super helpful to review data structures, algorithms and problem solving.
Want to read
December 16, 20221. Sắp xếp 10 triệu số
--> Dùng 1 mảng bit, số nào xuất hiện thì phần tử của số đó trong mảng sẽ có giá trị bằng 1, ngược lại thì = 0
/* Bước 1: Gán tất cả các phần tử trong mảng = 0 */
for i = [0, n)
bit[i] = 0
/* Bước 2: Đọc file ra, số nào xuất hiện thì gán giá trị của phần tử có thứ tự số đó trong mảng bit = 1 */
for each i in the input file
bit[i] = 1
/* Bước 3: Chạy vòng lặp qua mảng bit, nếu phần tử nào = 1 thì in ra output file */
for i = [0, n)
if bit[i] == 1
write i on the output file
- There were two reasons that the reduction in space led to a reduction in time: less data to process means less time to process it, and keeping data in main memory rather than on disk avoids the overhead of disk accesses
2. Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn't in the file (and there must be at least one missing — why?). How would you solve this problem with ample quantities of main memory? How would you solve it if you could use several external "scratch" files but only a few hundred bytes of main memory?
--> Answer: It is helpful to view this binary search in terms of the 32 bits that represent each integer. In the first pass of the algorithm we read the (at most) four billion input integers and write those with a leading zero bit to one sequential file and those with a leading one bit to another file.
One of those two files contains at most two billion integers, so we next use that file as the current input and repeat the probe process, but this time on the second bit. If the original input file contains n elements, the first pass will read n integers, the second pass at most n/2, the third pass at most rc/4, and so on, so the total running time is proportional to n. The missing integer could be found by sorting the file and then scanning, but that would require time proportional to n log n. This problem was given as an exam by Ed Reingold at the University of Illinois.
After each pass your next pass will be on the smaller of the two lists you've compiled.
At some point, you MUST encounter an empty list and this will determine your number. For example let's just use 3 bit numbers.
000
001
110
100
111
after the first pass we have
000
001
---
110
100
111
Then we look at the 2nd bits in the first list because it is smaller than (or equal to) the second. We would split them into
000
001
---
empty list
notice how the file that would start with 01 is empty, this means that there are no numbers that start with 01 so 010 and 011 are missing.
The reason we must eventually have a missing list is because we are choosing the smaller list for our next pass each time.
--> Dùng 1 mảng bit, số nào xuất hiện thì phần tử của số đó trong mảng sẽ có giá trị bằng 1, ngược lại thì = 0
/* Bước 1: Gán tất cả các phần tử trong mảng = 0 */
for i = [0, n)
bit[i] = 0
/* Bước 2: Đọc file ra, số nào xuất hiện thì gán giá trị của phần tử có thứ tự số đó trong mảng bit = 1 */
for each i in the input file
bit[i] = 1
/* Bước 3: Chạy vòng lặp qua mảng bit, nếu phần tử nào = 1 thì in ra output file */
for i = [0, n)
if bit[i] == 1
write i on the output file
- There were two reasons that the reduction in space led to a reduction in time: less data to process means less time to process it, and keeping data in main memory rather than on disk avoids the overhead of disk accesses
2. Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn't in the file (and there must be at least one missing — why?). How would you solve this problem with ample quantities of main memory? How would you solve it if you could use several external "scratch" files but only a few hundred bytes of main memory?
--> Answer: It is helpful to view this binary search in terms of the 32 bits that represent each integer. In the first pass of the algorithm we read the (at most) four billion input integers and write those with a leading zero bit to one sequential file and those with a leading one bit to another file.
One of those two files contains at most two billion integers, so we next use that file as the current input and repeat the probe process, but this time on the second bit. If the original input file contains n elements, the first pass will read n integers, the second pass at most n/2, the third pass at most rc/4, and so on, so the total running time is proportional to n. The missing integer could be found by sorting the file and then scanning, but that would require time proportional to n log n. This problem was given as an exam by Ed Reingold at the University of Illinois.
After each pass your next pass will be on the smaller of the two lists you've compiled.
At some point, you MUST encounter an empty list and this will determine your number. For example let's just use 3 bit numbers.
000
001
110
100
111
after the first pass we have
000
001
---
110
100
111
Then we look at the 2nd bits in the first list because it is smaller than (or equal to) the second. We would split them into
000
001
---
empty list
notice how the file that would start with 01 is empty, this means that there are no numbers that start with 01 so 010 and 011 are missing.
The reason we must eventually have a missing list is because we are choosing the smaller list for our next pass each time.
July 12, 2023
While this book is well written - it ultimately does not deliver on it's promise.
It is:
* A collection of fun math problems for programmers to gnaw on
* A decent reference for algorithms you should know, but never have to write (quick sort, heaps, etc)
* Slivers of high-level discussion of how to write code ("use libraries", "keep things simple")
What it is not:
* An efficient resource for furthering one's ability to write 'real code' in the 21st century
Toying with the challenges is good fun for folks like myself: who enjoy code-golf and remember Algo-101 fondly. However, I did not pickup this book to rewrite binary-search, I bought it because I am trying to find texts that explain programming methodology.
On coding-interviews, you might be forced to lean on some of the resources here - but rarely will more knowledge of how merge-sort works actually help you make a website, solve a business problem, or code a game. Your dusty memories from Uni (+ some googling) will better serve you there.
It feels far more important for me to learn: how best to structure code, what kinds of approaches work best for different problems, how to prevent codebases from becoming tangled, etc - this book provides none of that. Simply functions that "take in 's' and 'x' and return a the longest substring that..." - you know the kind. Most chapters come with this mathematician's excuse: "You should probably just use the built-in C++ sort. And you probably shouldn't name your variables 1 character." - so at least it is self aware.
Buy this book for when you want to whittle away some afternoons reimplementing standard library algorithms, in your favorite language, for the pure joy of simple problems. You will 'stretch that coding muscle', and have fun doing so.
But if you are looking for content that is directly applicable to your hobbies, or your career, look elsewhere.
As for myself - I already have a glut of fun little algorithms I want to write: those necessitated by my day-job, or my side-projects. 'Knowing how hashing works' is not my issue. Making sure I write readable, scalable, sensible code is. And Programming Pearls has little to offer on that.
It is:
* A collection of fun math problems for programmers to gnaw on
* A decent reference for algorithms you should know, but never have to write (quick sort, heaps, etc)
* Slivers of high-level discussion of how to write code ("use libraries", "keep things simple")
What it is not:
* An efficient resource for furthering one's ability to write 'real code' in the 21st century
Toying with the challenges is good fun for folks like myself: who enjoy code-golf and remember Algo-101 fondly. However, I did not pickup this book to rewrite binary-search, I bought it because I am trying to find texts that explain programming methodology.
On coding-interviews, you might be forced to lean on some of the resources here - but rarely will more knowledge of how merge-sort works actually help you make a website, solve a business problem, or code a game. Your dusty memories from Uni (+ some googling) will better serve you there.
It feels far more important for me to learn: how best to structure code, what kinds of approaches work best for different problems, how to prevent codebases from becoming tangled, etc - this book provides none of that. Simply functions that "take in 's' and 'x' and return a the longest substring that..." - you know the kind. Most chapters come with this mathematician's excuse: "You should probably just use the built-in C++ sort. And you probably shouldn't name your variables 1 character." - so at least it is self aware.
Buy this book for when you want to whittle away some afternoons reimplementing standard library algorithms, in your favorite language, for the pure joy of simple problems. You will 'stretch that coding muscle', and have fun doing so.
But if you are looking for content that is directly applicable to your hobbies, or your career, look elsewhere.
As for myself - I already have a glut of fun little algorithms I want to write: those necessitated by my day-job, or my side-projects. 'Knowing how hashing works' is not my issue. Making sure I write readable, scalable, sensible code is. And Programming Pearls has little to offer on that.
August 19, 2018
An interesting blast from the past. I think the big principles outlined in this book still apply today, but the examples are outdated. I read the first edition, not sure about the second. The principles are nicely summarised at the end of each chapter, following which some practice problems are provided. The author uses so many different languages it gets a little confusing at times though. So, what I took away from this book was not the technicalities, but rather key ideas that make one a better programmer. Among the pearls I found some gems:
“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.” – Antoine de Saint-Exupéry
“Binary search is a solution that looks for problems”
“Don’t write a big program when a little one will do.”
“The more general problem may be easier to solve” – Polya, on the Inventor’s Paradox in his book How To Solve It
“Representation is the essence of programming” – Fred Brooks, in Chapter 9 of Mythical Man Month
“Resist those foul urges to “just change it until it works””
“The cheapest, fastest and most reliable components of a computer system are those that aren’t there.” – Gordon Bell
“Above all, don’t forget common sense”
“Everything should be made as simple as possible but no simpler.” – Einstein
“Premature optimisation is the root of much programming evil” – Don Knuth
“Save concern for efficiency for when it matters”
“One part of a programmer’s job is solving today’s problem. Another, and perhaps more important, part of the job is to prepare for solving tomorrow’s problems.”
“Too many programmers jump too quickly to “the” solution to their problem; they think for a minute and code for a day rather than think for an hour and coding for an hour.”
“There remains always something to do; with sufficient study and penetration, we could improve any solution, and, in any case, we can always improve our understanding of the solution.” – Polya
“Spelling misteaks irritate readers.”
"Program into a language, not in it." - David Gries
“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.” – Antoine de Saint-Exupéry
“Binary search is a solution that looks for problems”
“Don’t write a big program when a little one will do.”
“The more general problem may be easier to solve” – Polya, on the Inventor’s Paradox in his book How To Solve It
“Representation is the essence of programming” – Fred Brooks, in Chapter 9 of Mythical Man Month
“Resist those foul urges to “just change it until it works””
“The cheapest, fastest and most reliable components of a computer system are those that aren’t there.” – Gordon Bell
“Above all, don’t forget common sense”
“Everything should be made as simple as possible but no simpler.” – Einstein
“Premature optimisation is the root of much programming evil” – Don Knuth
“Save concern for efficiency for when it matters”
“One part of a programmer’s job is solving today’s problem. Another, and perhaps more important, part of the job is to prepare for solving tomorrow’s problems.”
“Too many programmers jump too quickly to “the” solution to their problem; they think for a minute and code for a day rather than think for an hour and coding for an hour.”
“There remains always something to do; with sufficient study and penetration, we could improve any solution, and, in any case, we can always improve our understanding of the solution.” – Polya
“Spelling misteaks irritate readers.”
"Program into a language, not in it." - David Gries
October 27, 2020
It's not exactly an algorithm book.
It's not an introductory book either.
It's like a mechanical book on classical algorithms from very low level programming point of view.
It goes into details of how to build basic data structures with c code and c++ template, therefore, this book obviously needs basic c knowledge, but anyone who have already code in c most likely have read other algorithm textbooks, and almost certainly have already known all the stuff this book presented, that's awkward, isn't it?
Anyway, it is by no means a useless book, quite the opposite, its very intuitive, but sometimes too advanced and in the meantime too succinct and lack of further low level details(assumes reader already have c and maybe a bit assembly knowledge).
In my opinion, this book is for pros. Every chapter is somehow a takeaway from a collection of classical algorithm books, therefore makes it standing at a higher ground discussing each topic from pro's eyes, guess that's why its called programming pearls.
But in the end, I did picked up many useful insights, regardless of my hard to tell real level programming background. Might as well come back to this book for the pearls in the future.
It's not an introductory book either.
It's like a mechanical book on classical algorithms from very low level programming point of view.
It goes into details of how to build basic data structures with c code and c++ template, therefore, this book obviously needs basic c knowledge, but anyone who have already code in c most likely have read other algorithm textbooks, and almost certainly have already known all the stuff this book presented, that's awkward, isn't it?
Anyway, it is by no means a useless book, quite the opposite, its very intuitive, but sometimes too advanced and in the meantime too succinct and lack of further low level details(assumes reader already have c and maybe a bit assembly knowledge).
In my opinion, this book is for pros. Every chapter is somehow a takeaway from a collection of classical algorithm books, therefore makes it standing at a higher ground discussing each topic from pro's eyes, guess that's why its called programming pearls.
But in the end, I did picked up many useful insights, regardless of my hard to tell real level programming background. Might as well come back to this book for the pearls in the future.
January 28, 2023
Kinda interesting book, but reading it in 2023 is a bit difficult because a lot of problems are mostly outdated. Not many developers nowadays have limitations like a couple of kilobytes of memory available. So, from this point of view, this book can be considered as an introduction to programming history.
Anyway, it's an interesting and fun read and can be especially useful during an interview preparation
Anyway, it's an interesting and fun read and can be especially useful during an interview preparation
June 14, 2017
I really like the way this book presents everything as a story. It has a bit of an old-world charm to it, given that a lot of war stories are from bell-labs and so on, and in a time where programming languages weren't as advanced as today. But the way it approaches algorithm design is timeless and inspiring. Also a perfectly sized book to read on commutes.
Read
February 19, 2020I skimmed quite a bit of this. It's not the first time I read the book but I like to reference it from time to time to remind myself to think deeper than the package I'm using implement a solution for any given problem. I feel like this book would be especially good for folks that write searching and sorting functions a lot. ^_^
October 18, 2022
Guiding you through a large number of different problems, all relevant to day-to-day programming, this book walks you through both pitfalls and different solutions for different contexts. It’s incredibly in-depth without becoming a textbook and it definitely delivers on its title promise; within these pages are some real programming gems.
December 4, 2022
Very enjoyable (for a text mostly on algorithms and data structures). Some considerations are pretty dated by now, of course, but I still found a lot of the material and problems interesting. There's example code to be found online (C and very C-ish C++), but it's the opposite of clean.
March 2, 2017
this book is probably the best algorithmic book I have ever read.
March 18, 2017
A must read although it is a bit old.
December 24, 2017
Lots of good stories about famous coders stuffed with interesting problems which I'll try to solve when I re-read it.
April 18, 2018
A bit outdated
October 7, 2018
Jon L. Bentley is king.
February 14, 2019
First two chapters were great prep for interviews.
Displaying 1 - 30 of 91 reviews