非均匀权重集绘图的java实现
我想讨论如何以最佳方式实施以下内容：
给定一组元素
它们都是不同的。调用这个输入集N，它的大小为n。这些元素都有权重。现在，您需要创建一个子集（R），其中r小于或等于n。
这个子集同样不能包含重复。需要从N中随机选择R的每个元素，如果一个元素具有更高的权重，则其被选择的几率需要更高。如果N中所有元素的总权重为W，则选择元素i的几率需要为w_i/W
最后一个细节是，权重很容易改变，但只会增加，而不会减少
我想要一个简洁的实现。我在Java中工作，但我希望找到一些有趣的与语言无关的属性或细节（甚至是伪代码）
现在，对于我自己的解决方案：我创建一个原始元素集的Array List。我确保权重是自然数，如果元素的权重是n，我将它们加n次。然后我洗牌arraylist（collections.shuffle），然后继续从洗牌列表中获取元素，并将它们添加到Java Set，直到集合的大小为r。如果一个元素的权重增加，它会被添加到原始数组列表中更多次。再次洗牌，创建一个新子集
我的实现需要大量内存，如果集变大，洗牌的速度也会变慢。还有更好的主意吗
# 1 楼答案
首先，让我们把它简化为只画一个元素，你可以计算
然后，您只需在
[0,sum)范围内绘制一个数字r，并对r进行二进制搜索。它落在的范围就是你画的数字。这是
O(n)时间解决方案显然，您可以对更多元素执行此操作，但必须从集合中删除已选择的元素，或者重复此操作，直到选择新项目。然而，对于较大的子集大小，这两种解决方案都会退化为二次复杂度：（
但是，我们是否可以改进它以做得更好？
是的。使用二进制搜索树而不是数组。二叉搜索树实际上是order statistics tree的一种变体，它不存储
#children(v)，而是存储每个子树中的权重之和。除此之外，这基本上与顺序统计树保持相同关于树解决方案的更多信息，可以找到类似问题的答案：Algorithm to shuffle an Array randomly based on different weights
构建树的复杂度是
O(nlogn)，每个查询+删除都是O(logn)，这会给你O(nlogn + klogn) = O(nlogn)所以，我们有两个选择：
如果
k在o(logn)（little o这里），则更喜欢在每个查询中使用O(n)时间重新创建数组。否则，您应该更喜欢（在时间复杂度方面）基于O(nlogn)树的解决方案。就空间而言，两种解决方案在所需的额外空间量上都是线性的
这甚至可以做得更好，只需一次传球。这被称为weighted reservoir sampling。它的主要缺点是由于指数部分（至少从我的经验来看）导致的较大权重的数值问题导致的不稳定性
此解决方案以线性时间运行，带有
O(1)额外空间（如果不包括大小为k的输出数组）