c++ - 提升随机样本，如 python random.sample

Question

我正在尝试使用 C++ 来模仿 python

random.sample(a_set, n_samples)

C++ 函数

set<string> sample(set<string> input, int n_samples)

在写我自己的之前，有没有图书馆这样做？我的电脑上有boost 1.46。

Answer 1

由于 C++17 有std::sample：

std::sample(input.begin(), input.end(), std::back_inserter(out),
            n_samples, std::mt19937{std::random_device{}()});

原始答案如下。我把它留在这里供参考。

---

SGI的STL 实现具有random_sample和random_sample_n功能：

template <class InputIterator, class RandomAccessIterator>
Random AccessIterator random_sample(InputIterator first, InputIterator last,
                                    RandomAccessIterator ofirst,
                                    RandomAccessIterator olast) 

template <class ForwardIterator, class OutputIterator, class Distance>
OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
                               OutputIterator out, Distance n)

random_sample_n随机将范围内的元素样本复制[first, last)到范围内[out, out + n)。输入范围内的每个元素在输出范围内最多出现一次，并且以均匀概率选择样本。

很遗憾

Matt Austern 提出了几个额外的算法（大部分取自 SGI 的标准库的原始 STL 实现）。其中包括 random_sample和random_sample_n

^{（来自N3925）}

但

在 Sophia-Antipolis 会议上 WG21 审议后，Austern 更新了提案，产生了 [N2666]。在其他变化中，他撤回了采样算法，因为“LWG 担心它们可能对标准化的理解不够好……为 TR2 提出这些算法可能是合适的”。LWG 随后达成了坚实的共识（10-1, 2 abs.），支持在未来的技术报告（现在称为技术规范）中包含这些算法。

该算法的一个版本random_sample_n已进入 Library Fundamentals TS 并被称为std::experimental::sample，提案N3925的最新迭代于 2014-02 被采用，但仍未成为标准的一部分（可能在 C++17 中）。

除了储层采样算法之外，您还可以查看Donald Knuth 在计算机编程艺术 - 第 2 卷 - §3.4.2 中阐述的著名算法 S（“选择采样技术”）。

Answer 2

您要解决的问题称为水库采样。我尝试在谷歌上搜索“水库采样 C++ 实现”。谷歌自动为我完成了查询，但粗略地浏览一下结果并没有找到一个实际的库。

该算法非常简单，而且很有趣，可以自己学习和编写，所以这就是我推荐的。