不使用 random() 进行采样？
Sampling without using random()?
我最近被要求实现一个 sampleStream() 方法，该方法将以相等的概率选择每个元素，但不使用 random()。我以为面试官是在寻找水库采样，但当我偶然发现时，他补充说这是一种称为“stratified sampling”的方法。诚然，我可能对此感到困惑，因为有一种称为分层抽样的统计方法，我正在尝试思考如何使用它来不随机地从流中抽取元素。他指定的输入是要抽样的项目数量，以及我应该抽样的比率（大约 1000/100,000）。
无论如何，我仍然被这个问题困住了，尽管我已经因为没有正确回答而没有得到这份工作。谷歌搜索在这里失败了。谁能帮我理解一下？
实现分层抽样的一种方法是按用于分层的键对列表进行排序，然后进行 1 in n 抽样。
从技术上讲，如果键是类别，则不需要排序。在这种（典型）情况下，可以使用哈希方法。这个想法仍然是一样的：在 "ordered" 列表上进行 n 中的 1 采样。
面试官说的应该是这个吧
编辑：
您可以对流实施分层抽样，您实际上是在读取流并对每组相似的键值进行 "bucket" 计数。当桶有一些任意值时，您将输出记录。当桶达到某个值（基于总频率）时，您将重置计数器并重复（或使用模运算）。
但是，这并不是获得每条记录的概率均等。为此，我真的认为你需要某种随机化。一种接近的方法是将每个组的记录存储在一个桶中，然后在桶满时选择一个随机记录。您可以通过对某个其他值（例如插入时间）使用散列键，然后选择最小或最大散列键值来模拟随机性。 （而且，您可以通过仅存储一条记录来提高效率。）
我最近被要求实现一个 sampleStream() 方法，该方法将以相等的概率选择每个元素，但不使用 random()。我以为面试官是在寻找水库采样，但当我偶然发现时，他补充说这是一种称为“stratified sampling”的方法。诚然，我可能对此感到困惑，因为有一种称为分层抽样的统计方法，我正在尝试思考如何使用它来不随机地从流中抽取元素。他指定的输入是要抽样的项目数量，以及我应该抽样的比率（大约 1000/100,000）。
无论如何，我仍然被这个问题困住了，尽管我已经因为没有正确回答而没有得到这份工作。谷歌搜索在这里失败了。谁能帮我理解一下？
实现分层抽样的一种方法是按用于分层的键对列表进行排序，然后进行 1 in n 抽样。
从技术上讲，如果键是类别，则不需要排序。在这种（典型）情况下，可以使用哈希方法。这个想法仍然是一样的：在 "ordered" 列表上进行 n 中的 1 采样。
面试官说的应该是这个吧
编辑：
您可以对流实施分层抽样，您实际上是在读取流并对每组相似的键值进行 "bucket" 计数。当桶有一些任意值时，您将输出记录。当桶达到某个值（基于总频率）时，您将重置计数器并重复（或使用模运算）。
但是，这并不是获得每条记录的概率均等。为此，我真的认为你需要某种随机化。一种接近的方法是将每个组的记录存储在一个桶中，然后在桶满时选择一个随机记录。您可以通过对某个其他值（例如插入时间）使用散列键，然后选择最小或最大散列键值来模拟随机性。 （而且，您可以通过仅存储一条记录来提高效率。）