


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
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".
ProgrammingWe 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!

Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

AI Hentai Generator
Generate AI Hentai for free.

Hot Article

Hot Tools

Notepad++7.3.1
Easy-to-use and free code editor

SublimeText3 Chinese version
Chinese version, very easy to use

Zend Studio 13.0.1
Powerful PHP integrated development environment

Dreamweaver CS6
Visual web development tools

SublimeText3 Mac version
God-level code editing software (SublimeText3)

Hot Topics

This article analyzes the top four JavaScript frameworks (React, Angular, Vue, Svelte) in 2025, comparing their performance, scalability, and future prospects. While all remain dominant due to strong communities and ecosystems, their relative popul

The article discusses implementing multi-level caching in Java using Caffeine and Guava Cache to enhance application performance. It covers setup, integration, and performance benefits, along with configuration and eviction policy management best pra

Java's classloading involves loading, linking, and initializing classes using a hierarchical system with Bootstrap, Extension, and Application classloaders. The parent delegation model ensures core classes are loaded first, affecting custom class loa

This article addresses the CVE-2022-1471 vulnerability in SnakeYAML, a critical flaw allowing remote code execution. It details how upgrading Spring Boot applications to SnakeYAML 1.33 or later mitigates this risk, emphasizing that dependency updat

Node.js 20 significantly enhances performance via V8 engine improvements, notably faster garbage collection and I/O. New features include better WebAssembly support and refined debugging tools, boosting developer productivity and application speed.

Iceberg, an open table format for large analytical datasets, improves data lake performance and scalability. It addresses limitations of Parquet/ORC through internal metadata management, enabling efficient schema evolution, time travel, concurrent w

This article explores integrating functional programming into Java using lambda expressions, Streams API, method references, and Optional. It highlights benefits like improved code readability and maintainability through conciseness and immutability

This article explores methods for sharing data between Cucumber steps, comparing scenario context, global variables, argument passing, and data structures. It emphasizes best practices for maintainability, including concise context use, descriptive
