Java 具有相对距离的比较器

Question

我正在尝试创建一个使用相对距离比较的有序地图。然而，ConcurrentSkipListMap（这是我目前正在使用的）解释 Comparator 比较的方式使得比较相对距离变得不可能。是否有任何数据结构允许像键值操作和相对排序这样的映射？

当我说相对比较时，我的意思是两个值不能直接比较，而必须用一个参考点来看待。像欧几里德距离一样思考。

编辑：

例如：在比较二进制数0011和1100时我想说一个比另一个大基于汉明距离（两个数字异或中1的位数，相当于两个节点之间的距离一个超立方图），显然我需要一个参考点来比较距离，所以我选择 0000 作为参考。 0011到0000的距离是2，1100到0000的距离是2，但是1100不等于0011。我想说它们的相对距离相同，但不相等。最终将生成这些数字的排序列表。对于参考 0000，按升序排列，我们可能有 1000、0100、1100、1001、0011、1110、1101、1111。

EDIT2，为什么我不能使用比较器：

The quotient for this total order is: {(x, y) such that c.compare(x, y) == 0}.

It follows immediately from the contract for compare that the quotient is an equivalence relation on S, and that the imposed ordering is a total order on S. When we say that the ordering imposed by c on S is consistent with equals, we mean that the quotient for the ordering is the equivalence relation defined by the objects' equals(Object) method(s): {(x, y) such that x.equals(y)}.

http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html

Answer 1

几个 Set 实现允许比较器与 equals 不一致。如果 ConcurrentSkipListMap 不存在，那么您的选择是使用一个存在的集合或使用无序集合，然后在插入时使用 Collection.sort.

手动对其进行排序

下面是创建Comparator的例子（与equals不一致）：

class Point {
    int distanceTo(Point other) {
        ...
    }

    Comparator<Point> distanceComparator() {
        return (point1, point2) -> distanceTo(point1) - distanceTo(point2);
    }
}

List<Point> points;
Point fixedPoint;
Collections.sort(points, fixedPoints.distanceComparator());

这现在将按 points 到 fixedPoint 的距离排序。或者，出于效率原因，您可以使用集合已经排序的事实，以便在添加新项目时插入到正确的位置：

您参考了 Comparator 的文档，特别是关系的群论定义。关键条件是如果两个项目是 equals 那么他们比较时必须 return 0。然而相反的情况肯定不是这样：如果两个项目 return 0 比较时这并不一定意味着它们是 equals。在很多情况下，两个项目的顺序是不确定的。一个简单的例子是忽略大小写的字典排序。在这种情况下，单词 "Foobar"、"foobar" 和 "FOOBAR" 就顺序而言都是 'equal'。

这在文档中称为 'inconsistent with respect to equals'。例如 SortedSet 的文档说 "The behavior of a sorted set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface." 对于 Set.

的所有实现并非如此

Answer 2

当距离相同时，您可以通过进一步比较来区分与参考编号具有相同距离的实例。例如，假设您将数字表示为 Integers:

    public int compare(Integer i1, Integer i2) {
        Integer r1 = hammingDistanceToReference(i1);
        Integer r2 = hammingDistanceToReference(i2);

        if (!r1.equals(r2))
            return r1.compareTo(r2);

        return i1.compareTo(i2);
    }

这样，与参考汉明距离不同的数字将被正确排序，而具有相同汉明距离的数字也将完全排序。

Java 具有相对距离的比较器

Java comparator with relative distance

java

dictionary

distance

comparator

data-structures