我如何使用随机断开关系的比较器进行排序？

Question

我正在构建一个模拟体育联赛的程序，而且我经常想按积分、净胜球等对球队进行排序，以确定哪支球队获得晋级或哪支球队获得优先种子比赛。但是，有时，团队会在我想使用的所有标准上打成平手，我希望这些平局可以随机打破。我以前使用团队的 id（这是唯一的整数）来打破平局，但我想这样做，以便没有团队在这种排序中得到一致的优惠待遇。我知道如果我只是让 Java 决定哪支并列球队将排在另一支球队的前面，那将是非常不可预测的，但我不相信它实际上是随机的，而且我担心它会无意中给一些团队带来优势。

我一直在使用 Collections.sort() 和比较器来进行排序，我最近才这样做，并将我的比较器切换为使用随机数作为最终决胜局而不是团队 ID .这是有问题的比较器：

public static final Comparator<Team> pointsGDRand = new Comparator<Team>() {
    public int compare(Team a, Team b) {
        int result = b.getStats().getPts() - a.getStats().getPts();
        if (result == 0) {
            result = b.getStats().getGD() - a.getStats().getGD();
            if (result == 0) {
                result = R.boolNum();
            }
        }
        return result;
    }
};

我认为 getter 函数是不言自明的，但这是随机函数：

public static int boolNum() {
    return r.nextBoolean() ? 1 : -1;
}

但是，就在不久前（这个错误弹出似乎很久了），我得到了这个错误：

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!

我读了一点书，我认为问题很可能是我在某些情况下发现 A > B 和 B > C，还有 A < C。这说明了一些问题为什么要花这么长时间才弹出这个错误（在弹出这个错误之前可能做了 20,000 次排序），因为 2 个团队在 all 标准上获得完全相同的分数似乎是对我来说很少见，更不用说 3 个或更多了。

我宁愿不写我自己的自定义排序，我也宁愿在每次排序之前不打乱有问题的列表（我觉得那样效率很低，但我有信心会工作）。

那么，我怎样才能制作一个随机打破平局的比较器（这样就不会有团队不成比例地赢得平局的风险）而不会再次出现同样的错误？

Answer 1

我们需要使用一个额外的属性来比较并列球队。此属性需要在比较器的生命周期内保持不变，但从一个比较器到下一个比较器是随机的。

每次需要排序时创建一个新的比较器，并确保它以可预测但随机的方式运行：

class PointsGDRandComparator implements Comparator<Team> {
    // each comparator has a different seed
    private final long seed = new Random().nextLong();

    public int compare(Team a, Team b) {
        int result = b.getStats().getPts() - a.getStats().getPts();
        if (result == 0) {
            // every time we compare a particular team, the same random number will be produced
            long aValue = new Random(seed * a.getTeamId()).nextLong();
            long bValue = new Random(seed * b.getTeamId()).nextLong();
            return Long.compare(aValue, bValue);
        }
        return result;
    }
}

所以每个比较器都会有不同的随机数 seed，但每个随机决策都是相同的，因为我们使用基于比较器 seed 的种子创建新的 Random 实例以及两队的id。

我们仍然基于团队 ID 的函数进行排序（因为我们需要在比较团队之间建立对称和传递关系）。

使用相同种子创建的两个 Random 实例将产生相同的随机数序列。因此，每当我们将 ID 为 45 的团队与另一个团队进行比较时，我们将创建一个带有种子 seed * 45 的 Random 实例（其中 seed 在整个生命周期内保持不变比较器），因此我们第一次调用 nextLong() 任何使用该种子创建的 Random 实例时，我们将始终获得相同的数字。

这里有一个不那么棘手的方法来做同样的事情。它假定 Team 具有正确的 hashCode 和 equals 实现，因此我们可以将其用作 Map:

中的键

class PointsGDRandComparator implements Comparator<Team> {
    private final Map<Team,Long> tiebreakers = new HashMap<>();
    
    public PointsGDRandComparator(List<Team> teams) {
        Random r = new Random();
        for (Team t : teams) {
            tiebreakers.put(t, r.nextLong());
        }
    }

    public int compare(Team a, Team b) {
        int result = b.getStats().getPts() - a.getStats().getPts();
        if (result == 0) {
            return Long.compare(tiebreakers.get(a), tiebreakers.get(b));
        }
        return result;
    }
}

上面的解决方案很昂贵，因为它创建了一个大小为团队列表的地图，并为每个团队创建了一个随机数。除非你有成千上万的团队，这无关紧要，但我们可以通过延迟填充地图来降低成本：

class PointsGDRandComparator2 implements Comparator<Team> {
    private final Map<Team,Long> tiebreakers = new HashMap<>();
    private final Random r = new Random();

    public int compare(Team a, Team b) {
        int result = b.getStats().getPts() - a.getStats().getPts();
        if (result == 0) {
            return Long.compare(
                    tiebreakers.computeIfAbsent(a, t -> r.nextLong()), 
                    tiebreakers.computeIfAbsent(b, t -> r.nextLong())
            );
        }
        return result;
    }
}

Answer 2

这是随机选择并列球队的另一种方法

使用地图。

存储地图中并列的球队，以他们的分数作为键值。地图可以是树形图，这样可以排序。
然后遍历地图并从每个列表中随机选择一个团队。

以下是任何处理前的团队。输出是比分和队名。

[3, A]
[1, B]
[2, C]
[0, D]
[0, E]
[1, F]
[1, G]
[2, H]
[2, I]
[2, J]

现在构建团队地图。

Map<Integer, List<Team>> team = teams.stream().collect(
   Collectors.groupingBy(t->t.getStats().getPts(),
        ()->new TreeMap<Integer,List<Team>>(Comparator.reverseOrder()),
            Collectors.toList()));

这是球队的地图，按得分降序排列。键是分数，值是具有该分数的球队列表。

3=[[3, A]]
2=[[2, C], [2, H], [2, I], [2, J]]
1=[[1, B], [1, F], [1, G]]
0=[[0, D], [0, E]]

现在，只需从每个列表中为给定分数选择一个随机值。这会在 0 和列表中的值数 (i.e. size())

之间选择一个值

Random r = new Random();
for (Entry<Integer, List<Team>> e : team.entrySet()) {
    int pick = r.nextInt(e.getValue().size());
    System.out.println(e.getKey() + " " + e.getValue().get(pick));

为此运行印刷

3 [3, A]
2 [2, C]
1 [1, B]
0 [0, E]

我如何使用随机断开关系的比较器进行排序？

How can I sort using a comparator with ties broken randomly?

java

sorting

random

comparator