个人中心
gpt4 book ai didi

java - 当 "equality"暗示 "order doesn' t 重要时，如何编写传递比较器”？

转载 作者：搜寻专家 更新时间：2023-11-01 03:21:57 26 4
gpt4 key购买 nike

<分区>

我有一组序列化到文件中的项目。有些项目可以依赖其他项目，但不允许循环引用。因此，它们需要以某种方式序列化，如果 A 依赖于 B，则 B 首先在文件中序列化。

我编写了我的 Comparator，它使用 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() 方法？

编辑:有人指出我正在对有向无环图执行拓扑排序。我正在记忆我的数据结构类(class)。幸运的是，维基百科似乎有一个很好的线性时间算法来执行这种排序 - 我会试一试。

26 4 0
文章推荐： java - 将 double[] 包装成 Double[]
文章推荐： ios - GPUImageMovie 使用多个图像作为纹理和过程
文章推荐： iphone - 在 iOS 中将图像元数据写入 JPG/PNG 文件
文章推荐： ios - Xcode 6 - 无法找到或生成匹配的签名 Assets
搜寻专家
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com