Java 高效隨機數生成：Alias Method 算法完整實作

Alias Method 算法簡介

Alias Method（別名法）是一種以 O(1) 時間複雜度 從離散機率分佈中取樣的算法。透過預處理建立「機率表」與「別名表」，每次取樣僅需一次均勻隨機數與一次偏向隨機判斷，極適合高頻率、大規模隨機抽獎、加權隨機場景。

核心資料結構

• probability[]：各列調整後的機率值（0.0 ~ 1.0）。
• alias[]：各列的別名索引。

完整實作代碼

public final class LotteryAliasMethod {
    private final Random random;
    private final int[] alias;
    private final double[] probability;

    /** 建構子：輸入機率分佈列表，自動建表 */
    public LotteryAliasMethod(List probabilities) {
        this(probabilities, new Random());
    }

    public LotteryAliasMethod(List probabilities, Random random) {
        if (probabilities == null || random == null) throw new NullPointerException();
        if (probabilities.isEmpty()) throw new IllegalArgumentException("機率向量不可為空");

        int n = probabilities.size();
        this.probability = new double[n];
        this.alias = new int[n];
        this.random = random;

        double average = 1.0 / n;
        List probs = new ArrayList<>(probabilities);
        Deque small = new ArrayDeque<>();
        Deque large = new ArrayDeque<>();

        // 分類：小於平均值進 small，大於等於進 large
        for (int i = 0; i < n; i++) {
            if (probs.get(i) >= average) large.add(i);
            else small.add(i);
        }

        // 配對 small 與 large
        while (!small.isEmpty() && !large.isEmpty()) {
            int less = small.removeLast();
            int more = large.removeLast();

            probability[less] = probs.get(less) * n;
            alias[less] = more;

            // 調整 more 的機率
            probs.set(more, (probs.get(more) + probs.get(less)) - average);

            if (probs.get(more) >= 1.0 / n) large.add(more);
            else small.add(more);
        }

        // 剩餘項目機率設為 1.0
        while (!small.isEmpty()) probability[small.removeLast()] = 1.0;
        while (!large.isEmpty()) probability[large.removeLast()] = 1.0;
    }

    /** O(1) 取樣 */
    public int next() {
        int column = random.nextInt(probability.length);
        boolean coinToss = random.nextDouble() < probability[column];
        return coinToss ? column : alias[column];
    }
}

使用範例

List weights = Arrays.asList(0.1, 0.2, 0.3, 0.4); // 權重總和需為 1.0
LotteryAliasMethod sampler = new LotteryAliasMethod(weights);
for (int i = 0; i < 10; i++) {
    System.out.println("抽中索引：" + sampler.next());
}

算法優勢

• 預處理 O(n)，取樣 O(1)，大幅優於累積機率二分搜尋的 O(log n)。
• 記憶體佔用固定，僅兩個長度 n 的陣列。
• 支援任意離散分佈，適合抽獎、負載均衡、蒙地卡羅模擬等場景。