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

Question

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

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

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

为了我的目的,a和b应该是平等的.

我注意到番石榴有一种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();
    }
}

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

这不是总排序,不适合在Comparable.compareTo(T)实现中使用.特别是,它不具有传递性

我的问题是,这种缺乏传递性是一个真正的问题吗？如果是的话,它会如何呈现？我认为,如果比较真的被真正违反了,它会抛出类似于这个问题 的错误:Java错误:比较方法违反了它的一般合同,并且它甚至没有对我测试的各种值进行这样做.

或者因为一个IllegalArgumentException是运行时错误,我还没有遇到问题,因为只有一些不正确的值会引发问题？

或者也许它现在正在做错事,它只是微妙到我没注意到它？

Answer 1

TL; DR:

您的运营商不具有传递性.考虑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.如您所见,您违反了传递性.

如果你Comparator是不可传递的,这是一个问题吗？

方法通过使用文档和/或注释来断言某些条件.该compare方法承诺该方法是传递性的.对许多案例来说,打破这种承诺可能是好的,因为传递性并不重要,但依赖于这种承诺的代码可能会被打破.

如果传递的承诺被打破,那么代码的例子可能不起作用？

让我们创建一个场景,我们有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}.肯定有一些重要的定理证明了这种情况,但我不记得它的名字..