java - 我怎样才能摆脱不及物比较器？

Question

我有一个 Comparator<Foo>具有以下比较功能:

float d = o1.bar - o2.bar;
if (Math.abs(d) <= 0.001) {
    return 0;
} else {
    return d < 0 ? -1 : 1; // inline Math.copySign
}

本质上，这应该比较两个 Foo基于他们的 bar属性，除非值足够接近，在这种情况下它们应该被声明为相等。 (这很重要，因为在此之后我要在不同的属性上进行另一种排序。)

很明显，这不是传递比较器。如果有Foo s f1 , f2 , 和 f3值为 bar作为1.999 , 2.000 , 和 2.001 ，然后，根据我的比较器，f1==f2和 f2==f3但是f1 != f3 .

调用 sort(myListOfFoo, myFooComparator)给出了“比较方法违反了它的一般契约(Contract)!”错误很少，但具有确定性。

如何将这样的比较器与 Collections.sort(List, Comparator) 一起使用？而不会产生这个错误？

---

或者，有没有什么方法可以存储我的数据，让比较器正常工作？将每个 float 四舍五入到最近的 0.001 at construction 将是最简单的解决方案，除了 Foo.bar字段实际上是根据任意距离度量计算的，所以并没有那么简单。

实际代码是:

float d = metric.distance(vertex, o1)
        - metric.distance(vertex, o2);
if (Math.abs(d) < threshold) {
    return 0;
} else {
    return d < 0 ? -1 : 1; // inline Math.copySign
}

哪里o1 , o2 , 和 vertex是 class Point { float x; float y; } 的实例和 metric是 interface DistanceMetric { float distance(Point p1, Point p2); } 的实例.可能值得注意的是，即使在标准欧几里得度量上，这也是失败的。

Answer 1

恐怕 Java 7 排序实现不会容忍表现出不及物性的比较器。如果您想使用标准的 Java SE 排序 API，您对此无能为力。

---

但是，实际上，在排序中使用阈值比较在数学上是不正确的。

比较浮点值时的问题是它们开始时通常不精确，然后计算通常会在结果中引入更多的小错误。当两个结果足够接近时，累积误差可能大于值之间的差异......这意味着我们无法判断理想数字(没有误差)是小于、等于还是大于每个误差。我们通过使用阈值进行比较，将“接近等于”视为“相等”来处理此问题。

当我们对值进行排序(即按顺序排列)时，值中的错误问题需要以不同的方式处理。假设

• 我们有两个号码 v1 ± e1和 v2 ± e2 , 和

• 当我们使用阈值比较来比较数字时，阈值大于 mod(e1) + mod(e2)

如果结果是v1和 v2足够接近 mod(v1 - v2) < (mod(e1) + mod(e2))那么没关系如果我们把v1 ± e1在 v2 ± e2 之前或之后在订购中。如果我们观察两个数字的顺序(排序完成后)通过使用阈值进行比较，它们将显示为“相等”，无论我们将它们放在哪个顺序。

因此，如果我们忽略错误并简单地使用精确比较对数字进行排序，那么当我们使用基于阈值的比较时，我们不会将任何一对数字置于不正确的顺序中.

现在假设我们有 v1 ± e1 , v2 ± e2和 v3 ± e3 ... 和 mod(e1) + mod(e3)大于我们的阈值:

• 如果我们按上面的顺序排序(使用精确比较)，我们仍然会以正确的顺序得到数字。

• 如果我们使用“与阈值比较”来对值进行排序(并且排序实现允许这样做!)，我们最终可能会得到顺序为 v3 ± e3 的数字。 , v2 ± e2和 v1 ± e1 .我们有{v1 ± e1, v2 ± e2}和 {v2 ± e2, v3 ± e3}成对相等，但我们也可以有 {v1 ± e3, v3 ± e3}排序不正确，即使我们使用基于阈值的比较进行比较也是如此!

---

底线是您应该简单地实现您的Comparator (出于排序目的!)使用精确比较。对于这种情况，阈值比较是错误的。无论sort如何，这都适用。算法编码...