3.5、std::sample算法

template<class PopulationIterator, class SampleIterator, 
         class Distance, class URBG>
SampleIterator sample(PopulationIterator first, PopulationIterator last,
                      SampleIterator out, Distance n, URBG&& g);

这个设计反映了C++的几个重要理念：

• • 泛型编程：通过模板支持各种容器类型
• • 迭代器抽象：分离算法与数据结构
• • 组合性：与随机数生成器的无缝集成

std::sample的设计精髓在于它能够在O(n)的时间复杂度内完成采样，而不需要先对全集进行洗牌，这在处理大数据集时尤为重要。

基础用法详解

让我们通过一个简单例子了解std::sample的基本用法：

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

int main() {
    // 源数据集合
    std::vector<int> source{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 存储采样结果的容器（预先分配空间）
    std::vector<int> result(3);
    
    // 创建随机数生成器
    std::random_device rd;  // 用于获取真随机种子
    std::mt19937 gen(rd()); // 梅森旋转算法生成器
    
    // 执行随机采样
    std::sample(source.begin(), source.end(), 
                result.begin(), 3, gen);
    
    // 输出结果
    for(auto x : result) {
        std::cout << x << " ";
    }
    
    return 0;
}

这段代码从1到10的数字中随机选择3个不重复的数字。值得注意的是，我使用了std::random_device和std::mt19937组合来获取高质量的随机序列，这对于统计学应用尤为重要。

进阶技巧与深度剖析

1. 灵活处理不同容器类型

std::sample的一大优势是可以跨容器类型工作：

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <random>

int main() {
    // 从list采样到vector
    std::list<std::string> names{"张三", "李四", "王五", "赵六", "钱七"};
    std::vector<std::string> selected(2);
    
    std::random_device rd;
    std::mt19937 gen(rd());
    
    std::sample(names.begin(), names.end(), selected.begin(), 2, gen);
    
    // 从set采样到deque
    std::set<double> measurements{1.2, 3.4, 2.7, 4.1, 5.3};
    std::deque<double> samples;
    samples.resize(3);
    
    std::sample(measurements.begin(), measurements.end(), 
                samples.begin(), 3, gen);
    
    return 0;
}

这种灵活性体现了泛型编程的强大，使得std::sample可以适应各种数据结构。

2. 利用返回值优化性能

std::sample返回一个指向结果集最后元素之后位置的迭代器，我们可以利用这个特性：

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

int main() {
    std::vector<int> bigData(1000);
    // 填充数据
    for(int i = 0; i < 1000; ++i) {
        bigData[i] = i;
    }
    
    // 创建足够大的输出容器
    std::vector<int> samples(100);
    
    std::random_device rd;
    std::mt19937 gen(rd());
    
    // 使用返回值确定实际采样范围
    auto end_it = std::sample(bigData.begin(), bigData.end(), 
                              samples.begin(), 10, gen);
    
    // 仅处理采样得到的元素
    for(auto it = samples.begin(); it != end_it; ++it) {
        std::cout << *it << " ";
    }
    
    return 0;
}

这种模式允许我们精确地处理采样结果，不浪费额外的计算资源。

3. 随机性的掌控与调优

随机性对采样至关重要，我们可以通过控制随机数引擎实现可重现或不可重现的结果：

// 可重现的采样结果（固定种子）
std::mt19937 gen1(42);  // 使用固定种子
std::sample(data.begin(), data.end(), result.begin(), 5, gen1);

// 每次不同的采样结果
std::random_device rd;
std::mt19937 gen2(rd());  // 使用随机设备作为种子
std::sample(data.begin(), data.end(), result.begin(), 5, gen2);

这种控制在科学实验、调试和测试中非常有价值。

底层实现原理探秘

std::sample的内部实现基于"池采样算法"（Reservoir Sampling）或"选择采样算法"（Selection Sampling），具体取决于迭代器类型：

• • 当源是前向迭代器时，使用池采样算法，这使得即使在无法预知总体大小的情况下也能进行有效采样。
• • 当源是随机访问迭代器时，会采用更高效的选择采样算法，直接计算选取哪些元素。

实现中的关键考量是如何在O(n)时间内完成采样，同时保证每个元素被选中的概率相等。这种精心设计的算法确保了std::sample在各种场景下的高效运行。

常见错误与避坑指南

1. 未设置随机数种子

// 错误做法：每次运行结果相同
std::default_random_engine gen;
std::sample(data.begin(), data.end(), result.begin(), 5, gen);

// 正确做法：使用随机设备作为种子
std::random_device rd;
std::mt19937 gen(rd());
std::sample(data.begin(), data.end(), result.begin(), 5, gen);

不设置随机种子将导致每次程序运行时获得相同的"随机"样本，这在多数应用场景下并不符合预期。

2. 输出容器空间不足

// 错误做法：没有足够空间存储结果
std::vector<int> source{1, 2, 3, 4, 5};
std::vector<int> result;  // 空容器
std::sample(source.begin(), source.end(), result.begin(), 3, gen); // 运行时错误

// 正确做法：预先分配足够空间
std::vector<int> result(3);
// 或使用插入迭代器
std::vector<int> result;
std::sample(source.begin(), source.end(), 
            std::back_inserter(result), 3, gen);

确保输出容器有足够空间或使用插入迭代器是避免这类错误的关键。

3. 忽略迭代器要求

std::sample对迭代器类型有特定要求：如果源不是前向迭代器，目标必须是随机访问迭代器。违反这些要求会导致编译错误或运行时问题。

面试中可能遇到的问题

问题：std::sample和std::random_shuffle有什么区别？
答案：std::random_shuffle将整个序列随机打乱，而std::sample只选择指定数量的元素而不改变原序列。此外，std::random_shuffle在C++17中已被废弃，应使用std::shuffle替代。

问题：实现一个简化版的reservoir sampling算法
答案：池采样是std::sample的核心算法之一，简化实现如下：

template<class Iterator, class OutputIt, class URBG>
OutputIt reservoir_sample(Iterator first, Iterator last, 
                         OutputIt out, size_t k, URBG& g) {
    std::vector<typename std::iterator_traits<Iterator>::value_type> reservoir;
    reservoir.reserve(k);
    
    // 填充前k个元素
    size_t count = 0;
    for (; first != last && count < k; ++first, ++count) {
        reservoir.push_back(*first);
    }
    
    // 处理剩余元素
    std::uniform_int_distribution<size_t> dist(0, count);
    while (first != last) {
        size_t i = dist(g);
        if (i < k) {
            reservoir[i] = *first;
        }
        ++count;
        ++first;
        dist = std::uniform_int_distribution<size_t>(0, count);
    }
    
    return std::copy(reservoir.begin(), reservoir.end(), out);
}

问题：如何确保std::sample的结果不会包含重复元素？
答案：std::sample本身就保证了无重复采样。它会从输入范围中选择不同位置的元素，所以只要输入范围中的元素互不相同，采样结果就不会有重复。

实战应用案例

案例：智能推荐系统中的随机推荐

假设我们正在开发一个推荐引擎，需要从大量候选项中随机选择几个进行推荐：

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

struct Product {
    int id;
    std::string name;
    double relevance_score;
    // 其他产品属性...
};

class RecommendationEngine {
private:
    std::mt19937 rng;
    
public:
    RecommendationEngine() : 
        rng(std::chrono::system_clock::now().time_since_epoch().count()) {}
    
    std::vector<Product> getRandomRecommendations(
            const std::vector<Product>& candidates, 
            size_t count) {
        std::vector<Product> recommendations(count);
        
        // 使用std::sample随机选择推荐产品
        std::sample(candidates.begin(), candidates.end(),
                   recommendations.begin(),
                   std::min(count, candidates.size()),
                   rng);
                   
        return recommendations;
    }
    
    std::vector<Product> getWeightedRecommendations(
            const std::vector<Product>& candidates,
            size_t count) {
        // 根据相关性分数排序
        std::vector<Product> sorted_candidates = candidates;
        std::sort(sorted_candidates.begin(), sorted_candidates.end(),
                 [](const Product& a, const Product& b) {
                     return a.relevance_score > b.relevance_score;
                 });
        
        // 从前20%的高相关产品中随机选择
        size_t top_portion = sorted_candidates.size() / 5;
        if (top_portion < count) top_portion = sorted_candidates.size();
        
        std::vector<Product> recommendations(count);
        std::sample(sorted_candidates.begin(),
                   sorted_candidates.begin() + top_portion,
                   recommendations.begin(),
                   std::min(count, top_portion),
                   rng);
                   
        return recommendations;
    }
};

这个案例展示了std::sample在实际业务场景中的应用，它可以轻松实现随机推荐或加权随机推荐功能。

总结与展望

std::sample作为C++17的新成员，为随机采样这一常见需求提供了标准化、高效的解决方案。它的设计体现了C++标准库追求的简洁、高效和通用性原则。
本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）