Beautiful Code [137]
Here's the code for the theory:
public void assertTheory5(int[] testArray, int target) {
int numberOfComparisons =
Util.binarySearchComparisonCount(testArray, target);
assertTrue(numberOfComparisons <= 1 + log2(testArray.length));
}
I add this latest theory to my existing list inside the method testTheories, which now looks like this:
...
while (experiments-- > 0) {
testArray = generateRandomSortedArray( );
if (rand.nextInt( ) % 2 == 0) {
target = testArray[rand.nextInt(testArray.length)];
} else {
target = rand.nextInt( );
}
returnValue = Util.binarySearch(testArray, target);
assertTheory1(testArray, target, returnValue);
assertTheory2(testArray, target, returnValue);
assertTheory3(testArray, target, returnValue);
assertTheory4(testArray, target, returnValue);
assertTheory5(testArray, target);
}
...
I run a few tests with a maxArraySize set of a few different values, and I find that Theory 5 seems to be holding strong.
Because it's almost noon, I set the number of experiments to 1,000,000 and go to lunch while my computer crunches away and tests each theory a million times.
When I get back, I see that all my tests pass. There are probably a couple more things that I would want to test, but I have made great progress in boosting my confidence in this implementation of binarySearch. Because different developers have different backgrounds, styles, and levels of experience, you might have focused on different areas of the code. A developer already familiar with the unsigned shift operator, for example, would not feel the same need I had to test it.
In this section, I wanted to give you a flavor of performance testing and show you how you could gain insight into and confidence in your code's performance by combining code instrumentation with test theories. I highly recommend you study Chapter 3, where Jon Bentley gives this important topic the attention and beautiful treatment it deserves.
Beautiful Tests > Conclusion
7.4. Conclusion
In this chapter, we have seen that even the best developers and the most beautiful code can benefit from testing. We have also seen that writing test code can be every bit as creative and challenging as writing the target code. And, hopefully, I've shown you that tests themselves can be considered beautiful in at least three different ways.
Some tests are beautiful for their simplicity and efficiency. With a few lines of JUnit code, run automatically with every build, you can document the code's intended behavior and boundaries, and ensure that both of them are preserved as the code evolves.
Other tests are beautiful because, in the process of writing them, they help you improve the code they are meant to test in subtle but important ways. They may not discover proper bugs or defects, but they bring to the surface problems with the design, testability, or maintainability of the code; they help you make your code more beautiful.
Finally, some tests are beautiful for their breadth and thoroughness. They help you gain confidence that the functionality and performance of the code match requirements and expectations, not just on a few handpicked examples, but with a wide range of inputs and conditions.
Developers who want to write beautiful code can learn something from artists. Painters regularly put down their brushes, step away from the canvas, circle it, cock their heads, squint, and look at it from different angles and under different lights. They need to develop and integrate those perspectives in their quest for beauty. If your canvas is an IDE and your medium is code, think of testing as your way of stepping away from the canvas to look at your work with critical eyes and from different perspectives—it will make you a better programmer and help you create more beautiful code.
Top Down Operator Precedence > JavaScript
9. Top Down Operator Precedence
Douglas Crockford
In 1973, vaughan pratt presented "top down operator precedence"[*] at the first annual Principles