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
🎜🎜つまり、この並べ替えは当然彼の名前にちなんで名付けられました。 🎜🎜その後、インターネットで次のような画像の並べ替え比較を見つけました。 🎜
🎜🎜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🎜 は、この基準を満たしていません。 🎜🎜しかし、私たちのロジックはこれよりも複雑です、それは実際にはそのような並べ替え条件です。並べ替え条件: 🎜
- 🎜 価格が同じ場合、出発時刻が早いものが最初にランクされます。 🎜
- 🎜出発時刻も等しい場合、次の属性に従って実行されます: 🎜
- 🎜非乗合 ノンストップ>ノンストップ>ノン-共有>停止優先 選択。これらの属性がすべて等しい場合、それらは等しいとのみみなされます。 。 🎜
compareFlightPrice(a, b) , if ab と ab は両方とも非共有かつノンストップであるため、a が最初にランク付けされますが、<code>compareFlightPrice(b, a)
が呼び出された場合は、b が最初にランク付けされます。 a が 1 位にランクされるためには、a が非共有非停止であり、b が非共有非停止ではないかを判断する必要があります。 🎜🎜もちろん、比較関数を変更することに加えて、別の解決策があります。それは、JVM に起動パラメーターを追加することです。 🎜rrreee🎜また、セット内に等しい要素が存在することを必ずしも意味するわけではなく、比較関数が上記の厳密な定義を満たしていないことにも注意してください。実際、この例外は確実に安定して表示されます。実際、Java は、実稼働環境で発生する例外は非常に小さいので、最初に配列全体をチェックするほど愚かではありません。実際、ソート処理中にこの条件を満たしていないことがわかります。したがって、ある種の収集命令により、この判断を回避できる可能性があります。 🎜以上がJava ソート レポート: 比較メソッドは一般規約の例外ソリューションに違反していますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











一部のアプリケーションが適切に機能しないようにする会社のセキュリティソフトウェアのトラブルシューティングとソリューション。多くの企業は、内部ネットワークセキュリティを確保するためにセキュリティソフトウェアを展開します。 ...

多くのアプリケーションシナリオでソートを実装するために名前を数値に変換するソリューションでは、ユーザーはグループ、特に1つでソートする必要がある場合があります...

システムドッキングでのフィールドマッピング処理は、システムドッキングを実行する際に難しい問題に遭遇することがよくあります。システムのインターフェイスフィールドを効果的にマッピングする方法A ...

intellijideaultimatiateバージョンを使用してスプリングを開始します...

データベース操作にMyBatis-Plusまたはその他のORMフレームワークを使用する場合、エンティティクラスの属性名に基づいてクエリ条件を構築する必要があることがよくあります。あなたが毎回手動で...

Javaオブジェクトと配列の変換:リスクの詳細な議論と鋳造タイプ変換の正しい方法多くのJava初心者は、オブジェクトのアレイへの変換に遭遇します...

Redisキャッシュソリューションは、製品ランキングリストの要件をどのように実現しますか?開発プロセス中に、多くの場合、ランキングの要件に対処する必要があります。

eコマースプラットフォーム上のSKUおよびSPUテーブルの設計の詳細な説明この記事では、eコマースプラットフォームでのSKUとSPUのデータベース設計の問題、特にユーザー定義の販売を扱う方法について説明します。
