0

给定的是数据点的迭代器it，我们拥有的数据点的数量n，以及我们想要用来做一些计算的最大样本数 ( maxSamples)。

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

  • 如果n <= maxSamples我们当然会使用从迭代器中获得的每个元素
  • 如果n > maxSamples我们必须选择查看哪些元素以及跳过哪些元素

我已经在这方面花费了相当长的时间。问题当然是如何选择何时跳过元素以及何时保留它。到目前为止我的方法：

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

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

4

4 回答 4

1 
interval = n/(n-maxSamples) //an euclidian division of course
offset = random(0..(n-1)) //a random number between 0 and n-1
totalSkip = 0
indexSample = 0;
FOR it IN samples DO
    indexSample++ // goes from 1 to n
    IF totalSkip < (n-maxSamples) AND indexSample+offset % interval == 0 THEN
        //do nothing with this sample
        totalSkip++
    ELSE
        //work with this sample
    ENDIF
ENDFOR
ASSERT(totalSkip == n-maxSamples) //to be sure

interval表示要跳过的两个样本之间的距离。 offset不是强制性的，但它允许有很少的多样性。

于 2013-05-15T15:15:02.423 回答
1

根据讨论和对您问题的更深入了解，我提出以下建议。您可以利用质数的属性，我认为这将为您提供一个非常好的解决方案，它似乎会抓取伪随机数。它在以下代码中进行了说明。

#include <iostream>
using namespace std;


int main() {
    const int SOME_LARGE_PRIME = 577;  //This prime should be larger than the size of your data set.  
    const int NUM_ELEMENTS = 100;
    int lastValue = 0;
    for(int i = 0; i < NUM_ELEMENTS; i++) {
        lastValue += SOME_LARGE_PRIME;
        cout << lastValue % NUM_ELEMENTS << endl;
    }
}

使用此处介绍的逻辑，您可以创建一个包含从 1 到“NUM_ELEMENTS”的所有值的表。由于素数的属性，在您一直旋转回到数据集的大小之前，您不会得到任何重复。如果你然后取其中的第一个“NUM_SAMPLES”，并对它们进行排序，你可以遍历你的数据结构，并获取数字的伪随机分布（不是很好的随机，但比预先确定的间隔更随机），没有额外的空间，只有一次通过您的数据。更好的是，您可以通过每次抓取一个随机素数来更改分布的布局，再次必须大于您的数据集，否则下面的示例会中断。

PRIME = 3，数据集大小 = 99。不起作用。

当然，最终这与预先确定的间隔非常相似，但它插入了一定程度的随机性，而这是通过简单地抓取每个“size/num_samples”个元素无法获得的。

于 2013-05-15T16:51:47.080 回答
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 值的版本，因为您使用了更多来自伪随机分布的数字。如果您想要的是可靠的随机分布，这是一个非常简单的优化，它将大大提高您看到的“假随机性”的质量。或者，

于 2013-05-15T14:28:30.150 回答
0

这称为水库采样

于 2019-09-21T12:54:15.537 回答