compare
関数を含むクラス）を作成できます。 コンパレータの代わりにオブジェクトの自然な順序があります。オブジェクトは
Comparable
インターフェイスを実装します。このインターフェイスには、このオブジェクトを別のオブジェクトと比較できる
compareTo
メソッドが含まれています。 比較関数は、オブジェクトが等しい場合は0を返し、最初のオブジェクトが2番目よりも小さい場合は負の数（通常-1）を返し、最初のオブジェクトがより多い場合は正の数（通常1）を返します。 通常、このような関数の実装は難しくありませんが、多くの人が忘れているケースが1つあります。
比較は、ソートやバイナリ検索から
TreeMap
などのソートされたコレクションの順序の維持まで、さまざまなアルゴリズムで使用されます。 これらのアルゴリズムは、比較関数の3つの重要なプロパティに関連付けられています：反射性（要素と常に0を与える）、反対称性（AとBおよびBとAを比較することは異なる符号を与えるはずです）および推移性（AとBを比較する場合、BとCを与える場合同じ符号で、AとCを比較すると同じ結果になります）。 比較関数がこれらのプロパティを満たさない場合、アルゴリズムは完全に予測不可能な結果を生成する可能性があります。 ほとんどの場合、例外は発生せず、結果が正しくありません。
判明したように、これらのプロパティに準拠していないことはそれほどまれな状況ではありません。 問題は、実数（floatまたはdouble）を比較するときに発生します。
double型のフィールドを持つクラスがあり、フィールドの値に応じてこのクラスのオブジェクトを順序付けするとします。 多くの場合、このコードを見つけることができます。
public class DoubleHolder implements Comparable<DoubleHolder> { double d; public DoubleHolder(double d) { this.d = d; } @Override public int compareTo(DoubleHolder o) { return d > od ? 1 : d == od ? 0 : -1; } @Override public String toString() { return String.valueOf(d); } }
上記のcompareToメソッドには2つの問題があります。 最初のものは重要ではありません-
new DoubleHolder(-0.0).compareTo(new DoubleHolder(+0.0))
と-0.0を区別しません：
new DoubleHolder(-0.0).compareTo(new DoubleHolder(+0.0))
は0を返します。 orderいように見える注文。 それにもかかわらず、これらはすべてNaNと比較すると些細なことです。 数値NaN（doubleとfloatの両方）は、かなり具体的なものです。 それはそれ以上でも、それ以上でも、他の数字とも等しくありません。 その結果、すぐに比較プロパティの違反が発生します。
DoubleHolder nan = new DoubleHolder(Double.NaN); DoubleHolder zero = new DoubleHolder(0.0); System.out.println("nan.compareTo(nan): "+nan.compareTo(nan)); System.out.println("nan.compareTo(zero): "+nan.compareTo(zero)); System.out.println("zero.compareTo(nan): "+zero.compareTo(nan));
nan.compareTo(nan): -1 nan.compareTo(zero): -1 zero.compareTo(nan): -1
反射性も反対称性も観察されません。 このような比較実装も見つけることができます。
public int compareTo(DoubleHolder o) { return d > od ? 1 : d < od ? -1 : 0; }
ここでは、以前の3つの比較すべてがゼロ、つまりプロパティが観察されているかのようになります。 しかし、もちろん、それを喜ぶには早すぎます：
DoubleHolder nan = new DoubleHolder(Double.NaN); DoubleHolder zero = new DoubleHolder(0.0); DoubleHolder one = new DoubleHolder(1.0); System.out.println("zero.compareTo(nan): "+zero.compareTo(nan)); System.out.println("nan.compareTo(one): "+nan.compareTo(one)); System.out.println("zero.compareTo(one): "+zero.compareTo(one));
zero.compareTo(nan): 0 nan.compareTo(one): 0 zero.compareTo(one): -1
ここでは、推移性が侵害されています。最初のオブジェクトは2番目に等しく、2番目は3番目に等しく、最初のオブジェクトは3番目に等しくありません。
単純な素人にとってこれはどういう意味ですか？ これを理解するには、簡単なリストを作成し、それを数回混合してソートしてみてください。
List<DoubleHolder> data = new ArrayList<>(); for(int i=1; i<=10; i++) { data.add(new DoubleHolder(i)); } data.add(new DoubleHolder(Double.NaN)); for(int i=0; i<10; i++) { Collections.shuffle(data); Collections.sort(data); System.out.println(data); }
各実行の出力は異なり、たとえば次のようになります。
[NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, NaN, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, NaN, 1.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 10.0, NaN, 9.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, NaN, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0]
または、
compareTo
の2番目の実装の場合：
[1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 8.0, 9.0, NaN, 7.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 9.0, 10.0, NaN, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [2.0, 6.0, NaN, 1.0, 3.0, 4.0, 5.0, 7.0, 8.0, 9.0, 10.0] [2.0, 4.0, NaN, 1.0, 3.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 3.0, NaN, 2.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN]
約半分のケースでは、NaNを持つ要素がソートされたリストの最初または最後に釘付けされ、他のケースでは、周囲の要素の順序を台無しにしてさまよい始めます。
DoubleHolder
をキーとして使用するコレクションでは、良いことも起こりません。
TreeSet
を例にとります。
compareTo
の2番目の実装では
compareTo
すべてが非常に単純です
compareTo
を含む要素は他の要素と等しいため、そのような要素が既に存在すると判断するため、空でないセットに挿入できません。 ただし、最初にNaN要素を挿入した場合は注意してください。その後、セットには何も出力されません。
比較機能の最初のバージョンはサイケデリックです。 たとえば、このようなテストを書きましょう：
Set<DoubleHolder> set = new TreeSet<>(); for(int i=0; i<50; i++) { set.add(new DoubleHolder( i%10==0 ? Double.NaN : i%10 )); } System.out.println(set);
NaNを含む5つの要素と、1〜9の各数字を含む5つの要素を挿入しました。その結果、次のようになります。
[NaN, NaN, 1.0, 2.0, 3.0, NaN, NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, NaN]
NaNを5回見ることが予想されます。それらは互いに等しくありません。 しかし、誤った比較により、他のいくつかの要素が数回挿入されました。 TreeMapで何が起こるかを自分で確認できます。 NaNを誤ってヒットすると、コレクション全体が破壊される可能性があります。これは必ずしもデバッグが容易ではないことに注意してください。コレクションは、誤った状態で長期間存在し、すべてが正常であるふりをすることができます。
奇妙なことに、この問題はまったく存在しないはずです。 JDK 1.4に戻り、Float.compareおよびDouble.compareと呼ばれる特別な静的メソッドが登場しました。これらのメソッドは、すべての処理を行い、特殊なケースを正しく処理します。 書くことだけが必要です：
public int compareTo(DoubleHolder o) { return Double.compare(d, od); }
どうやら、比較アルゴリズムの見かけ上の単純さが影響します。プログラマーは、これを行うための標準的な方法についてドキュメントを調べるよりも自分で書く方が簡単だと考えることがあります。
さまざまなオープンソースプロジェクトでの不正なdouble / float比較の例： JTS 、 Batik 、 Hadoop 、 Hudson 、 ICU4J 、 Lucene どのような場合にこれが問題を引き起こす可能性があるかを判断することは困難ですが、これは私が無条件に修正する場合です：正しく信頼できるオプションは通常、間違ったオプションよりも短くなります。
状況を変えるために、FindBugs用の小さな検出器を作成しました。これは、誤って実装された比較関数を検出し、Float.compare / Double.compareの使用を提案します。
一般に、すべてのプリミティブ型には、同様の方法があります。 複数のフィールドを順番に比較する必要がある場合は、次のように記述できます。
public class MyObject implements Comparable<MyObject> { double d; int i; String s; char c; @Override public int compareTo(MyObject o) { int result; result = Double.compare(d, od); if(result != 0) return result; result = Integer.compare(i, oi); if(result != 0) return result; result = s.compareTo(os); if(result != 0) return result; result = Character.compare(c, oc); return result; } }
多かれ少なかれブランチの束よりも良く見えます。 そして、 グアバなどを使用する場合、次のようになります。
@Override public int compareTo(MyObject o) { return ComparisonChain.start() .compare(d, od) .compare(i, oi) .compare(s, os) .compare(c, oc) .result(); }