加權隨機選取演算法：遊戲武將掉落機率的 Java 實作

問題背景

遊戲系統中，武將登場機率不同（如 A:30%、B:40%、C:30%），且武將數量動態變化。需高效實作「按權重隨機選取」。

核心思路：前綴和區間映射

1. 計算權重總和 total = 100。
2. 產生隨機數 rand ∈ [1, total]。
3. 將權重轉為前綴和陣列：[30, 70, 100]。
4. 找到首個 prefix[i] >= rand 的索引 i，即為命中項目。

程式碼實作（線性掃描版）

public int selectByWeight(List<General> generals) {
    int total = generals.stream().mapToInt(General::getWeight).sum();
    int rand = ThreadLocalRandom.current().nextInt(total) + 1; // 1-based
    int sum = 0;
    for (int i = 0; i < generals.size(); i++) {
        sum += generals.get(i).getWeight();
        if (rand <= sum) return i;
    }
    return generals.size() - 1; // 兜底
}

效能優化：二分查找（O(log n)）

當武將數量大（>100）或頻繁調用時，預先建立前綴和陣列，改用 Arrays.binarySearch 或手寫二分：

// 建構時預計算
int[] prefix = new int[generals.size()];
int sum = 0;
for (int i = 0; i < generals.size(); i++) {
    sum += generals.get(i).getWeight();
    prefix[i] = sum;
}

// 查詢
int idx = Arrays.binarySearch(prefix, rand);
if (idx < 0) idx = -idx - 1; // 插入點即為命中索引
return idx;

進階考量

• 權重動態更新：若權重頻繁變動，需重建前綴和；可考慮 Fenwick Tree (Binary Indexed Tree) 實現 O(log n) 更新與查詢。
• 機率精度：權重總和較大時，nextInt(total) 足夠；極大總和可用 nextLong()。
• 測試驗證：跑百萬次統計頻率，驗證是否符合預期分布（卡方檢定）。

總結

「前綴和 + 隨機數落區間」是經典加權隨機演算法。小規模用線性掃描簡潔明瞭；大規模或高頻場景請升級二分查找或 Fenwick Tree。記得用 ThreadLocalRandom 保證執行緒安全與效能。