AliasMethod解决带权重随机选择问题

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二叉树样例

AliasMethod的做法

首先,我们将宝箱里宝物出现的概率抽象成下图:

AliasMethod (1)

简单来说这是一个概率占用空间的比例图,现在宝箱里有5件宝物,每件宝物的平均概率为20%,我可以明显的看到青龙偃月刀,丈八蛇矛,龙胆亮银枪是低于平均概率的,而卷云刀高于平均概率,因此将低于平均概率的宝物放入Small堆,将高于平均概率的宝物放入Large堆。

AliasMethod_s_l (1)

AliasMethod的核心思想就是将高于平均概率的宝物当做“别名”分配到低于平均概率宝物之上,做法大致步骤:

1、从Large堆里找到第一个元素,将其填充至Small堆第一个元素

2、若未填满,则从Large堆里找到下一个元素;若填满,则从Small堆找到下一个元素填充,这样循环下去

3、Large堆或者Small堆任何堆为空则退出循环

初始化分配后如图(概率后面是高度占比,区间(0,1]):

AliasMethod (3)

接下的来处理方式就比较简单了,我们随机取一个下标[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

5 Comments

 Add your comment
  1. 博主你好, 第二个平衡二叉树的方法我还get不到,举个例子, 从1-100 随机出60 ,然后怎么定位到 是该落到哪个 武器的节点上,是按什么顺序一直减直到小于0,该落到哪个武器?

    • 你指的是[好一些的做法]这一段吗?
      如果是话,落到哪个节点是二叉搜索树的中序遍历

      • 是那一段 假如从100里随机出60 ,理论上落到根节点青钢剑,虽然用了二叉搜索树,我理解的 复杂度似乎还是o(n) . 因为中序遍历的时候 有多少个节点 就得遍历多少次。

      • 你分析的没错,是我回答错误,误会了你的意思。

        二叉搜索树的查找时间复杂度O(log(N)),重新分析你的例子,随机出60,我们给每个节点分配权重(注意开闭区间!!!),青龙偃月刀[0,15),丈八蛇矛[15,30)…
        树节点取值青龙偃月刀15,丈八蛇矛30…这里处理流程是从根节点开始先比对区间,若不符合,则根据小于节点值去左子树,大于等于去右子树…
        所以随机出60,应该是落到了青釭剑。

        中序遍历可以从0-99顺序排列所有节点,最初以为你是要从60到0依次是哪些武器。

  2. 感谢 ,终于明白方法二的巧妙了。 假如构建好了 这些区间分布,如果数据量不大,感觉再消耗多点空间,复杂度直接可以变成O(1), 只要提前一次性做好一个映射,只要保存每个随机值到武器名字的 映射,一共需要100个映射,假如随机到了60 ,而50~65都映射到了60青钢剑,根据这映射就能直接0(1)定位到是青钢剑,就不需要从根节点左右O(log(N))对比了。

Leave a Comment

Your email address will not be published.

鄂公网安备42018502003990号