首页 文章

如何摆脱不及物比较？

提问于
浏览 次
2

我有 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
}

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

但显然，这不是一个传递性比较器 . 如果 f1 ， f2 和 f3 的值分别为 1.999 ， 2.000 和 2.001 ，则根据我的比较器， f1==f2 和 f2==f3 ，但 f1 != f3 .

调用 sort(myListOfFoo, myFooComparator) 很少给出"Comparison method violates its general contract!"错误，但确定性 .

如何在不产生此错误的情况下使用 Collections.sort(List, Comparator) 这样的比较器？

或者，有什么方法可以存储我的数据，使比较器正常工作？将每个浮点运算到最接近的 0.001 构造将是最简单的解决方案，除了 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); } 的实例 . 值得注意的是，即使按照标准欧几里德度量标准，这也是失败的 .

java sorting collections comparison comparator

2 回答

  • 2

    我担心Java 7排序实现不会容忍表现出不敏感的比较器 . 如果您想使用标准的Java SE排序API，那么您无能为力......

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

    比较浮点值时的问题是它们通常不精确，然后计算通常会在结果中引入更多的小错误 . 当两个结果足够接近时，累积误差可能大于值之间的差异......意味着我们无法判断理想数字（没有误差）是否小于，等于或大于每个误差 . 我们通过使用阈值进行比较将"close to equals"视为"equal"来解决这个问题 .

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

    • 我们有两个数字 v1 ± e1 和 v2 ± e2 ，和

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

    如果事实证明 v1 和 v2 足够接近 mod(v1 - v2) < (mod(e1) + mod(e2)) 那么我们在 v2 ± e2 之前或之后放置 v1 ± e1 并不重要 . 如果我们通过使用阈值进行比较来观察两个数字的排序（在完成排序之后），它们将显示为"equal"，我们将它们放入其中 .

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

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

    • 如果我们按照上面的顺序（使用精确比较），我们仍然会以正确的顺序结束数字 .

    • 如果我们使用"comparison with thresholds"对值进行排序（并允许排序实现！），我们最终可能会按照 v3 ± e3 ， v2 ± e2 和 v1 ± e1 的顺序输入数字 . 我们 {v1 ± e1, v2 ± e2} 和 {v2 ± e2, v3 ± e3} 成对相等，但我们也可能错误地排序 {v1 ± e3, v3 ± e3} ，即使我们使用基于阈值的比较进行比较！

    最重要的是，您应该简单地实现 Comparator （用于排序目的！）以使用精确比较 . 阈值比较对于此上下文是错误的 . 无论 sort 算法如何编码，这都适用...

    回复于
  • 0

    我想你真正想要做的是删除重复值（按你的门槛），然后对其余值进行排序 . 为什么不首先根据非舍入值进行自然排序，然后根据阈值使用过滤 .

    回复于

相关问题