问题标签 [reservoir-sampling]

我尝试在http://jeremykun.com/2013/07/05/reservoir-sampling/之后在 haskell 中实现一个简单的水库采样（请注意，显示的算法可能在语义上不正确）

据此：迭代或惰性水库采样惰性水库采样是不可能的，除非您提前知道人口规模。

即便如此，我还是不明白为什么（从操作上讲）下面的sampleReservoir内容不适用于无限列表。懒惰到底在哪里被打破了？

挑战和考验是fmap (take 1) $ sampleReservoir [1..]。

此外，如果水库采样不能惰性，那么什么可以接收惰性列表并生成采样惰性列表？

我认为必须有一种方法可以使上述函数在输出中变得惰性，因为我可以更改它：

至：

这显示了函数在列表上迭代时的结果。使用协程抽象，也许可以代替print ea yield e，其余的计算可以作为延续。

我无法理解储层采样所涉及的概率。下面是我在几乎所有地方都看到过的示例代码：

我的理解正确吗（？）：假设我们有 k=3 并且 input = [100, 200, 300, 400, 500] 并且 i 目前处于 500 索引。500 替换 300 在水库中的概率（大小为 3）= 在水库中选择 300 的概率 * 选择 500 的概率只有当随机函数返回的索引小于或等于 3 时才有可能5 个选择 = 1/3 * 3/5 = 1/5

我的问题与此链接的“算法 R”部分中的示例代码有关https://en.m.wikipedia.org/wiki/Reservoir_sampling

我从该部分复制了以下代码片段。为什么这段代码用逐渐降低的概率替换元素？根据问题，输入中的每个项目都应该具有相同的概率，对吧？

例如，将以下三个输入的随机函数调用与我的水库大小 10 进行比较

• 随机 (1,15) 获得低于 10 的随机数的机会很高
• random (1, 100) 获得低于 10 的随机数的机会非常低
• random (1, 1000) 获得低于 10 的随机数的机会非常低

因此，随着输入的增长，替换项目的机会非常少，那么我们怎么能说水库采样算法是在每个项目上以相等概率选择随机样本的解决方案呢？也许我错过了一些东西，请解释一下。

我有一个大小为 n 的输入流，我想生成一个大小为 k 的输出流，其中包含输入流的不同随机元素，而不需要为样本选择的元素提供任何额外的内存。

我要使用的算法基本上如下：

函数 random() 在随机分布上从 [0..1) 生成一个数字，我相信该算法的操作原理很简单。

尽管该算法在选择最后一个元素时可以提前终止，但通常该算法仍约为 O(n)。起初它似乎按预期工作（从输入流中输出大致均匀分布但仍然是随机的元素），但我认为当 k 远小于 n 时，可能会有一种不均匀的倾向来选择后面的元素。但是，我不确定这一点......所以我很高兴知道一种或另一种方式。我也想知道是否存在更快的算法。显然，由于必须生成 k 个元素，因此算法不能比 O(k) 快。对于 O(k) 解决方案，可以假设存在一个函数 skip(x)，它可以在 O(1) 时间内跳过输入流中的 x 个元素（但不能向后跳过）。

我正在尝试实现 A-Chao 版本的加权水库采样，如https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Chao所示

但是我发现wiki中描述的伪代码似乎是错误的，尤其是在初始化部分。我读了这篇论文，它提到我们需要处理权重过大的数据点，但我仍然不知道如何正确初始化。

据我了解，在初始化步骤中，我们要确保选择的所有初始数据点都应该具有相同的概率*权重。但是，我不明白超重点与此有何关系。

我根据wiki实现的代码，但结果显示它是不正确的。