[P&R#6] Programming Pearls by Jon Bentley - Part 1
Today, we shall commence our reading of Programming Pearls by Jon Bentley.
I've been wanting to pick up Programming Pearls for some time now. It's a classic for many programmers and Steve McConnell - a giant in the software development industry whom I have much respect for - had recommended it in his reading list at the end of his book Code Complete. The book is comprises a series of columns, each describing a pearl of wisdom that had emerged from real problems that have irritated real programmers. Each column teaches important programming techniques and fundamental design principles. In the preface, it is suggested that readers read each column carefully, one per setting, and I shall strive to read one column per day and share my reflections thereafter.
In this post, we shall discuss columns one and two of Part I: Preliminaries.
Column 1: Cracking the Oyster
Jon Bentley begins this column by sharing a conversation he had with a programmer, wherein the programmer had asked: "How do I sort a disk file?"
Here are several of my key takeaways from this column.
The Bitmap Data Structure
I have come across bitmaps in the past, and so this column serves as a timely refresher. The idea is simple. What is a good way to represent a set of nonnegative integers in a small number of bits in memory? The naive solution to the problem would be to store each nonnegative integer in the set as its integer representation. For example, if each integer is represented by 16 bits, a set of 500,000 numbers would occupy 1MB.
If we are only dealing with nonnegative integers across a relatively small range and no duplicates, a better solution would be to represent the set in a file of x bits, where x is the range of numbers that the set can contain. Then, each bit in the i position would be set if and only if the integer i is in the set. A bitmap data structure allows us to represent a dense set over a finite domain when each element occurs at most once and no other data is associated with the element.
Bit representation and bit manipulation can be excellent solutions to problems. I'd love to get more practice on this and to see how it can be applied at work.
Importance of Problem Identification
Jon explains: "Careful analysis of a problem can yield tremendous practical benefits." Indeed, this is something which I seek to follow. As I learn and grow, I find myself being able to refrain from tackling problems immediately but rather, sit back and pause to think about the problem for some time. In my opinion, I think solving programming problems on websites such as LeetCode can be an excellent way to hone this skill, and I hope to do that more. In addition, Jon recommends the book Conceptual Blockbusting by James L. Adams. This is a book that I'd definitely like to pick up soon as I think it can help me in many ways in programming and beyond.
Column 2: Aha! Algorithms
This column talks about problems that seem difficult, but which may have a simple, unexpected solution.
Here are several of my key takeaways from this column.
Signatures
When an equivalence relation defines classes, it is helpful to define a signature suchh taht every item in a class has the same signature and no other item does. An example would be to use signatures to represent anagrams .
A Problem Solver's Perspective
One of the joys from programming is thinking deeply about problems before coming up with any solutions. As Jon mentions, good programmers sit back and wait for insight rather than rushing forward with their first idea. Again, I understand that to be a better programmer, I have to learn how to become better at solving problems. One way I'd like to do this is to develop the habit of starting my day with one LeetCode question.
Conclusion
Tomorrow, I shall discuss column three of part I.
PullAndRebase is a series of posts about technical topics where I pull knowledge from the amazing and wonderful people and resources around me, and rebase/reconsolidate what I've learnt through writing.