目录
- Alias Method
- 举例验证：
- 采样过程（对照你的话）：
- 一句话精确定义：
Alias Method
Alias Method（别名采样法）是一种用于从离散概率分布中进行高效随机采样的算法，其核心优势在于采样时间复杂度为 O(1)，适用于需要高频采样的场景，如游戏掉落系统、推荐系统候选集筛选、蒙特卡洛模拟等。
// 当前实现
public static <T> T weightRandom(Map<T, Integer> map) {int total = 0;for (Map.Entry<T, Integer> entry : map.entrySet()) {total += entry.getValue();}if (total <= 0) {return null;}int key = 0;int random = nextInt(total);for (Map.Entry<T, Integer> entry : map.entrySet()) {key += entry.getValue();if (key > random) {return entry.getKey();}}return null;
}
优缺点对比
| 方法 | 预处理 | 查询 | 适用场景 |
|---|---|---|---|
| 当前实现 | O(1) | O(n) | 元素少、权重频繁变化 |
| Alias Method | O(n) | O(1) | 元素多、权重固定或少变 |
| 前缀和+二分 | O(n) | O(log n) | 中等规模、需要动态更新 |
总结：Alias Method 通过巧妙的数学变换，将加权随机问题转化为两次均匀随机，实现了真正的 O(1) 查询，非常适合游戏掉落、抽奖等高频调用场景！
核心就是把大概率的多出来的概率，补给低概率的，低概率的随机到时，再去随机一次，看实际是给低概率和高概率
举例验证：
原始：A(0.2), B(0.4), C(0.4)
n=3, q=[0.6, 1.2, 1.2]
构造后（你的直觉）：
- A 缺一点，B 多出来补给 A
- B 还多，再补给 C
Alias 表：
| 列 | 主项 | 概率(主项) | 别名 |
|---|---|---|---|
| 1 | A | 0.6 | B |
| 2 | B | 0.8 | C |
| 3 | C | 1.0 | (无) |
采样过程（对照你的话）：
- 均匀随机选一列（比如列 1 → 主项 A）
- 再去随机一次（随机数 r）
- 如果 r ≤ 0.6 → 返回 A
- 否则 → 返回 B
这正是你说的：低概率的（A这一列）随机到时→ 再去随机一次，看实际是给低概率(A)还是高概率(B)。
一句话精确定义：
Alias Method = 将 n 项概率分布摊成 n 个“一个主项 + 一个别名”的二分选择，使得总权重每列=1，然后通过 2 次随机选择（一次选列，一次选主项/别名）实现 O(1) 采样。