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

Question

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

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

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

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

我注意到双打的 guava has a 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

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。可以看到，你已经违反了transitivity.

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

方法通过使用文档 and/or 注释断言某些条件。 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}。肯定有一些重要的定理证明是这样的，但我不记得它的名字了..

Answer 2

is this lack of transitivity a real problem

也许吧，这取决于您要解决的问题。但是您可能会运行陷入微妙的问题，其中代码期望 Comparator 的实现以传递方式工作。很难说效果是什么，除了 "undefined".

如果我在评论中看到这段代码，我将不会很高兴：您将 Java 明确定义的比较概念与您自己的 - 有效但不同的 - 比较概念重载。

如果您将其命名为不同的名称 - fuzzyCompare、FuzzyComparator 等 - 这两个概念不会混淆。

Answer 3

使用非传递 compareTo 是个糟糕的主意：

排序可能会抛出 already pointed。
更糟糕的是，排序可能 return 错误的结果，可能完全错误。它依赖于您违反的合同，并且绝对不能保证它最终会很好（即有例外）。分析 TimSort 无济于事，因为该算法可能会在几年内被更好的算法取代。
任何 SortedMap 都可能崩溃。可能会发生你放置的东西找不到的情况（这样的事情确实发生在 HashMap 和损坏的 equals 或 hashCode 上）。同样，实施可能会在几年内发生变化，然后一切皆有可能。

我强烈建议您以不同的方式命名您的方法。或者，创建一个带有相应警告的 Comparator 文档（这可能会导致相同类型的问题，但更为明确）。

请注意，如果 Comparable 损坏，即使是 HashMap 也可能会损坏，因为在多次碰撞的情况下，它会尽可能使用 compareTo。

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

Effects of violating compareTo transitivity contract due to numerical precision errors

java

guava

compareto

TL;DR:

详细解释：