Java sorting report: Comparison method violates its general contract exception solution

This article mainly introduces to you the solution to the exception of sorting report in java: Comparison method violates its general contract. The introduction in the article is very detailed and has certain reference and learning value for everyone. Friends who need it can come together. Let's see.

Preface

A Comparison method violates its general contract appeared in a piece of sorted java code online last week , I learned some knowledge on the way to solving this problem and will summarize and share it here.

Cause of exception

The exception caused by this sorting will appear in versions above java7, so if your JDK starts from 6 If you upgrade to 7 or 8, you must be careful about this exception.

In the compatibility list of java7, there is a description of the incompatibility of this sort:

Area: API: Utilities
Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException
Description: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation.
If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behavior.
Nature of Incompatibility: behavioral
RFE: 6804124

I found from the information that java7 began to introduce the Timsort sorting algorithm. I had always thought that most of the built-in sorting algorithms in the standard library were quick sort. Now I learned that many multi-language uses Timsort internally. Then I found this sentence on Wikipedia:

t was implemented by Tim Peters in 2002 for use in the Python programming language.

So This ranking is naturally named after him.

Then I found this picture sorting comparison on the Internet:

It can be found that Timsort is even better than QuickSort in performance.

This blog will not discuss the implementation of Timsort in detail (it seems that this algorithm is quite complicated). I may write another blog to discuss Timsort separately. Simply put, Timsort combines merge sort and insertion sort. . This algorithm clearly requires strict monotonic increase or decrease during implementation to ensure the stability of the algorithm.

• ##sgn(compare(x, y)) == -sgn(compare(y, x))

• ##((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0

• compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z

  
  

Looks a lot like the symmetry and transitive relationships of sets learned in discrete mathematics classes.

So the reason for the exception is that the sorting algorithm is not rigorous enough. In fact, business code is often not as rigorous as pure technology. For example, for an algorithm like this:

Select the lowest price among flights

Then if two equal low prices exist at the same time, according to the logic of finding the lowest price, if it is written like this:

if (thisPrice < lowPrice){
 lowPrice = thisPrice;
}

The low-price location is "first come, first served".

But if this is achieved:

if(thisPrice <= lowPrice){
 lowPrice = thisPrice;
}

Then the lower prices in the back will cover the ones in the front, and it will become a "latecomer comes first".

Programming

We often encounter the two problems of first come first served and latecomers taking precedence. So for the above one, it is necessary to provide a rigorous judgment and size comparison function implementation. So if it looks like this:

return x > y ? 1 : -1;

then this condition is not met.

But our logic is more complicated than this. It is actually such a sorting condition. Sort by:

price. If the prices are equal, the one with the earlier departure time will be ranked first.
If the departure times are also equal, the following will be used:
non-shared non-stop>non-stop>non-shared> The attributes of the stop are
• priority

  selected. If these attributes are all equal, they can only be considered equal.

So the problem with this judgment function is:

public compareFlightPrice(flightPrice o1, flightPrice o2){
 // 非经停非共享
 if (o1.getStopNumber() == 0 && !o1.isShare()) {
 return -1;
 } else if (o2.getStopNumber() == 0 && !o2.isShare()) {
 return 1;
 } else {
 if (o1.getStopNumber() == 0) {
  return -1;
 } else if (o2.getStopNumber() == 0) {
  return 1;
 } else {
  if (!o1.isShare()) {
  return -1;
  } else if (!o2.isShare()) {
  return 1;
  } else {
  if (o1.getStopNumber() > 0) {
   return -1;
  } else if (o2.getStopNumber() > 0) {
   return 1;
  } else {
   return 0;
  }
  }
 }
 }
}

This function has an obvious first-come, first-served problem, such as

compareFlightPrice(a, b)

, if ab is non-shared and non-stop, then a will be ranked first, but if compareFlightPrice(b, a) is called, b will be ranked first, so a must be judged Only if b is non-shared and non-stop, and b is not non-shared and non-stop, can a be ranked first. Of course, in addition to changing the comparison function, there is another solution: add startup parameters to the jvm.

-Djava.util.Arrays.useLegacyMergeSort=true

It should also be noted that if there are equal elements in your collection, and the comparison function does not meet the strict definition above, this exception will definitely appear stably. In fact, it appears in our production environment. The probability of this exception is very small. After all, Java is not stupid enough to check the entire array first. In fact, it finds that you do not meet this condition during the sorting process. So it's possible that some kind of collection order allows you to just bypass this judgment.

The above is the detailed content of Java sorting report: Comparison method violates its general contract exception solution. For more information, please follow other related articles on the PHP Chinese website!