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 of 1 review
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.
Displaying 1 of 1 review