C++ 从 0:n-1 (n > k) 范围内随机抽取 k 个数，不放回

Question

我正在努力将 MATLAB 模拟移植到 C++ 中。为此，我试图复制 MATLAB 的 randsample() function。我还没有想出一个有效的方法来做到这一点。

所以我问大家，在 C++ 中，如何最好地从范围 0:n-1（对于 n > k）中随机抽取 k 个数字而不进行替换？

我考虑过以下伪代码（灵感来自 cppreference.com 上的第三个示例），但我觉得它有点 hacky：

initialize vect<int> v of size n
for i = 0 to n-1
    v[i] = i
shuffle v
return v[0 to k-1]

这里的缺点也是需要先构建一个庞大的数组。这似乎 slow/clunky 矫枉过正。

如果你能帮忙的话，我很乐意在这里提供一些指导。我对理论不太感兴趣（算法很有趣，但现在与我的需求无关），而不是用 C++ 实现它的最佳方法。

提前致谢！

Answer 1

Bob Floyd 创建了一个使用集合的随机样本算法。中间结构大小与您要获取的样本大小成正比。

它的工作原理是随机生成 K 个数字并将它们添加到一个集合中。如果生成的数字碰巧已经存在于集合中，它会放置一个计数器的值，而不是保证还没有看到。从而保证在线性时间内运行，不需要很大的中间结构。它仍然具有很好的随机分布特性。

此代码基本上是从 Programming Pearls 中提取的，并进行了一些修改以使用更现代的 C++。

unordered_set<int> BobFloydAlgo(int sampleSize, int rangeUpperBound)
{
     unordered_set<int> sample;
     default_random_engine generator;

     for(int d = rangeUpperBound - sampleSize; d < rangeUpperBound; d++)
     {
           int t = uniform_int_distribution<>(0, d)(generator);
           if (sample.find(t) == sample.end() )
               sample.insert(t);
           else
               sample.insert(d);
     }
     return sample;
}

此代码尚未经过测试。

Answer 2

这是一种不需要生成和洗牌巨大列表的方法，以防 N 很大但 k 不是：

std::vector<int> pick(int N, int k) {
    std::random_device rd;
    std::mt19937 gen(rd());

    std::unordered_set<int> elems = pickSet(N, k, gen);

    // ok, now we have a set of k elements. but now
    // it's in a [unknown] deterministic order.
    // so we have to shuffle it:

    std::vector<int> result(elems.begin(), elems.end());
    std::shuffle(result.begin(), result.end(), gen);
    return result;
}

现在实现 pickSet 的简单方法是：

std::unordered_set<int> pickSet(int N, int k, std::mt19937& gen)
{
    std::uniform_int_distribution<> dis(1, N);
    std::unordered_set<int> elems;

    while (elems.size() < k) {
        elems.insert(dis(gen));
    }

    return elems;
}

但如果 k 相对于 N 较大，则此算法可能会导致大量冲突并且可能会非常慢。我们可以做得更好，保证我们可以在每次插入时添加一个元素（由 Robert Floyd 提供）：

std::unordered_set<int> pickSet(int N, int k, std::mt19937& gen)
{
    std::unordered_set<int> elems;
    for (int r = N - k; r < N; ++r) {
        int v = std::uniform_int_distribution<>(1, r)(gen);

        // there are two cases.
        // v is not in candidates ==> add it
        // v is in candidates ==> well, r is definitely not, because
        // this is the first iteration in the loop that we could've
        // picked something that big.

        if (!elems.insert(v).second) {
            elems.insert(r);
        }   
    }
    return elems;
}

Answer 3

从 C++17 开始，有一个标准函数：<algorithm> 库中的 std::sample。保证具有线性时间复杂度。

示例 _{（双关语）} 用法：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>

int main()
{
    std::vector<int> population {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    std::vector<int> sample;
    std::sample(population.begin(), population.end(), 
                std::back_inserter(sample),
                5,
                std::mt19937{std::random_device{}()});
    for(int i: sample)
        std::cout << i << " "; //prints 5 randomly chosen values from population vector

Answer 4

Bob Floyds 采样是一个很好的解决方案。 Reservoir sampling 然而，当 k 与 N 处于同一数量级时，这可能是一个不错的选择。

水库采样：

vector<size_t> reservoir_sample(const size_t& k,const size_t& N) {
  vector<size_t> sample;
  if (k==0) return sample;
  std::default_random_engine gen;
  size_t i;
  for (i=0;i!=k;++i) sample.push_back(i);
  for (;i<N;++i) {
    uniform_int_distribution<size_t> distr(0,i);
    if (distr(gen) > k) continue;
    distr = uniform_int_distribution<size_t>(0,k-1);
    sample[distr(gen)]=i;
  }
  std::shuffle(sample.begin(),sample.end(),gen);
  return sample;
}

鲍勃·弗洛伊德采样：

std::unordered_set<size_t> floyd_sample(const size_t& k,const size_t& N) {
  std::default_random_engine gen;
  // for the benchmark I used a faster hash table
  std::unordered_set<size_t> elems(k); //preallocation is good
  for (size_t r = N - k; r < N; ++r) {
    size_t v = std::uniform_int_distribution<>(1, r)(gen);
    if (!elems.insert(v).second) elems.insert(r);
  }
  return elems;
}

随机抽样不完整：

#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <iostream>
#include <iomanip>

using std::vector;
using std::uniform_int_distribution;
using std::shuffle;
using std::cout;
using std::swap;

template<class iterator,class generator>
void inline shuffle(iterator beg,iterator unt,iterator end,generator gen){
  const size_t n = end-beg;
  for (;beg!=unt;++beg) {
    size_t i=end-beg;
    size_t r=uniform_int_distribution<size_t>(0,i)(gen);
    swap(*beg,*(beg+r));
  }
}

template<class iterator>
vector<size_t> sample(const size_t& k,iterator beg,iterator end) {
  vector<size_t> sample(k);
  std::default_random_engine gen;
  if (k<(end-beg)/2) {
    shuffle(beg,beg+k,end,gen);
    for (size_t i=0;i!=k;(++i,++beg)) sample[i] = *beg;
  } else {
    const size_t l = end-beg-k;
    shuffle(beg,beg+l,end,gen);
    beg+=l;
    for (size_t i=0;i!=k;(++i,++beg)) sample[i] = *beg;
  }
  return sample;
}

int main(int argc,char** argv){
  vector<size_t> samples(std::stol(argv[2]));
  auto start = std::clock();
  std::iota(samples.begin(),samples.end(),0);
  sample(std::stol(argv[1]),samples.begin(),samples.end());
  cout << std::setw(12) << (std::clock()-start);
}

一些注意事项：std::shuffle 总是随机播放整个范围，但是当您只需要 k 个项目时，您可以在第 k 个元素处使用 fisher-yates 随机播放停止，使其成为最快的方法从已经存在的样本中抽样。

Answer 5

所以这是我想出的解决方案，它将以随机顺序生成样本，而不是以稍后需要打乱顺序的确定性方式：

vector<int> GenerateRandomSample(int range, int samples) {
  vector<int> solution; // Populated in the order that the numbers are generated in.
  vector<int> to_exclude; // Inserted into in sorted order.
  for(int i = 0; i < samples; ++i) {
    auto raw_rand = rand() % (range - to_exclude.size());
    // This part can be optimized as a binary search
    int offset = 0;
    while(offset < to_exclude.size() &&
        (raw_rand+offset) >= to_exclude[offset]) {
      ++offset;
    }
    // Alternatively substitute Binary Search to avoid linearly
    // searching for where to put the new element. Arguably not
    // actually a benefit.
    // int offset = ModifiedBinarySearch(to_exclude, raw_rand);

    int to_insert = (raw_rand + offset);
    to_exclude.insert(to_exclude.begin() + offset, to_insert);
    solution.push_back(to_insert);
  }  
  return solution;
}

我添加了一个可选的二进制搜索来查找新插入的位置生成了随机成员，但在尝试对其在大范围（N）/和集合（K）（在 codeinterview.io/ 上完成）的执行进行基准测试之后，我没有发现这样做有任何显着的好处，只是线性遍历和提前退出。

编辑：经过进一步的广泛测试，我发现了足够大的参数：（例如 N = 1000，K = 500，TRIALS = 10000）二进制搜索方法实际上提供了相当大的改进：对于给定的参数：使用二进制搜索：~2.7 秒线性：~5.1 秒确定性的（没有 Barry 在接受的基于 Robert Floyd 的答案中提出的洗牌）：~3.8 秒

int ModifiedBinarySearch(const vector<int>& collection, int raw_rand) {
  int offset = 0;
  int beg = 0, end = collection.size() - 1;
  bool upper_range = 0;
  while (beg <= end) {
    offset = (beg + end) / 2;
    auto to_search_for = (raw_rand+offset);
    auto left = collection[offset];
    auto right = (offset+1 < collection.size() ?
        collection[offset+1] :
        collection[collection.size() - 1]);
    if ((raw_rand+offset) < left) {
      upper_range = false;
      end = offset - 1;
    } else if ((raw_rand+offset+1) >= right) {
      upper_range = true;
      beg = offset + 1;
    } else {
      upper_range = true;
      break;
    }
  }
  offset = ((beg + end) / 2)  + (upper_range ? 1 : 0);
  return offset;
}

Answer 6

正如 Yksisarvinen 中指出的那样的回答，C++17在<algorithm>中提供了std::sample应该有用。不幸的是，它对迭代器的使用使得直接使用整数变得尴尬，即没有构建一个大的临时 array/vector，我让它有效工作的唯一方法是使用大量样板代码：

#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>

template<typename I>
class boxed_iterator {
    I i;

public:
    typedef I difference_type;
    typedef I value_type;
    typedef I pointer;
    typedef I reference;
    typedef std::random_access_iterator_tag iterator_category;

    boxed_iterator(I i) : i{i} {}

    bool operator==(boxed_iterator<I> &other) { return i == other.i; }
    I operator-(boxed_iterator<I> &other) { return i - other.i; }
    I operator++() { return i++; }
    I operator*() { return i; }
};

给我们一些与 std::sample:

一起使用时不会太痛苦的东西

int main()
{
    std::vector<int> result;

    auto rng = std::mt19937{std::random_device{}()};

    // sample five values without replacement from [1, 100]
    std::sample(
        boxed_iterator{1}, boxed_iterator{101},
        std::back_inserter(result), 5, rng);

    for (auto i : result) {
        std::cout << i << ' ';
    }
}

如果不需要 boxed_iterator 就好了，如果有人能告诉我怎么做就好了！

C++ 从 0:n-1 (n > k) 范围内随机抽取 k 个数，不放回

C++ randomly sample k numbers from range 0:n-1 (n > k) without replacement

c++

random