Optimising the compareTo method...

On the previous page, we saw an example implementation of the compareTo() method of the Comparable interface. Our implementation was methodical and easy to follow, but a bit "long-winded".

...so long as we're careful!

In some cases we can make the comparison method more succinct, but we need to proceed with caution as we'll see in a second.

Using a subtraction instead of a comparison

The first optimisation that can be made in certain cases is to use a subtraction instead of a comparison of numeric values. In principle, this works thanks to some extremely elementary mathematics:

• if a < b, then a - b will be negative;
• if a > b, then a - b will be positive.

Oh, and of course subtracting a number from itself gives zero. So our card comparison routine can now look as follows:

public class PlayingCard implements Comparable<PlayingCard> {
  public int compareTo(PlayingCard o) {
    int cardComp = this.suit - o.suit;
    if (cardComp == 0) {
      cardComp = this.number - o.number;
    }
    return cardComp;
  }
}

Using subtraction is a very common idiom for comparing numbers in sorting routines, and is almost certainly the reason why compareTo() is defined to return an integer in the first place. Indeed, you may be wondering why we bothered with the previous version of doing comparisons and returning specific values. Well, it turns out that the subtraction method is incorrect for the general case, although it works here.

Problem with this method: comparing large numbers

The above method works because we know that the numbers we'll be comparing will be small. But ints can only store numbers up to a certain magnitude. So if we know that the difference between the two numbers can exceed about 2 billion (2³²) we should avoid the above method. Converting to longs gives us extra breathing space (the magnitude can now read 2⁶³), but the essential problem remains.

This means, for example, that if you're comparing database keys, you should check very carefully what your database's key allocation policy is if you intend to use this method. (Just because you only have 100,000 keys in your table may not mean that the keys are allocated from that range of numbers.)

Is it worth it?

In tests I ran (on Intel architecture), I actually found that:

• when the compareTo() involves a single comparison, using a subtraction instead of comparisons makes no appreciable difference;
• when two comparisons are involved, using subtraction as above (so that our method has just a single comparison with zero) makes the overall sort about 10% faster.

In other words, in the single-variable case, the "optimisation" appears non-existent and in the two-variable case, the performance benefits are minimal. Possibly the main benefit is therefore a readability issue, at least on modern architecture.

Next...

Next, you may wish to look at how to set an arbitrary sort order using the Java Comparator interface.