不使用随机采样（）？

Question

我最近被要求执行，将选择具有相同的概率各元素的sampleStream（）方法，而不是使用随机的（）。我认为面试官正在寻找油藏采样，但当我偶然发现它时，他补充说这是一种叫做“stratified sampling”的方法。无可否认，我可能已经被抛弃了，因为有一种称为分层抽样的统计方法，我试图想到如何使用它来从流中对元素进行抽样而没有随机抽样。他指定的输入是要抽样的项目数量和我应该抽样的比率（类似1000/100,000）。

无论如何，我仍然停留在这个问题上，即使我已经不得到未正确回答它的工作。谷歌搜索在这里失败了。任何人都可以帮助我理解它吗？实行分层抽样

Answer 1

一种方法是排序用于分层密钥列表，然后在正取样做1。

技术上，分类是不必要的，如果键是类别。在这种（典型的）情况下，可以使用哈希方法。这个想法仍然是一样的：在一个“有序”列表中进行n次采样。

或许，这就是面试官指的。

编辑：

您可以实现流上的分层抽样，你就基本上可以读取该流并做了“桶”计算每组相似的键值。当存储桶有一些任意值时，您将输出记录。当桶达到某个值（基于整体频率）时，您将重置计数器并重复（或使用模运算）。

但是，这并没有获得每条记录的相同概率。为此，我确实认为你需要某种随机化。接近的方法是将每个组的记录存储在一个存储桶中，然后在存储桶已满时选择一个随机记录。您可以通过在其他值（例如插入时间）上使用散列键来模拟随机性，然后选择最小或最大散列键值。 （而且，你可以让这个更有效的通过只是存储一个记录。）