4

I just found this statement: "One can greatly increase the performance of compareTo by comparing first on items which are most likely to differ". Is it true? And if it is, why?

dhblah
  • 9,751
  • 12
  • 56
  • 92
  • Is it from http://www.javapractices.com/topic/TopicAction.do?Id=10 ? – Adam Paynter Feb 28 '11 at 12:57
  • Where did you find it? My guess is that it was in the context of a discussion on sorting. – unholysampler Feb 28 '11 at 12:58
  • well, yeah, I know, I just want to know is it true cause I didn't find any other mention of such thing. – dhblah Feb 28 '11 at 12:59
  • it is as simple as [this](http://stackoverflow.com/questions/3786358/get-rid-of-ugly-if-statements/3786376#3786376) – jmj Feb 28 '11 at 13:08
  • it's very simple observation, if you compare 9properties and all returned 0 but the 10th yields a results, you have 10 `compareTo` invokations (which are not exactly fast), if you manage to compare the 10th firstly, you win w/ a single `compareTo`. – bestsss Feb 28 '11 at 13:13

3 Answers3

5

Consider a class with several properties. For comparing instances, you need to compare some of their properties. If all properties except one are equal, the amount of comparisons you need to do depends on the order of the property comparisons: if you happen to compare the differing properties first, you got the result with one comparison. But if you compare the differing properties last, you had to do n comparisons to get the same result.

As @Kdeveloper noted, the performance difference may not be noticeable unless you do lots of similar comparisons in batches. But the other benefit is IMHO logical ordering: this makes you think about the logical relationship between class properties. And overall, since this is a nondisruptive optimization (i.e. it does not make the code more difficult to read and maintain), I think it is worth doing it most of the time.

Péter Török
  • 114,404
  • 31
  • 268
  • 329
  • Well, I think that maybe that phrase was not about object to compare, but about that properties. At first I thought that the order of object comparison matters, but if it is what you're talking about, it makes sense. – dhblah Feb 28 '11 at 13:05
1

Yes, it's true

Because if you put the most selective comparison first, you will on average execute less code for each comparison. But as these test are typically very fast, the speed improvements will only be noticeable if you compare many objects, for example when you sort a big collection.

Kdeveloper
  • 13,679
  • 11
  • 41
  • 49
  • *But as these test are typically very fast* if you need to call compareTo on some other properies/fields, they are not fast, esp. if it is an interface having multiple (>2) call targets. – bestsss Feb 28 '11 at 13:13
  • Still, this is normally only noticeable when you do it often, like for example a sort on a collection. – Kdeveloper Feb 28 '11 at 14:36
0

Is it true? And if it is, why?

Well, literally speaking, no. The compareTo method will take equally long time to execute, regardless of history.

If it can gain any overall performance in a particular implementation? Yes, for sure. But to be able to answer your question we would need more context about the situation.

aioobe
  • 413,195
  • 112
  • 811
  • 826