algorithm - 给定迭代器获取 N 个样本

Question

给定一个迭代器 it在数据点上，我们拥有的数据点数量n ，以及我们要用于进行某些计算的最大样本数 (maxSamples)。

想象一个函数 calculateStatistics(Iterator it, int n, int maxSamples) .此函数应使用迭代器检索数据并对检索到的数据元素进行一些(大量)计算。

• 如果n <= maxSamples我们当然会使用从迭代器中获得的每个元素
• 如果n > maxSamples我们将不得不选择要查看和跳过的元素

我已经花了很多时间在这上面。问题当然是如何选择什么时候跳过一个元素，什么时候保留它。到目前为止我的方法:

• 我不想拿第一个 maxSamples来自迭代器，因为值可能分布不均。
• 另一个想法是使用随机数生成器并让我创建 maxSamples 0 之间的(不同的)随机数和 n并在这些位置获取元素。但是如果例如n = 101和 maxSamples = 100找到一个不在列表中的新的不同数字变得越来越困难，仅仅在随机数生成中就浪费了很多时间
• 我最后的想法是反其道而行之:生成 n - maxSamples随机数并排除这些位置元素的数据元素。但这似乎也不是一个很好的解决方案。

你对这个问题有什么好主意吗？可能有标准的已知算法吗？

Answer 1

为了提供一些答案，在给定集合大小 > 所需元素的情况下收集一组随机数的好方法如下。 (在 C++ ish 伪代码中)。

编辑:您可能需要先迭代并创建“someElements”向量。如果您的元素很大，它们可以作为这些元素的“指针”以节省空间。

vector randomCollectionFromVector(someElements, numElementsToGrab) {
    while(numElementsToGrab--) {
         randPosition = rand() % someElements.size();
         resultVector.push(someElements.get(randPosition))
         someElements.remove(randPosition);
    }
    return resultVector;
}

如果您不关心更改元素向量，您也可以从 someElements 中删除随机元素，如您所提到的。该算法看起来非常相似，而且，这在概念上是相同的想法，您只需通过引用传递 someElements 并对其进行操作。

值得注意的是，伪随机分布的质量(就其随机性而言)会随着您使用的分布大小的增加而增加。因此，如果您根据哪种方法导致使用更多随机数来选择使用哪种方法，您可能会获得更好的结果。示例:如果您有 100 个值，并且需要 99 个，您可能应该选择 99 个值，因为这将导致您使用 99 个伪随机数，而不仅仅是 1 个。相反，如果您有 1000 个值，并且需要 99 个，您应该可能更喜欢删除 901 值的版本，因为您使用伪随机分布中的更多数字。如果您想要的是可靠的随机分布，这是一个非常简单的优化，将大大提高您看到的“假随机性”的质量。或者，如果性能比分布更重要，您可以采用替代方法，甚至只获取前 99 个值的方法。