每日算法 — 使用java实现Alias Method：O(1)带权随机采样与离散概率分布

算法概述

Alias Method（别名方法）是离散概率分布采样的经典算法，由Walker于1977年提出。对于包含 (n) 个事件、对应概率为 (p_1, p_2, …, p_n) 的离散分布，Alias Method通过预处理构造两个辅助表——概率表（Prob）和别名表（Alias），使得每次采样仅需一次均匀随机数生成和一次数组查找，达到 (O(1)) 的时间复杂度。

相比朴素方法的 (O(n)) 线性扫描或二分搜索的 (O(\log n))，Alias Method在需要大量重复采样的场景（如游戏掉落系统、蒙特卡洛模拟、负载均衡）中具有显著优势。

核心原理

Alias Method的核心思想是将任意离散概率分布转化为 (n) 个等概率的二元选择。

具体构造过程：
1. 将每个事件的概率 (p_i) 乘以 (n)，得到期望值 (E_i = n \cdot p_i)
2. 对于 (E_i \geq 1) 的项（富项），将多余概率转移给 (E_j < 1) 的项（贫项）
3. 最终每个位置 (i) 存储：以概率 (Prob[i]) 选择事件 (i)，否则选择 (Alias[i])

每个位置的期望概率恰好为1，且所有事件的总概率被精确保留。

Java实现

项目结构

alias-method/
├── AliasTable.java       // Alias Method核心实现
├── WeightedRandom.java   // 带权随机采样器
├── GameDropSystem.java   // 游戏掉落系统应用示例
└── Main.java             // 测试入口

核心实现：AliasTable.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Random;

/**
 * Alias Method 离散概率采样器
 * 预处理 O(n)，单次采样 O(1)
 */
public class AliasTable {

    private final int n;
    private final double[] prob;   // 概率表
    private final int[] alias;     // 别名表
    private final Random random;

    /**
     * 构造Alias表
     * @param weights 各事件的权重（无需归一化）
     */
    public AliasTable(double[] weights) {
        if (weights == null || weights.length == 0) {
            throw new IllegalArgumentException("权重数组不能为空");
        }

        this.n = weights.length;
        this.prob = new double[n];
        this.alias = new int[n];
        this.random = new Random();

        build(weights);
    }

    /**
     * 使用指定随机种子构造
     */
    public AliasTable(double[] weights, long seed) {
        if (weights == null || weights.length == 0) {
            throw new IllegalArgumentException("权重数组不能为空");
        }

        this.n = weights.length;
        this.prob = new double[n];
        this.alias = new int[n];
        this.random = new Random(seed);

        build(weights);
    }

    /**
     * 构建Alias表的核心算法
     * 使用双端队列分别存储富项和贫项
     */
    private void build(double[] weights) {
        // 计算总权重
        double sum = 0;
        for (double w : weights) {
            if (w < 0) throw new IllegalArgumentException("权重不能为负");
            sum += w;
        }

        if (sum == 0) {
            throw new IllegalArgumentException("总权重不能为零");
        }

        // 标准化概率并乘以 n
        double[] scaled = new double[n];
        for (int i = 0; i < n; i++) {
            scaled[i] = (weights[i] / sum) * n;
        }

        // 初始化队列
        Deque<Integer> small = new ArrayDeque<>(); // 贫项: scaled[i] < 1
        Deque<Integer> large = new ArrayDeque<>(); // 富项: scaled[i] >= 1

        for (int i = 0; i < n; i++) {
            if (scaled[i] < 1.0) {
                small.addLast(i);
            } else {
                large.addLast(i);
            }
        }

        // 贪心配对：将富项的多余概率分配给贫项
        while (!small.isEmpty() && !large.isEmpty()) {
            int l = small.removeFirst();  // 贫项
            int g = large.removeFirst();  // 富项

            prob[l] = scaled[l];
            alias[l] = g;

            // 富项减去分配给贫项的部分
            scaled[g] = scaled[g] + scaled[l] - 1.0;

            if (scaled[g] < 1.0) {
                small.addLast(g);
            } else {
                large.addLast(g);
            }
        }

        // 处理剩余项（数值精度导致的余项）
        while (!large.isEmpty()) {
            int g = large.removeFirst();
            prob[g] = 1.0;
        }

        while (!small.isEmpty()) {
            int l = small.removeFirst();
            prob[l] = 1.0;
        }
    }

    /**
     * O(1) 采样一个事件索引
     * @return 事件索引 [0, n-1]
     */
    public int sample() {
        // 等概率选择一个列
        int column = random.nextInt(n);
        // 以 prob[column] 的概率返回当前列，否则返回别名
        double coin = random.nextDouble();
        return coin < prob[column] ? column : alias[column];
    }

    /**
     * 批量采样
     */
    public int[] sampleBatch(int count) {
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            result[i] = sample();
        }
        return result;
    }

    /**
     * 获取某个索引被采样的理论概率
     */
    public double getProbability(int index) {
        if (index < 0 || index >= n) return 0;

        double p = 0;
        for (int i = 0; i < n; i++) {
            if (i == index) {
                p += prob[i] / n;
            } else if (alias[i] == index) {
                p += (1.0 - prob[i]) / n;
            }
        }
        return p;
    }

    /**
     * 打印Alias表结构（调试用）
     */
    public void printTable() {
        System.out.println("Alias Table:");
        System.out.println("Index\tProb\tAlias");
        for (int i = 0; i < n; i++) {
            System.out.printf("%d\t%.4f\t%d%n", i, prob[i], alias[i]);
        }
    }
}

游戏掉落系统应用：GameDropSystem.java

/**
 * 游戏装备掉落系统 - Alias Method应用示例
 * 模拟RPG游戏中怪物掉落不同品质装备的概率分配
 */
public class GameDropSystem {

    public enum ItemRarity {
        COMMON("普通"), UNCOMMON("精良"), RARE("稀有"), 
        EPIC("史诗"), LEGENDARY("传说");

        private final String name;
        ItemRarity(String name) { this.name = name; }
        public String getName() { return name; }
    }

    private final AliasTable dropTable;
    private final ItemRarity[] rarities = ItemRarity.values();

    /**
     * 创建掉落系统
     * @param dropRates 各品质掉落权重 [普通, 精良, 稀有, 史诗, 传说]
     */
    public GameDropSystem(double[] dropRates) {
        if (dropRates.length != rarities.length) {
            throw new IllegalArgumentException("权重数量与品质数量不匹配");
        }
        this.dropTable = new AliasTable(dropRates);
    }

    /**
     * 模拟一次击杀掉落
     */
    public ItemRarity rollDrop() {
        int index = dropTable.sample();
        return rarities[index];
    }

    /**
     * 模拟批量击杀并统计
     */
    public void simulate(int kills) {
        int[] counts = new int[rarities.length];

        for (int i = 0; i < kills; i++) {
            ItemRarity drop = rollDrop();
            counts[drop.ordinal()]++;
        }

        System.out.printf("模拟击杀 %d 次掉落统计:%n", kills);
        for (int i = 0; i < rarities.length; i++) {
            double rate = (double) counts[i] / kills * 100;
            System.out.printf("  %s: %d 次 (%.2f%%)%n", 
                rarities[i].getName(), counts[i], rate);
        }
    }

    public static void main(String[] args) {
        // 设定掉落权重：普通50%, 精良30%, 稀有15%, 史诗4%, 传说1%
        double[] weights = {50, 30, 15, 4, 1};

        GameDropSystem system = new GameDropSystem(weights);

        System.out.println("=== 掉落概率表 ===");
        system.dropTable.printTable();
        System.out.println();

        // 模拟10万次击杀
        system.simulate(100000);
    }
}

测试入口：Main.java

public class Main {
    public static void main(String[] args) {
        System.out.println("=== Alias Method 带权随机采样测试 ===\n");

        // 测试1：基础采样
        System.out.println("--- 测试1：基础离散分布 ---");
        double[] weights = {1, 2, 3, 4}; // 对应概率: 0.1, 0.2, 0.3, 0.4
        AliasTable table = new AliasTable(weights);
        table.printTable();

        int n = 100000;
        int[] counts = new int[4];
        for (int i = 0; i < n; i++) {
            counts[table.sample()]++;
        }

        System.out.println("\n采样结果（10万次）：");
        for (int i = 0; i < 4; i++) {
            System.out.printf("  事件%d: %d 次 (%.2f%%)%n", 
                i, counts[i], counts[i] * 100.0 / n);
        }

        // 测试2：性能对比
        System.out.println("\n--- 测试2：性能对比 ---");
        int samples = 10_000_000;

        // Alias Method
        long start = System.nanoTime();
        for (int i = 0; i < samples; i++) {
            table.sample();
        }
        long aliasTime = System.nanoTime() - start;

        // 朴素线性扫描
        double[] probs = {0.1, 0.2, 0.3, 0.4};
        java.util.Random rand = new java.util.Random();
        start = System.nanoTime();
        for (int i = 0; i < samples; i++) {
            naiveSample(probs, rand);
        }
        long naiveTime = System.nanoTime() - start;

        System.out.printf("Alias Method:  %.3f ms%n", aliasTime / 1e6);
        System.out.printf("朴素线性扫描: %.3f ms%n", naiveTime / 1e6);
        System.out.printf("加速比: %.1fx%n", (double) naiveTime / aliasTime);

        // 测试3：游戏掉落
        System.out.println("\n--- 测试3：游戏掉落模拟 ---");
        GameDropSystem.main(args);
    }

    private static int naiveSample(double[] probs, java.util.Random rand) {
        double u = rand.nextDouble();
        double cumsum = 0;
        for (int i = 0; i < probs.length; i++) {
            cumsum += probs[i];
            if (u < cumsum) return i;
        }
        return probs.length - 1;
    }
}

复杂度分析

操作	时间复杂度	空间复杂度
构造Alias表	(O(n))	(O(n))
单次采样	(O(1))	(O(1))
批量采样 (k) 次	(O(k))	(O(1))

构造过程中，每个事件最多被处理两次（一次作为贫项接收概率，一次作为富项分配概率），因此总体为线性时间。

算法正确性验证

Alias Method保证每个事件 (i) 被采样的精确概率等于其原始概率 (p_i)。证明如下：

事件 (i) 被采样的情况有两种：
1. 选中列 (i) 且硬币投掷成功：概率 (\frac{1}{n} \cdot Prob[i])
2. 选中其他列 (j)（其中 (Alias[j] = i)）且硬币投掷失败：(\sum_{j: Alias[j]=i} \frac{1}{n} \cdot (1 – Prob[j]))

由构造过程可知，对于每个列 (j)，分配给别名的概率恰好使其期望为1，且每个事件 (i) 的总概率在所有列中的贡献之和精确等于 (n \cdot p_i / n = p_i)。

适用场景

游戏开发：装备掉落、抽奖系统、随机事件触发
负载均衡：按权重分配请求到不同服务器
蒙特卡洛模拟：需要从复杂离散分布重复采样
自然语言处理：语言模型中的词采样、分类采样
推荐系统：按用户兴趣权重推荐内容

与朴素方法的对比

方法	预处理	单次采样	适用场景
线性扫描	无	(O(n))	事件数极少或一次性采样
二分搜索	(O(n))	(O(\log n))	中等事件数，概率更新频繁
Alias Method	(O(n))	(O(1))	大量重复采样，事件数固定

扩展方向

动态Alias Method：支持在线更新权重（如树状数组+Alias混合）
多维Alias Method：将方法扩展到联合离散分布
拒绝采样+Alias：在连续分布离散化后使用Alias Method加速

总结

Alias Method是离散概率采样的”黄金标准”之一。通过Java实现，我们理解了其核心构造思想：将任意概率分布转化为等概率的二元选择表。在游戏开发、蒙特卡洛模拟等需要高频采样的场景中，Alias Method以 (O(1)) 的查询效率提供了极高的性能保障。掌握这一算法，是构建高效随机系统的关键一步。

Tagged with: Alias Method 带权随机概率分布采样算法