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 は、Python で使用するために 2002 年に Tim Peters によって実装されました。 プログラミング言語。
🎜🎜つまり、この並べ替えは当然彼の名前にちなんで名付けられました。 🎜🎜その後、インターネットで次のような画像の並べ替え比較を見つけました。 🎜

🎜🎜Timsort のパフォーマンスが QuickSort よりも優れていることがわかります。 🎜🎜このブログでは Timsort の実装については詳しく説明しません (このアルゴリズムは非常に複雑なようです)。Timsort については別のブログで説明するかもしれません。簡単に言えば、Timsort はマージ ソートと挿入ソートを組み合わせたものです。このアルゴリズムは、アルゴリズムの安定性を確保するために、実装中に厳密な単調増加または単調減少を明らかに必要とします。 🎜

🎜

• 🎜sgn(compare(x, y)) == -sgn(compare(y, x))🎜
• 🎜((compare(x, y)>0) && (compare(y, z)>0)) は、compare(x, z)>0 を意味します🎜
• 🎜compare(x, y)==0 は、すべての z に対して sgn(compare(x, z))==sgn(compare(y, z)) を意味します
  🎜

🎜これは、離散数学の授業で学んだ集合の対称性と推移的関係によく似ています。 🎜🎜つまり、例外の理由は、並べ替えアルゴリズムが十分に厳密ではないためです。実際、ビジネスコードは純粋なテクノロジーほど厳密ではないことがよくあります。たとえば、次のようなアルゴリズムの場合: 🎜🎜フライトの中で最低価格を選択
🎜🎜最低価格を見つけるロジックに従って、同じ最低価格が同時に2つ存在する場合、次のように記述されている場合: 🎜rrreee🎜では、安値の位置は「早い者勝ち」です。 🎜🎜しかし、これが達成されれば: 🎜rrreee🎜すると、後ろの安い価格が前のものをカバーし、「後発優先」になります。 プログラミングでは、先着順と後着順という 2 つの問題がよく発生します。 🎜🎜そのため、上記のものについては、厳密な判断とサイズ比較関数の実装が必要です。したがって、次のような場合: 🎜rrreee🎜 は、この基準を満たしていません。 🎜🎜しかし、私たちのロジックはこれよりも複雑です、それは実際にはそのような並べ替え条件です。並べ替え条件: 🎜

• 🎜 価格が同じ場合、出発時刻が早いものが最初にランクされます。 🎜
• 🎜出発時刻も等しい場合、次の属性に従って実行されます: 🎜
• 🎜非乗合 ノンストップ>ノンストップ>ノン-共有>停止優先 選択。これらの属性がすべて等しい場合、それらは等しいとのみみなされます。 。 🎜

🎜 したがって、この判定関数の問題は次のとおりです。 🎜rrreee🎜 この関数には、たとえば、compareFlightPrice(a, b) , if ab と ab は両方とも非共有かつノンストップであるため、a が最初にランク付けされますが、<code>compareFlightPrice(b, a) が呼び出された場合は、b が最初にランク付けされます。 a が 1 位にランクされるためには、a が非共有非停止であり、b が非共有非停止ではないかを判断する必要があります。 🎜🎜もちろん、比較関数を変更することに加えて、別の解決策があります。それは、JVM に起動パラメーターを追加することです。 🎜rrreee🎜また、セット内に等しい要素が存在することを必ずしも意味するわけではなく、比較関数が上記の厳密な定義を満たしていないことにも注意してください。実際、この例外は確実に安定して表示されます。実際、Java は、実稼働環境で発生する例外は非常に小さいので、最初に配列全体をチェックするほど愚かではありません。実際、ソート処理中にこの条件を満たしていないことがわかります。したがって、ある種の収集命令により、この判断を回避できる可能性があります。 🎜

以上がJava ソート レポート: 比較メソッドは一般規約の例外ソリューションに違反していますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。