java - 由于数值精度错误而违反 compareTo 传递契约的影响

Question

我有一些数字要比较。它们代表通过不同空间的路径长度。

对我来说不幸的是，一些不精确导致了错误的比较。例如，在注意到错误的效果后，我发现我在进行这样的比较:

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

为了我的目的，a 和 b 应该是相等的。

我注意到 guava 有一个用于 double 的 fuzzyCompare() 方法，它似乎做了我想做的，忽略了一些这种精度:

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();
    }
}

关于模糊比较的警告并没有引起我的注意:

This is not a total ordering and is not suitable for use in Comparable.compareTo(T) implementations. In particular, it is not transitive

我的问题是，传递性的缺乏是一个真正的问题吗？如果是，它将如何呈现自己？我认为，如果比较确实被违反，它会抛出类似于 this question: Java error: Comparison method violates its general contract 的错误，并且即使针对我测试过的各种值，它也不会这样做。

或者也许因为 IllegalArgumentException 是一个运行时错误，我只是还没有遇到问题，因为只有一些不正当的值才会触发问题？

或者也许它现在做错了什么，只是非常微妙以至于我没有注意到它？

Answer 1

长话短说:

您的运算符不可传递。考虑 a = 0 , b = 0.6 , c = 1.2公差为 1 . a==b , b==c但是a!=c .解决方案是将您的值划分为类(例如通过舍入或截断)并使用 Double.compare()以保持传递性。

详细解释:

首先让我们讨论在使用 fuzzyCompare(double, double, double) 时您的数据是否可传递:

虽然在大多数情况下您的数据将是可传递的，但可以生成不是可传递的样本。让我们采用以下值:

a = 384.52710054120
b = 384.52710054126
c = 384.52710054132

如您所见，使用我们的新指标，以下内容为真:a==b , b==c ，但是a!=c .可以看到，你违反了transitivity .

如果您的 Comparator 有问题吗？是不可传递的？

方法通过使用文档和/或注释来声明某些条件。 compare方法 promise 该方法是可传递的。在传递性不重要的情况下，违反该 promise 可能没问题，但依赖于该 promise 的代码可能会被破坏。

如果传递性的 promise 被破坏，可能无法运行的代码示例是什么？

让我们创建一个场景，其中我们有 3 个类型为 Foo 的元素根据一些 Comparator 是不可传递的称为 fooComparator .我们称它们为f1 , f2和 f3 .

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

由于它们不可传递，我们假设 f0 < f1 , f1 < f2 , f2 < f0成立。如果你把它们放在一个列表中并尝试 sort() 会发生什么？他们？

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

如何解决问题

您可以通过将数据映射到另一个数据集并使用在该数据集上定义的传递运算符来创建传递运算符。让我们将实数映射到精度较低的实数。

考虑以下值:

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

如果将它们截断到第二位 ( Math.truncate(x * 10)/10 ) 并使用 Double.compare() , 传递性被保留。

你可以看到我们已经将我们的值分为三类{a, b} < {c, d} < {e} .肯定有一些重要的定理证明是这样的，但我不记得它的名字了..