Java 權重隨機算法實戰：從輪盤賭到前綴和優化

問題背景

給定元素及其權重（如 {A:8, B:2, C:11, D:79}），需按權重概率隨機選取元素。權重越大，被選中機率越高。常見於廣告投放、負載均衡、遊戲掉寶等場景。

方案演進

方案一：展開數組（空間換時間）

按權重複製元素構建大數組：[A×8, B×2, C×11, D×79]，隨機索引直接取值。
缺點：權重和大時極其浪費記憶體（如權重和 10 億不可行）。

方案二：前綴和 + 二分查找（標準解法）

1. 構建前綴和陣列 prefix[i] = Σ weights[0..i]，總和 sum = prefix[n-1]。
2. 生成隨機數 r ∈ [1, sum]。
3. 二分查找首個 prefix[i] ≥ r，返回對應元素。

複雜度：預處理 O(n)，查詢 O(log n)，空間 O(n)。

方案三：輪盤賭單次遍歷（流式處理）

無需預構建陣列，單次遍歷累加權重，同時生成隨機閾值：

public int rouletteSelect(double[] weights) {
    double sum = Arrays.stream(weights).sum();
    double r = Math.random() * sum; // [0, sum)
    double acc = 0;
    for (int i = 0; i < weights.length; i++) {
        acc += weights[i];
        if (r < acc) return i;
    }
    return weights.length - 1; // 浮點誤差兜底
}

優點：O(n) 時間、O(1) 額外空間、適合權重動態變化場景。
注意：若頻繁調用且權重不變，方案二更高效。

完整可運行示例

public class WeightRandom {
    private final double[] prefixSum;
    private final double total;

    public WeightRandom(double[] weights) {
        prefixSum = new double[weights.length];
        double acc = 0;
        for (int i = 0; i < weights.length; i++) {
            acc += weights[i];
            prefixSum[i] = acc;
        }
        total = acc;
    }

    // 二分查找版
    public int nextIndex() {
        double r = Math.random() * total;
        int idx = Arrays.binarySearch(prefixSum, r);
        return idx >= 0 ? idx : -idx - 1;
    }

    // 萬次驗證分布
    public static void main(String[] args) {
        double[] w = {8, 2, 11, 79};
        WeightRandom wr = new WeightRandom(w);
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int i = 0; i < 2_000_000; i++) cnt.merge(wr.nextIndex(), 1, Integer::sum);
        cnt.forEach((k, v) -> System.out.printf("索引%d(權重%.0f): %d 次 (%.2f%%)%n", k, w[k], v, v/20000.0));
    }
}

輸出示例

索引0(權重8): 159221 次 (7.96%)
索引1(權重2): 39987 次 (2.00%)
索引2(權重11): 219876 次 (11.00%)
索引3(權重79): 1580916 次 (79.05%)

實測分布極其接近理論值，算法正確。

進階優化

• 別名法：O(1) 查詢，O(n) 構建，適合極高頻、靜態權重場景（如遊戲掉寶表）。
• 動態權重：段樹/二叉索引樹維護前綴和，支持單點更新 O(log n)。
• 線程安全：ThreadLocalRandom 替代 Math.random() 避免爭用。

總結

權重隨機核心是「概率空間映射」。工程中優先選「前綴和+二分」通用模板；記憶體敏感或權重動態改用「輪盤賭單遍歷」；極致性能考慮「別名法」。理解原理比背誦代碼更重要。