提问人：Cheiron 提问时间：3/31/2017 最后编辑：Cheiron 更新时间：3/31/2017 访问量：80
从具有非均匀权重的集合中绘图的实现
Implementation of drawing from a set with non-uniform weights
问：
我想讨论一下如何以最佳方式实现以下内容：
给定一组元素，
它们都是不同的。调用这个输入集，它的大小。这些元素每个都有一个权重。现在，您需要创建一个 size 的子集 （），其中小于或等于 。
同样，此子集不能包含重复。每个元素都需要从中随机选择，如果一个元素的权重较高，那么它被选择的几率就需要更高。如果 中所有元素的总权重为 ，则选择该元素的几率需要为 。NnRNrrnRNNWiw_i/W
最后一个细节是权重容易变化，但只会增加，不能减少。
我想要一个简洁的实现。我正在使用 Java，但我希望找到一些有趣的与语言无关的属性或细节（甚至是伪代码）。
现在，对于我自己的解决方案：我创建了一组原始元素。我确保权重是自然数，如果元素的权重为 .然后我打乱了数组列表（），并继续从打牌列表中获取元素并将它们添加到 Java 中，直到集合的大小为 .如果元素的权重增加，则会将其添加到原始数组列表中的次数。再次随机播放，创建一个新的子集。Array Listnncollections.shuffleSetr
我的实现需要大量的内存，如果集合变大，洗牌也会变慢。有没有更好的主意？
答：
1赞
amit
3/31/2017
#1
首先，让我们将其简化为仅绘制一个元素，即计算
sum[-1] = 0
sum[i] = sum[i-1] + weight[i]
然后，您只需在范围内绘制一个数字，然后对 进行二进制搜索。它所属的范围，就是你抽到的数字。
这是时间解决方案。r[0,sum)rO(n)
你显然可以对更多元素这样做，但你必须从集合中删除你选择的元素，或者重复，直到你选择一个新项目。然而，对于较大的子集大小，这两种解决方案都会衰减到二次复杂度:(
但是，我们能改进它以做得更好吗？
是的。使用二叉搜索树而不是数组。二叉搜索树实际上是顺序统计树的变体，其中不是存储 ，而是在每个子树中存储权重的总和。除此之外 - 这基本上与订单统计树相同。#children(v)
有关树解决方案的更多信息可以作为类似问题的答案找到：基于不同权重随机随机洗牌数组的算法
构建树的复杂度为 ，每个查询 + 删除为 ，这为您提供了O(nlogn)O(logn)O(nlogn + klogn) = O(nlogn)
因此，我们有两种选择：
如果在（这里是小 o），则更喜欢重新创建数组，其中包含每个查询的时间。否则，您应该更喜欢（就时间复杂度而言）基于树的解决方案。
在空间方面，两种解决方案在所需的额外空间量上都是线性的。ko(logn)O(n)O(nlogn)
这甚至可以做得更好，只需一次通过。这称为加权储层取样。它的主要缺点是由于指数部分（至少根据我的经验）导致的大权重的数值问题而导致的不稳定性。
此解决方案以线性时间运行，具有额外的空间（如果不包括 size 的输出数组）。O(1)k
下一个：检查日期范围是否触及时间范围
评论