如何使用隨機破壞關系的比較器進行排序？

我正在構建一個模擬體育聯賽的程式，而且，我經常想按積分、目標差異等對球隊進行排序，以確定哪支球隊獲得晉級或哪支球隊在錦標賽中獲得優先種子。但是，有時，團隊會在我想要使用的所有標準上捆綁在一起，我希望這些捆綁被隨機打破。我以前使用團隊的 ID（它們是唯一的整數）來打破平局，但我想這樣做，以便沒有團隊在這種排序中獲得一致的優惠待遇。我知道如果我只是讓 Java 決定將哪些并列的團隊放在另一個之前，這將是非常不可預測的，但我不相信它實際上是隨機的，我擔心它d 不經意間給了一些球隊一個優勢。

我一直在將 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 個團隊在所有標準上獲得完全相同的分數對我來說似乎非常罕見，更不用說 3 或更多。

我寧愿不撰寫自己的自定義排序，也不愿在每次排序之前對有問題的串列進行洗牌（我覺得這樣效率低下，但我相信它會起作用）。

那么，我怎樣才能制作一個隨機打破平局的比較器（這樣就不會有團隊不成比例地贏得平局的風險）而不會再次冒同樣的錯誤？

uj5u.com熱心網友回復：

我們需要使用一個額外的屬性來比較并列的球隊。這個屬性需要在 Comparator 的生命周期內保持不變，但從一個 Comparator 到下一個是隨機的。

每次需要排序時創建一個新的比較器，并確保它以可預測但隨機的方式運行：

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;
    }
}

所以每個 Comparator 都會有一個不同的 random seed，但每個隨機決定都是一樣的，因為我們會根據 Comparator和兩個團隊的 id創建Random帶有種子的新實體。seed

我們仍然基于團隊 id 的函式進行排序（因為我們需要在比較團隊之間建立對稱和??傳遞關系）。

使用相同種子創建的兩個Random實體將產生相同的亂數序列。因此，當我們將帶有 id 的團隊45與另一個團隊進行比較時，我們將Random使用種子創建一個實體seed * 45（其中seed在比較器的生命周期內是常量），因此我們第一次呼叫使用該種子創建nextLong()的任何實體時Random，我們將總是得到相同的數字。

這是做同樣事情的一種不那么棘手的方法。它假設它Team具有正確hashCode的equals實作，因此我們可以將它用作 a 中的鍵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;
    }
}

上面的解決方案很昂貴，因為它創建了一個團隊串列大小的 Map，并為每個團隊創建了一個亂數。除非你有成千上萬的團隊，否則這無關緊要，但我們可以通過懶惰地填充地圖來降低成本：

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;
    }
}

uj5u.com熱心網友回復：

這是隨機選擇平局球隊的另一種方法

使用地圖。

• 將打成平手的球隊存盤在地圖中，并以他們的分數為鍵。該地圖可以是樹狀地圖，因此可以對其進行排序。
• 然后遍歷地圖并從每個串列中隨機選擇一個團隊。

這是任何處理之前的團隊。輸出是得分和團隊名稱。

[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]

標籤：爪哇 排序 随机的 比较器

上一篇：谷歌作業表用復選框計數多個條件范圍

下一篇：如何將價格最高的陣列顯示到最低