I want to take this opportunity to constructively criticize coderodde's answer and point out some very important lessons about microbenchmarking.
As you know, Java is a hybrid between being compiled and interpreted:
javac compiles your source files down to bytecode, and then the Java Virtual Machine (
java) executes this bytecode, either by interpreting it or compiling it "just in time" (i.e., right before it runs).
javac compilation process does essentially no optimization; this is by design. Rather, optimization is performed by the JVM at runtime. As your code runs, the JVM determines the "hot spots," and optimizes them as best it can. Consequently, your code's performance improves over time within a single run of the program.
Whenever you are profiling a Java program, then, there are a few critical steps you must follow:
- "Warm up the JVM," by running your code a few times so that the JVM can begin to identify the hot spots.
- Run both versions of your code, timing a segment that takes at least a full second to run. (Otherwise, there is too much noise.)
- Collect the results and compare the timing data from after the JVM warmup.
The microbenchmark provided by coderodde properly handles step (2), which many people forget: the runtime of ten or more seconds is a good window to test. But this benchmark neglects to handle the JVM warmup phase. At best, it is timing the unoptimized versions of each algorithm; at worst, the second algorithm timed is benefitting partially due to the JVM having warmed up on the first one and identified similar patterns.
Here's a better driver. I'll paste in the results below:
Trial Normal Cached Equal?
0 10450 9418 true
1 10459 9391 true
2 2242 2194 true
3 2231 2179 true
4 2230 2185 true
5 2233 2209 true
6 2236 2186 true
7 2236 2174 true
8 2237 2189 true
9 2258 2174 true
10 2239 2196 true
11 2240 2194 true
12 2219 2218 true
13 2245 2194 true
14 2246 2195 true
15 2246 2203 true
You can see that something magical happens after the second trial: the runtime of both algorithms improves by a factor of 4–5. This is where the JVM optimization has kicked in! After this point, the differences between the two algorithms are negligible. In this particular run, the cached version always seems to do between 0.05% and 4% better than the original version; on other runs, the opposite is true.
Finally, microbenchmarks inherently have problems of their own: the performance of an algorithm in a microbenchmark may not reflect that algorithm's performance in a larger application.
For example, suppose you have two algorithms for calculating trigonometric functions: one uses Taylor series, and the other uses lookup tables. You write a microbenchmark, following all best practices, and the lookup table algorithm wins, hands down. But you start using it in your application and your performance drops by a factor of six. What happened? In the microbenchmark, the lookup table for the function was stored in cache; in the real application, there was more contention on the cache, leading to more cache misses and poorer performance overall.
One moral of the story is that you should always be exceptionally careful while profiling and optimizing, testing carefully at every step that your optimizations are not actually pessimizations.
Another moral, though, is to be skeptical of any "optimization" as simple as caching a scalar value, or reusing a variable: these are precisely the kinds of things that compilers (and run-time optimizers) are good at. It is most important to write code that is simple, clear, and uses efficient algorithms; the compiler will figure out the details of the performance.
In terms of the rest of your code:
- I second coderodde's suggestion to use the "diamond operator" for clarity.
- You should also remove the comment that says "we create a list of integers"—yes, that's what
new ArrayList<Integer> means.
- In terms of organization, I would have created a three-field
class PythagoreanTriple instead of using a
List<Integer>; this clarifies the intent from the type and makes it more difficult to do something wrong, like including an empty list.
- No, you should not prefix private variables with underscores.
Overall, it's good, and pretty Java-like. Well done.