These techniques are typical. We can often simplify a program by asking, "What problem do we really need to solve?" or, "Is there a better function to solve that problem?"
These techniques are typical. We can often simplify a program by asking, "What problem do we really need to solve?" or, "Is there a better function to solve that problem?"
data structures are frozen algorithms." And if we freeze the Quicksort algorithm, we get the data structure of a binary search tree. Knuth's publication presents that structure and analyzes its runtime with a recurrence relation similar to that for Quicksort.
data structures are frozen algorithms." And if we freeze the Quicksort algorithm, we get the data structure of a binary search tree. Knuth's publication presents that structure and analyzes its runtime with a recurrence relation similar to that for Quicksort.
Almost four decades of computer programming have left me with deep respect for the difficulty of the craft (well, more precisely, abject fear of bugs).
Almost four decades of computer programming have left me with deep respect for the difficulty of the craft (well, more precisely, abject fear of bugs).
the program execution time and the time a user spends waiting for it, but to do this we'd have to burn some of the programmer's time, and thus the time the user waits for the programmer to get the program written
the program execution time and the time a user spends waiting for it, but to do this we'd have to burn some of the programmer's time, and thus the time the user waits for the programmer to get the program written
Binary search has some very large advantages. First of all, its performance is O(log2 N). People often don't really grasp how powerful this is. On a 32-bit computer, the biggest log2 you'll ever encounter is 32
Binary search has some very large advantages. First of all, its performance is O(log2 N). People often don't really grasp how powerful this is. On a 32-bit computer, the biggest log2 you'll ever encounter is 32
Some look at my binary-search algorithm and ask why the loop always runs to the end without checking whether it's found the target. In fact, this is the correct behavior; the math is beyond the scope of this chapter, but with a little work, you should be able to get an intuitive feeling for it—and this is the kind of intuition I've observed in some of the great programmers I've worked with. Let's think about the progress of the loop. Suppose you have n elements in the array, where n is some really large number. The chance of finding the target the first time through is 1/n, a really small number. The next iteration (after you divide the search set in half) is 1/(n/2)—still small—and so on. In fact, the chance of hitting the target becomes significant only when you're down to 10 or 20 elements, which is to say maybe the last four times through the loop.
Some look at my binary-search algorithm and ask why the loop always runs to the end without checking whether it's found the target. In fact, this is the correct behavior; the math is beyond the scope of this chapter, but with a little work, you should be able to get an intuitive feeling for it—and this is the kind of intuition I've observed in some of the great programmers I've worked with. Let's think about the progress of the loop. Suppose you have n elements in the array, where n is some really large number. The chance of finding the target the first time through is 1/n, a really small number. The next iteration (after you divide the search set in half) is 1/(n/2)—still small—and so on. In fact, the chance of hitting the target becomes significant only when you're down to 10 or 20 elements, which is to say maybe the last four times through the loop.
If there's a moral to this story, it is this: do not let performance considerations stop you from doing what is right. You can always make the code faster with a little cleverness. You can rarely recover so easily from a bad design
If there's a moral to this story, it is this: do not let performance considerations stop you from doing what is right. You can always make the code faster with a little cleverness. You can rarely recover so easily from a bad design
One of the deepest lessons in design is that you can gain a great deal if you hold the right things constant.
One of the deepest lessons in design is that you can gain a great deal if you hold the right things constant.
The world is filled with frameworks that are a little too hard to understand and look like they have a bit too much investment in them—so much investment that it's hard to justify reinventing the wheel. When that happens, we end up with large frameworks that miss important areas of use.
The world is filled with frameworks that are a little too hard to understand and look like they have a bit too much investment in them—so much investment that it's hard to justify reinventing the wheel. When that happens, we end up with large frameworks that miss important areas of use.
When speaking of beautiful tests, it's hard not to think of the JUnit testing framework.
When speaking of beautiful tests, it's hard not to think of the JUnit testing framework.
the old hacker wisdom that "six months in the lab can save you ten minutes in the library
the old hacker wisdom that "six months in the lab can save you ten minutes in the library
when starting a new project, getting the foundation right has to be the crucial starting point
when starting a new project, getting the foundation right has to be the crucial starting point
A good abstraction proves its worth when it makes coding simpler under diverse conditions, or when it ends up being useful in ways that were originally unintended.
A good abstraction proves its worth when it makes coding simpler under diverse conditions, or when it ends up being useful in ways that were originally unintended.
Part of the reason that young software engineers should cut their teeth debugging complicated systems is that it inculcates a lifelong skill: the ability to analyze a solution to a problem in terms of the ways that it won't work instead of the ways that it might—the ability to focus on the edge conditions. When conceiving of new software, we software engineers should not try to convince ourselves why our design will work; we should invalidate the reasons why it will not.
Part of the reason that young software engineers should cut their teeth debugging complicated systems is that it inculcates a lifelong skill: the ability to analyze a solution to a problem in terms of the ways that it won't work instead of the ways that it might—the ability to focus on the edge conditions. When conceiving of new software, we software engineers should not try to convince ourselves why our design will work; we should invalidate the reasons why it will not.
beautiful program is one that is so simple and elegant that it obviously has no mistakes, rather than merely having no obvious mistakes
beautiful program is one that is so simple and elegant that it obviously has no mistakes, rather than merely having no obvious mistakes
It is therefore good library design to export STM actions (rather than IO actions) whenever possible, because they are composable; their type advertises that they have no irrevocable effects. The library client can readily get from STM to IO (using atomically), but not vice versa.
It is therefore good library design to export STM actions (rather than IO actions) whenever possible, because they are composable; their type advertises that they have no irrevocable effects. The library client can readily get from STM to IO (using atomically), but not vice versa.
Human beings are more conservative than you might think; most people find it difficult to embrace new concepts or change their ways of thinking. Instead, many prefer to continue suffering rather than change.
Human beings are more conservative than you might think; most people find it difficult to embrace new concepts or change their ways of thinking. Instead, many prefer to continue suffering rather than change.
There are places where it could be more bookish, or where code could blend in more, for example. Sure, we'd like to clean those up, but while we like pretty code, we like clean merges even better. Changes to variable names, whitespace, line breaks, and so forth can be more of an obstacle to merging than logic changes.
There are places where it could be more bookish, or where code could blend in more, for example. Sure, we'd like to clean those up, but while we like pretty code, we like clean merges even better. Changes to variable names, whitespace, line breaks, and so forth can be more of an obstacle to merging than logic changes.