使用Rcpp调用std::uniform_int_distribution触发C栈溢出段错误

首先，栈溢出的核心原因是递归重试逻辑导致的递归深度过大，参数大小的差异影响了随机数碰撞概率，进而决定递归深度是否会耗尽栈空间。

为什么16^{15触发栈溢出，15}16却正常？ #

先明确两个参数的数值量级：

• 15^16 ≈ 4.38×10¹⁸
• 16^15 ≈ 1.15×10¹⁸

假设你调用函数时抽样的size参数固定（比如接近1e18）：

• 当传入n=15^16时，size远小于总体数量n，随机生成的数重复概率极低，每次操作几乎都能成功插入新元素，递归层数最多等于size，栈空间足够容纳这些栈帧。
• 当传入n=16^15时，size接近n，此时生成的随机数几乎都已在已选集合中，导致递归重试次数暴增——每一次失败的生成都会触发新的递归调用，递归深度直接超出栈的最大容量（通常仅几MB），最终触发栈溢出错误。

最可能的错误实现 #

如果你的函数用了类似下面的递归逻辑，必然会出现这个问题：

void sample_int(long long n, long long size, std::set<long long>& res) {
    if (res.size() == size) return;
    long long r = generate_uniform_random(1, n);
    if (!res.count(r)) {
        res.insert(r);
    }
    sample_int(n, size, res); // 递归重试，导致深度爆炸
}

解决方案 #

把递归逻辑改成循环，彻底避免递归栈耗尽的问题：

#include <unordered_set>
#include <random>

void sample_int(long long n, long long size, std::unordered_set<long long>& res) {
    // 边界处理：无放回抽样不能抽取比总体更多的元素
    if (size > n) {
        throw std::invalid_argument("size cannot exceed n for replace=FALSE");
    }
    
    std::random_device rd;
    std::mt19937_64 gen(rd());
    std::uniform_int_distribution<long long> dist(1, n);
    
    while (res.size() < size) {
        long long r = dist(gen);
        res.insert(r); // unordered_set自动去重，无需提前判断
    }
}

另外，用std::unordered_set替代std::set可以大幅提升插入和查找的效率（平均O(1) vs O(logk)），尤其当size很大时效果明显。

内容的提问来源于stack exchange，提问作者BerriJ