C++中最佳的随机抽样方法

Question

我有一个长度为一百万的数据向量A（从0到一百万）。我想要创建一个向量B（长度为A的10%），包含A中的索引。这些索引是从A中随机抽取的样本索引。我尝试使用srand()和random_shuffle，但这是提取非常大的向量样本的好方法吗？请问是否有其他建议？

  std::vector <int> samplingIndex;

   for (int i = 0; i < 1000000; ++i) { samplingIndex.push_back(i); } 
   std::srand(50); 
   std::random_shuffle(samplingIndex.begin(), samplingIndex.end());

接下来，我将从采样索引中选择前10%的索引，以创建B。

- Hum

---

srand和random_shuffle在C++11中都已被弃用。 - Konrad Rudolph

也许值得看一下https://dev59.com/tXVD5IYBdhLWcg3wOo5h#48089 - Jackson

Answer 1

您可以使用Fisher–Yates shuffle，并避免构建巨大的数组a：

类似于：

// Fisher–Yates_shuffle
std::vector<int> FisherYatesShuffle(std::size_t size,
                                    std::size_t max_size,
                                    std::mt19937& gen)
{
    assert(size <= max_size);
    std::vector<int> res(size);

    for (std::size_t i = 0; i != max_size; ++i) {
        std::uniform_int_distribution<> dis(0, i);
        std::size_t j = dis(gen);
        if (j < res.size()) {
            if (i < res.size()) {
                res[i] = res[j];
            }
            res[j] = i;
        }
    }
    return res;
}

{{链接1:实时示例}}

- Jarod42

Answer 2

看起来很合理。一个小调整是你可以用这个替换你的for循环，以避免重复重新分配向量：

std::vector <int> samplingIndex(1000000);
std::iota(samplingIndex.begin(), samplingIndex.end(), 0);

如果您的取值百分比远小于10％，那么只需在[0，len（A））范围内生成随机数，直到获得len（B）个不同的值即可。

- John Zwinck

---

感谢@John。random_shuffle是一个好的采样器（均匀采样器）吗？例如，我想通过逐位比较观察两个长度巨大（1M）向量中错误位数的数量。比较应该在不到10％的位数内完成（这些位应该代表整个向量的错误趋势）。因此，从random_shuffle中提取的10％位应该是均匀的。即从提取的10％位和20％位中获得的错误百分比应该更多或更少相同。 - Hum

@Hum 请看我上面的评论。random_shuffle本身使用的是无偏算法，但它使用的随机数生成器是有偏的。使用std::shuffle可以获得更好的结果。 - Konrad Rudolph

@John：不是不同的值，而是不同的索引... 这非常不同。 - Gianluca Ghettini

Answer 3

你的代码是使用旧版C++编写的。我觉得你应该仔细看看新版C++11/14中的随机数。

http://en.cppreference.com/w/cpp/algorithm/random_shuffle

- Dakorn

Answer 4

如果您的输入来自AWGN源（或接近它），您可以每10个样本选择1个样本，并在O（N）时间内完成任务（您想要随机样本的10％吗？）

否则，从巨大向量中提取10％的随机样本的一种非常有效的方法是随机选择样本并每次存储所选索引。继续随机选择项目，并在索引已被选择时重复此过程。是的，这是一种概率方法，但在最佳和平均情况下，您可以实现O（N）复杂度。最坏的情况是您不断选择相同的索引，但这意味着PRNG实现非常糟糕：您可以将最坏的情况视为非常不可能的情况（只需保持像哈希函数中那样的赔率足够低即可）

您还可以使用链表并“短路”所选样本（将PRNG输出空间减少到N-1），但这将需要额外的内存来存储链表。

- Gianluca Ghettini