一尘不染

部分订购的比较器

algorithm

如何实现java.util.Comparator根据部分顺序关系对元素进行排序?

例如,给定的部分顺序关系 一个ÇbÇ ; ab 的顺序不确定。

由于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需要传递?
    (用于时TreeMap

  • 如何正确实施? (如果上面的实现不起作用)
    (哈希码可能会发生冲突,为简单起见,冲突示例会忽略冲突;请参见Damien B对在Java中对 any
    类的所有实例施加总排序的答案,以了解对哈希码的故障保护排序)


阅读 195

收藏
2020-07-28

共1个答案

一尘不染

问题是,当您拥有无法比拟的元素时,您需要退回到比比较哈希码更聪明的地方。例如,给定部分顺序{a <b,c
<d},哈希码可以满足h(d)<h(b)<h(c)<h(a),这意味着a <b < c <d < a( 粗体
表示用哈希码打断领带),这将导致a出现问题TreeMap

通常,除了事先对密钥进行拓扑排序之外,您可能不需要做任何事情,因此欢迎您提供部分感兴趣的部分的详细信息。

2020-07-28