ComparatorからCollections.sortに非推移的なものを入力するとどうなりますか？無限ループに陥ることはできますか？非過渡コンパレータ「仕事」によるソートはありますか？
私が書いた小さなテストでは、出力が得られましたが、これが常に正しいことを確認したいと思います。
問題は、コンパレータがサイクルを生成することがあり、この場合は無限ループにならないようにしたいということです。私は実際の結果を気にしません。
Java docsは、コンパレータが推移的であることを確認する必要があると言います。要求されたものを遵守しないコンパレータを供給すると、すべてのベットはオフになります。それは与えられた実装ではうまくいくかもしれませんが、別のものでひどくクラッシュするかもしれません（C++のstd::sort）。
要するに、いくつかの例や他の例でも機能しているとは限りません。
はい...それは理にかなっています。私はそれに頼るべきではありません、ありがとう。 – duduamar
こんにちはパブロ。コメントをハイジャックして申し訳ありませんが、ここで質問しました： https://stackoverflow.com/questions/45599509/why-does-stdsort-segfault-with-non-transitive-comparators C++ std :: sortが非推移的コンパレータでクラッシュする今日の私が直面している問題に明らかに直面しています。なぜあなたが知っていたのだろうかと思っていたのですか？ もう一度、6歳のコメントをハイジャックして申し訳ありませんが、この件に関するデータはほとんどありません。 –
Collections.sort()は、mergesortに基づいています。
mergesortは配列サイズが常に分割されているため、全体的にO（logn）回の反復があるため、Comparatorが推移的ではないにもかかわらずsort（）は終了する必要があります。
結果リストの順序は保証されませんが、
この場合のCollections.sortの動作は実装に依存します。 Java 6 SEの実装では、MergesortとInsertionsortの組み合わせが使用されていますが、どちらも非推移的コンパレータでは確定的ですが、Java 7ではTimsortアルゴリズムが使用され、他の実装ではQuicksortなどが使用される可能性があります。すべての実装で動作します。
まず、私はあなたが比較について考えてみることをお勧めします - 本当に思いやりの操作です同値関係。 それはそうではないと受け入れるならば、それはあるローカル変数の比較されたオブジェクトを追跡する必要があります。 このローカル変数は、オブジェクトまたはスレッドローカル変数と比較することができます。 この変数は、比較されたオブジェクトペアのセットです。 と比較してメソッドの呼び出しをチェックします。このペアが訪問されたかどうかをチェックします。真の場合、何をすべきかを決定します。 しかし、訪問したオブジェクトのセットについては車に乗ってください。実際にはハッシュやオブジェクトIDのようなものが含まれているはずです。他の方法で無限に行くことができるからです。 また、ローカル変数に比較ペアを格納するとメモリが消費されることも考慮してください。
Java 7 Collections.sortはTimSortを使用しているため、 Java> = 7でソートする非推移的コンパレータを使用すると、次の例外がスローされます。
多分関連コードを投稿してください。 – pap
これは一般的な質問ですが、特定のコードには関係ありません。問題は、Collections.sortに推移しないコンパレータを提供する場合の動作です。 – duduamar
非推移的な 'Comparator'を使用する動作は定義されていません。非推移的な「Comparator」は正しく実装されていません**。実際には、 'Collections.sort（）'は 'Comparator'が壊れていても、無限ループでは実行されません。しかし、仕様*の何もこの動作を必要としません。 –