AliasMethod是一个初始化复杂度为O(n)，占用内存O(n)，运行时复杂度为O(1)的算法。
核心文献：http://www.keithschwarz.com/darts-dice-coins/
本文部分文字来自上文翻译。
AliasMethod使用场景
这里用游戏服务来举例，当我们打开一个宝箱会随机获得一件宝物，宝物可能出现的概率如下：
青龙偃月刀 15%
丈八蛇矛 15%
龙胆亮银枪 15%
青釭剑 20%
卷云刀 35%
一般做法：我们将其概率相加等于100，意思是将其看成有100份分片，第0-14片表示青龙偃月刀，第15-29片表示丈八蛇矛……，然后利用rand()%100获得第几片，代表获得了第几件宝物，显然这种做法的运行时获取结果的时间复杂度为O(n)。
好一些的做法：我们将每样宝物的概率利用平衡二叉树构建初始化，如下图所示，利用二叉树的特性找到rand()%100结果对于所处树的节点，运行时获取结果的时间复杂度为O(log(N))。
AliasMethod的做法
首先，我们将宝箱里宝物出现的概率抽象成下图：
简单来说这是一个概率占用空间的比例图，现在宝箱里有5件宝物，每件宝物的平均概率为20%，我可以明显的看到青龙偃月刀，丈八蛇矛，龙胆亮银枪是低于平均概率的，而卷云刀高于平均概率，因此将低于平均概率的宝物放入Small堆，将高于平均概率的宝物放入Large堆。
AliasMethod的核心思想就是将高于平均概率的宝物当做“别名”分配到低于平均概率宝物之上，做法大致步骤：
1、从Large堆里找到第一个元素，将其填充至Small堆第一个元素
2、若未填满，则从Large堆里找到下一个元素；若填满，则从Small堆找到下一个元素填充，这样循环下去
3、Large堆或者Small堆任何堆为空则退出循环
初始化分配后如图（概率后面是高度占比，区间(0,1]）：
接下的来处理方式就比较简单了，我们随机取一个下标[0,4]，比如下标2，对应的是宝物龙胆亮银枪（占比0.75），被分配的宝物为卷云刀（占比0.25），那么我们再从[0,1]随机一个浮点数，看落在龙胆亮银枪占比区间，还是落在卷云刀占比区间，落入对应区间获得相应宝物。
AliasMethod的误差（主要基于核心文献翻译）
当我们在理想情况下，通过概率计算出的权重是可以均分的。但是在复杂的情况下，特别是1/n会有小数余数的时候（例如 1/3=0.333333…..），使用double计算时就会存在精度问题。直接导致的结果使Small堆还存在元素，但是Large堆已分配空的情况（反之亦然）。
这里原文的解决方法是，无论是Small堆还是Large堆，在循环分配后，若还存在未分配的元素，那么我们强行将其占比置1。
这里笔者提一句，原文没有给出严格的数学证明上述做法是否会导致结果失真，但是从实际测试用例来看，误差在合理的范围之内。
使用C++实现的代码 – 请点这里
（全文结束）
转载文章请注明出处：漫漫路 - lanindex.com