Consequences of contract breach compareTo transitivity

Question

I have some numbers that I am trying to compare. They represent the lengths of paths through different spaces.

Unfortunately, for me, some inaccuracy caused false comparisons. For example, noticing the wrong effects, I found that I had such comparisons:

a=384.527100541296 b=384.52710054129614 //Note the trailing 14 

For my purposes, a and b should be equal.

I noticed that guava has fuzzyCompare() for doubles, which seems to do what I want, ignoring some of this precision:

 private static final double COMPARISON_PRECISION=1e-10; private static final Comparator<Double> fuzzyCompare= new Comparator<Double>(){ public int compare(Double o1, Double o2) { return DoubleMath.fuzzyCompare(o1, o2, COMPARISON_PRECISION); } }; public int compareTo(Object o) { if (o instanceof Spam){ Spam other=(Spam) (o); return ComparisonChain.start() .compare(this.getLength(),other.getLength(),fuzzyCompare) //... .result(); }else{ throw new ClassCastException(); } } 

A warning about this fuzzy comparison did not slip my notice:

This is not a complete order and is not suitable for use in Comparable.compareTo (T) Options. In particular, it is not transitive.

My question is, is this lack of transitivity a real problem? If so, how would he imagine himself? I would have thought that if the comparison were really broken, it would have generated an error similar to this question: Java error: the comparison method violates its general contract and does not even do this against the many values ​​that I tested.

Or, perhaps, since IllegalArgumentException is a run-time error, I just did not run into problems, because only some insidious values ​​would cause the problem?

Or, perhaps, now he is doing something wrong, is it subtle enough that I did not notice him?

Answer 1

TL; DR:

Your operator is not transitive. Consider a = 0 , b = 0.6 , c = 1.2 with a tolerance of 1 . a==b , b==c , but a!=c . The solution is to split your values ​​into classes (e.g. rounding or truncating) and using Double.compare() to maintain transitivity.

My question is, is this lack of transitivity a real problem?

First, let's discuss whether your data is transitive when using fuzzyCompare(double, double, double) :

While in most cases your data will be transitive, you can create patterns that are not. Take the following values:

 a = 384.52710054120 b = 384.52710054126 c = 384.52710054132 

As you can see, using our new metric, the following is true: a==b , b==c , but a!=c As you can see, you have violated transitivity .

Is this a problem if your Comparator not transitive?

The methods state certain conditions using documentation and / or annotations. The compare promises method that the method is transitive. Breaking this promise can be justified in many cases, since transitivity is not important, but the code that builds on this promise may be broken.

What is sample code that might not work if the promise of transitivity is broken?

Allows you to create a script in which there are 3 elements of type Foo that are not transitive according to some Comparator called fooComparator . We call them f1 , f2 and f3 .

 Comparator<Foo> fooComparator = new Comparator<Foo>(){ public int compare(Foo o1, Foo o2) { // some non-transitive return value } }; 

Since they are not transitive, let f0 < f1 , f1 < f2 , f2 < f0 satisfied. What happens if you put them in a list and try sort() them?

 List<Foo> foos = new LinkedList<>(); Collections.addAll(f1, f2, f3) Collections.sort(foos, fooComparator); 

How to fix the problem

You can create a transitive operator by matching data with another data set and using the transit operator defined on this set. Allows you to compare real numbers with real numbers with less accuracy.

Consider the following values:

 a = 0.01; b = 0.05; c = 0.13; d = 0.19; e = 0.21 

If you truncate them to the second digit ( Math.truncate(x * 10)/10 ) and use Double.compare() , transitivity is preserved.

You can see that we put our values ​​in three classes {a, b} < {c, d} < {e} . Undoubtedly, there is some important theorem which proves that this is so, but I cannot recall its name.

Answer 2

is the lack of transitivity of the real problem

It may depend on the problem you are trying to solve. But you may run into small problems when the code expects a Comparator implementation to work in a transitive way. It’s hard to say what effects are other than “undefined”.

I would not be very pleased if I saw this code in a review: you are overloading Java with a well-defined concept of comparison with your own - valid, but different - concept of comparison.

If you call it something else - fuzzyCompare , FuzzyComparator , etc., there is no confusion between the two concepts.

Answer 3

Using nontransitive compareTo is a terrible idea:

• Sort may be displayed as already indicated .
• Worse, sorting can lead to incorrect results, possibly completely wrong. It relies on a contract that you violate, and there is absolutely no guarantee that it will end well (that is, with the exception). TimSort analysis TimSort not help, as the algorithm can be replaced by the best in a few years.
• Any SortedMap can be severely affected. It may happen that the things you placed are not found (such things really happen with a HashMap with broken equals or hashCode ). Again, the implementation may change in a few years, and then everything is possible.

I would strongly suggest calling your method differently. Or create a Comparator , documented by an appropriate warning (this can lead to the same problems, but much more explicit).

Please note that with a broken Comparable even a HashMap can break, as in the case of many collisions, it uses compareTo when possible.