我有一组项目被序列化到文件中。某些项目会依赖于其他项目,但不允许循环引用。因此,它们需要以这样的方式进行序列化,即如果A依赖于B,则B首先在文件中进行序列化。
我编写了一个比较器,使用reliesOn()函数确定两个项目是否关联:
这在某些情况下是有效的,但并非所有情况都适用。在调试中,很明显排序依赖于 Comparator 的传递性,并且可以理解为不会比较每个可能的项目对。
例如,对于五个项目 A 到 E,如果:
至少,
然而,在比较阶段(以一个例子来解释),发生的是将
结果,排序算法假定
编辑:有人指出我正在对有向无环图进行拓扑排序。我回想起了我的数据结构课程。幸运的是,维基百科似乎有一个很好的线性时间算法来执行这个排序——我会尝试一下。
我编写了一个比较器,使用reliesOn()函数确定两个项目是否关联:
Collections.sort(itemsToSort, new Comparator<Item>() {
@Override
public int compare(Item first, Item second) {
boolean firstReliesOnSecond = reliesOn(first, second);
if (firstReliesOnSecond) {
return 1;
}
boolean secondReliesOnFirst = reliesOn(second, first);
if (secondReliesOnFirst) {
return -1;
}
return 0;
}
});
这在某些情况下是有效的,但并非所有情况都适用。在调试中,很明显排序依赖于 Comparator 的传递性,并且可以理解为不会比较每个可能的项目对。
例如,对于五个项目 A 到 E,如果:
A -> B
B -> E
C
D
E
那么一种可能的顺序是:
E, B, A, C, D
至少,
E
在B
之前,B
在A
之前。然而,在比较阶段(以一个例子来解释),发生的是将
C
与E
进行比较,返回0
,因为它们没有关系。然后将C
与B
进行比较,并且也返回0
。结果,排序算法假定
B = E
,这并非事实。(即使我违反了Comparator
合同)。我该如何编写我的compare()
方法以确保传递性?编辑:有人指出我正在对有向无环图进行拓扑排序。我回想起了我的数据结构课程。幸运的是,维基百科似乎有一个很好的线性时间算法来执行这个排序——我会尝试一下。
Comparator
应该满足的约定的结合。我会更新我的措辞,谢谢! - Craig OtisItem
的相关对象吗?是否有像getParents()
这样的方法? - aioobe