14

如何实现java.util.Comparator根据偏序关系对其元素进行排序？

例如给定一个偏序关系a ≺ c , b ≺ c；a和b的顺序是不确定的。

由于Comparator需要总排序，因此实现对未定义部分排序的元素进行任意排序但保持一致。

下面的工作吗？

interface Item {
    boolean before(Item other);
}

class ItemPartialOrderComperator implements Comparator<Item> {
    @Override
    public int compare(Item o1, Item o2) {
        if(o1.equals(o2)) {  // Comparator returns 0 if and only if o1 and o2 are equal;
            return 0;
        }
        if(o1.before(o2)) {
            return -1;
        }
        if(o2.before(o1)) {
            return +1;
        }
        return o1.hashCode() - o2.hashCode(); // Arbitrary order on hashcode
    }
}
  • 这个比较器的顺序是传递的吗？
    （我担心不是）
  • Comparators必须是可传递的吗？
    （当用于 a 时TreeMap）
  • 如何正确实施？
    （如果上面的实现不起作用）
    （哈希码可能会发生冲突，为简单起见，示例会忽略冲突；请参阅Damien B对在 Java 中对 *any* 类的所有实例实施总排序以对哈希码进行故障安全排序的回答.)
4

6 回答 6

9

问题是，当您有不可比较的元素时，您需要回退到比比较哈希码更聪明的方法。例如，给定一个偏序 {a < b, c < d}，哈希码可以满足 h(d) < h(b) < h(c) < h(a)，这意味着 a < b < c < d < a （粗体表示被哈希码打破的平局），这将导致 a 出现问题TreeMap。

一般来说，除了事先对键进行拓扑排序外，您可能无事可做，因此欢迎您提供有关您感兴趣的部分顺序的一些详细信息。

于 2013-05-22T14:55:19.353 回答
8

这似乎更像是一个答案而不是评论，所以我会发布它

文档说：

立即从比较合同得出，商是 S 上的等价关系，而强加的排序是 S 上的全排序。”

所以不，比较器需要总排序。如果您使用部分排序来实现这一点，那么您将违反接口合同。

即使它可能在某些情况下工作，您也不应该尝试以违反接口合同的方式解决您的问题。

请参阅有关适合偏序的数据结构的这个问题。

于 2013-05-22T14:55:07.290 回答
2

每当我尝试将哈希码用于此类事情时，我都会后悔。如果您的排序是确定性的，您会更高兴 - 如果没有别的，可以调试。下面将通过为以前未遇到的任何索引创建一个新索引Item并在所有其他方法都失败时使用这些索引进行比较来实现这一点。

请注意，排序仍然不能保证是可传递的。

class ItemPartialOrderComperator implements Comparator<Item> {
    @Override
    public int compare(Item o1, Item o2) {
        if(o1.equals(o2)) {
            return 0;
        }
        if(o1.before(o2)) {
            return -1;
        }
        if(o2.before(o1)) {
            return +1;
        }
        return getIndex(o1) - getIndex(o2);
    }

    private int getIndex(Item i) {
        Integer result = indexMap.get(i);
        if (result == null) {
            indexMap.put(i, result = indexMap.size());
        }
        return result;
    }

    private Map<Item,Integer> indexMap = new HashMap<Item, Integer>();
}
于 2013-05-22T22:01:39.980 回答
1

在 jdk7 中，您的对象将抛出运行时异常：

领域：API：实用程序概要：更新了数组和集合的排序行为可能会引发IllegalArgumentExceptionjava.util.Arrays.sort描述：由和（间接） 使用的排序算法java.util.Collections.sort已被替换。
如果新的排序实现检测到违反 Comparable 合同的 Comparable，它可能会抛出IllegalArgumentException 。之前的实现默默地忽略了这种情况。如果需要以前的行为，您可以使用新的系统属性java.util.Arrays.useLegacyMergeSort, 来恢复以前的合并排序行为。

不兼容的性质：行为
RFE：6804124

于 2013-05-22T14:59:12.340 回答
0

如果a < b和b < c暗示a < c，那么您已经使用 hashCodes 进行了总排序。拿a < d, d < c。部分顺序表示b并且d不一定是有序的。通过引入 hashCodes 你提供了一个排序。

示例：is-a-descendant-of(human, human)。

Adam (hash 42) < Moses (hash 17), Adam < Joe (hash 9)

暗示

Adam < Joe < Moses

一个负面的例子是相同的关系，但是当时间旅行允许成为你自己的后代时。

于 2013-05-22T15:19:15.370 回答
-1

当一项既不是“之前”也不是“之后”另一项时，不返回哈希码的比较，而是返回0。结果将是重合项目的“总排序”和“任意”排序。

于 2013-05-22T14:51:29.673 回答