Java 정렬 보고서: 비교 방법이 일반 계약 예외 솔루션을 위반합니다.

이 기사에서는 주로 Java의 정렬 예외에 대한 솔루션을 소개합니다. 비교 방법은 일반 계약을 위반합니다. 기사의 소개는 매우 상세하며 필요한 모든 친구가 살펴볼 수 있는 특정 참고 자료와 학습 가치가 있습니다. 아래.

머리말

비교 방법이 일반 계약을 위반합니다가 지난 주에 온라인에서 정렬된 Java 코드 조각에 나타났습니다. 이 문제를 해결하는 방법에 대한 지식을 공유하겠습니다. 여기. . Comparison method violates its general contract，在解决这个问题的途中学到了一些知识这里总结分享一下。

异常原因

这个排序导致的异常将会在java7以上的版本出现，所以如果你的JDK从6升级到了7或者8，那一定要小心此异常。

在java7的兼容列表中，就有对此排序不兼容的说明：

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

我从资料中查阅到java7开始引入了Timsort的排序算法。我之前一直以为大部分标准库的内置排序算法都是快速排序。现在才得知很多语言内部都使用Timsort排序。随后我在wiki百科上找到了这样一句话：

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

所以这个排序自然是以他命名的。

随后我又在网上找到了这样一张图排序比较的图：

可以发现，Timsort在表现上比QuickSort还要好。

这篇博客不去详细讨论Timsort的实现（看上去这个算法还挺复杂的），我可能会写另一篇博客单独讨论Timsort，简单来说Timsort结合了归并排序和插入排序。这个算法在实现过程中明确需要：严格的单调递增或者递减来保证算法的稳定性。

• 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
  

看上去很像离散数学课中学习的集合的对称性，传递性的关系。

所以异常的原因是因为排序算法不够严谨导致的，实际上业务上的代码经常不如纯技术上的严谨。比如对于这样一个算法：

选出航班中的最低价

那如果两个相等低价同时存在，按照寻找最低价的逻辑如果这么写：

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

那低价这个位置就是“先到先得”了。

但如果这么实现:

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

那后面的低价就会覆盖前面的，变成了“后来者居上”。编程中经常遇到先到先得和后来者居上这两个问题。

所以对于上面那个需要提供严谨的判断大小比较函数实现。所以如果是这样的：

return x > y ? 1 : -1;

那么就不符合此条件。

不过我们逻辑要比这个复杂，其实是这样一个排序条件。按照：

• 价格进行排序，如果价格相等则起飞时间靠前的先排。

• 如果起飞时间也相等，就会按照：

• 非共享非经停>非经停>非共享>经停的属性进行优先级选择，如果这些属性都全部相等，才只能算是相等了。

所以这个判断函数的问题是：

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;
  }
  }
 }
 }
}

这个函数有明显的先到先得的问题，比如对于compareFlightPrice(a, b) ，如果ab都是非共享非经停，那么这个就会把a排到前面，但如果调用compareFlightPrice(b, a)

예외 원인

🎜🎜이 정렬로 인한 예외는 java7 이상 버전에서 나타나므로 JDK를 6에서 7, 8로 업그레이드하는 경우에는 이 예외에 주의해야 합니다.
🎜🎜java7의 호환성 목록에는 이런 종류의 비호환성에 대한 설명이 있습니다. 🎜

-Djava.util.Arrays.useLegacyMergeSort=true

🎜java7이 Timsort 정렬 알고리즘을 도입하기 시작했다는 정보에서 찾았습니다. 나는 항상 표준 라이브러리에 내장된 대부분의 정렬 알고리즘이 빠른 정렬이라고 생각했습니다. 이제 저는 많은 다국어가 내부적으로 Timsort를 사용한다는 것을 알게 되었습니다. 그러다가 Wikipedia에서 다음 문장을 발견했습니다. 🎜🎜t는 2002년 Tim Peters가 Python에서 사용하기 위해 구현했습니다. 프로그래밍 언어입니다.
🎜🎜따라서 이 정렬은 자연스럽게 그의 이름을 따서 명명되었습니다. 🎜🎜그런 다음 인터넷에서 다음과 같은 사진 정렬 비교를 찾았습니다. 🎜

🎜🎜Timsort가 QuickSort보다 성능이 더 좋은 것을 확인할 수 있습니다. 🎜🎜이 블로그에서는 Timsort의 구현에 대해 자세히 설명하지 않습니다(이 알고리즘은 상당히 복잡한 것 같습니다). Timsort를 별도로 설명하기 위해 다른 블로그를 작성할 수도 있습니다. 간단히 말해서 Timsort는 병합 정렬과 삽입 정렬을 결합합니다. 이 알고리즘은 알고리즘의 안정성을 보장하기 위해 구현 중에 엄격한 단조 증가 또는 감소를 요구합니다. 🎜

🎜

• 🎜sgn(비교(x, y)) == -sgn(비교(y, x))🎜
• 🎜((compare(x, y)>0) && (compare(y, z)>0))은 비교(x, z)>0을 의미합니다.🎜
• 🎜compare(x, y)==0은 모든 z에 대해 sgn(compare(x, z))==sgn(compare(y, z))를 의미함
  🎜

🎜이산 수학 수업에서 배운 집합의 대칭 및 전이 관계와 매우 유사해 보입니다. 🎜🎜그래서 예외가 발생하는 이유는 정렬 알고리즘이 충분히 엄격하지 않기 때문입니다. 실제로 비즈니스 코드는 순수 기술만큼 엄격하지 않은 경우가 많습니다. 예를 들어 다음과 같은 알고리즘의 경우: 🎜🎜항공편 중 최저 가격 선택
🎜🎜두 개의 동일한 저가 가격이 동시에 존재하는 경우 최저가 찾기 논리에 따라 다음과 같이 작성하면 : 🎜rrreee🎜그럼 최저가의 입장은 "선착순" 입니다. 🎜🎜하지만 이것이 달성된다면: 🎜rrreee🎜그러면 뒤쪽의 낮은 가격이 앞쪽의 가격을 덮게 되고 "후발자 우선"이 됩니다. 프로그래밍은 종종 선착순과 후순위라는 두 가지 문제에 직면합니다. 🎜🎜그래서 위의 경우에는 엄격한 판단과 크기 비교 기능 구현이 필요합니다. 따라서 다음과 같이 보인다면: 🎜rrreee🎜 이는 이 기준을 충족하지 않는 것입니다. 🎜🎜하지만 우리의 논리는 이보다 더 복잡합니다. 실제로는 이러한 정렬 조건입니다. 정렬 기준: 🎜

• 🎜가격이 동일할 경우 출발 시간이 빠른 것이 우선 순위가 됩니다. 🎜
• 🎜출발 시간도 동일할 경우 다음 속성에 따라 수행됩니다. 🎜
• 🎜Non-shared non-stop>Non-stop>Non- 공유>중지우선순위 선택, 이러한 속성이 모두 동일하면 동일한 것으로 간주될 수 있습니다. . 🎜

🎜이 판단 함수의 문제점은 다음과 같습니다. 🎜rrreee🎜이 함수에는 명백한 선착순 문제가 있습니다. 예를 들어 compareFlightPrice(a, b) , ab와 ab가 모두 비공유이고 논스톱이면 a가 첫 번째 순위가 되지만, <code>compareFlightPrice(b, a)가 호출되면 b가 첫 번째 순위가 되므로 a가 비공유, 논스톱인지 판단해야 합니다. b가 비공유 논스톱이 아닌 경우에만 a가 1순위가 될 수 있습니다. 🎜🎜물론, 비교 기능을 변경하는 것 외에도 또 다른 해결 방법이 있습니다. 즉, jvm에 시작 매개변수를 추가하는 것입니다. 🎜rrreee🎜또한 집합에 동일한 요소가 있다는 의미는 아니며 비교 함수가 위의 엄격한 정의를 충족하지 않는다는 점에 유의해야 합니다. 실제로 이 예외는 확실히 안정적으로 나타날 가능성이 있습니다. 이는 프로덕션 환경에서 발생하는 예외입니다. 결국 Java는 전체 배열을 먼저 확인할 만큼 어리석지 않습니다. 실제로 정렬 과정에서 이 조건을 충족하지 못하는 것을 발견합니다. 따라서 일종의 추심 명령을 통해 이러한 판단을 우회할 수 있는 가능성이 있습니다. 🎜

위 내용은 Java 정렬 보고서: 비교 방법이 일반 계약 예외 솔루션을 위반합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!