貯蔵庫サンプリング(Reservoir sampling)
入力(数>n)からn個をランダムに選択する方法。
1. 最初のn個をI[0]...I[n-1]にコピーする。t = n - 1。
2. 入力値がなかったら、5へ。
3. ++tとし、[0, t]の一様乱数uを生成する。 u >= nならば、2へ。
4. I[u] = I[t]とし、2へ。
5. Iをソートして終了。
#include <random> #include <iostream> #include <vector> #include <assert.h> #include <algorithm> template <typename U> const std::vector<int>& generate( U& u, const std::vector<int>& inputs, std::vector<int>& i, std::size_t n, std::size_t t) { if (inputs.size() <= t) { std::sort(i.begin(), i.end()); return i; } std::size_t r = static_cast<std::size_t>(t * u()); ++t; if (r >= n) return generate(u, inputs, i, n, t); i[r] = inputs[t]; return generate(u, inputs, i, n, t); } template <typename U> std::vector<int> generate( U& u, const std::vector<int>& inputs, std::size_t n) { assert(inputs.size() >= n); std::vector<int> results(inputs.begin(), inputs.begin() + n); return generate(u, inputs, results, n, n); } int main() { unsigned int seed = 54635; std::mt19937 mt(seed); std::uniform_real_distribution<double> d; std::size_t size = 100; std::vector<int> inputs(size); for (std::size_t j = 0; j < inputs.size(); ++j) { inputs[j] = j; } std::size_t n = 10; std::vector<int> r = generate([&]() {return d(mt); }, inputs, n); for (auto x : r) std::cout << x << std::endl; return 0; }