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

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

Jun 30, 2017 am 10:35 AM
method

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
Copy after login

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;
}
Copy after login

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

But if this is achieved:

if(thisPrice <= lowPrice){
 lowPrice = thisPrice;
}
Copy after login

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;
Copy after login

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;
  }
  }
 }
 }
}
Copy after login

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
Copy after login

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!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Top 4 JavaScript Frameworks in 2025: React, Angular, Vue, Svelte Top 4 JavaScript Frameworks in 2025: React, Angular, Vue, Svelte Mar 07, 2025 pm 06:09 PM

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

How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache? How do I implement multi-level caching in Java applications using libraries like Caffeine or Guava Cache? Mar 17, 2025 pm 05:44 PM

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

How does Java's classloading mechanism work, including different classloaders and their delegation models? How does Java's classloading mechanism work, including different classloaders and their delegation models? Mar 17, 2025 pm 05:35 PM

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

Spring Boot SnakeYAML 2.0 CVE-2022-1471 Issue Fixed Spring Boot SnakeYAML 2.0 CVE-2022-1471 Issue Fixed Mar 07, 2025 pm 05:52 PM

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: Key Performance Boosts and New Features Node.js 20: Key Performance Boosts and New Features Mar 07, 2025 pm 06:12 PM

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: The Future of Data Lake Tables Iceberg: The Future of Data Lake Tables Mar 07, 2025 pm 06:31 PM

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

How can I implement functional programming techniques in Java? How can I implement functional programming techniques in Java? Mar 11, 2025 pm 05:51 PM

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

How to Share Data Between Steps in Cucumber How to Share Data Between Steps in Cucumber Mar 07, 2025 pm 05:55 PM

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

See all articles