Java Reference
In-Depth Information
}
Clearly, x is less than z , yet the program prints 294967296 , which is positive. Given that this
comparison idiom is broken, why is it used so commonly? Because it works most of the time. It
breaks only if the numbers to which it is applied differ by more than Integer.MAX_VALUE . This
means that for many applications, failures won't be observed in practice. Worse, they may be
observed infrequently enough that the bug will never get found and fixed.
So what does this mean for the behavior of our program? If you look at the Comparator
documentation, you will see that the relation it implements must be transitive . In other words,
(compare(x, y) > 0) && (compare(y, z) > 0) implies that compare(x, z) > 0 . Consider the
case in which x and z have the values in the Overflow example and y has the value 0 . Our
comparator violates transitivity for these values. In fact, it returns the wrong value for one quarter of
all int pairs chosen at random. Performing a search or sort with such a comparator or using it to
order a sorted collection can cause unspecified behavior, which is what we observed when we ran
the program. For the mathematically inclined, the general contract of the Comparator.compare
method requires that comparators impose a total order , but this one fails to do so on several counts.
We can fix our program by substituting a Comparator implementation that obeys the general
contract. Because we want to reverse the natural order, we don't even have to write our own
comparator. The Collections class provides one that's made to order. If you replace the original
Arrays.sort invocation by Arrays.sort(arr, Collections.reverseOrder()) , the program will
print DESCENDING as expected.
Alternatively, you can write your own comparator. The following code is not "clever," but it works,
causing the program to print DESCENDING as expected:
public int compare(Integer i1, Integer i2) {
return (i2 < i1 ? -1 : (i2 == i1 ? 0 : 1));
}
This puzzle has several lessons. The most specific is: Do not use a subtraction-based comparator
unless you are sure that the difference between values will never be greater than
Integer.MAX_VALUE [EJ Item 11]. More generally, beware of int overflow, as discussed in Puzzles
3 , 26 , and 33 . Another lesson is that you should avoid "clever" code. Strive to write clear, correct
code, and do not optimize it unless it proves necessary [EJ Item 37].
 
 
Search WWH ::




Custom Search