Rcpp sample v. C++ shuffle 的效率

我正在try 为R优化一个算法.最初，我使用Rcpp(和Rcpp向量等)编写了该算法，但随后使用标准C++向量重写了该算法，并仅在最后阶段将其转换为Rcpp.然而，涉及shuffle的C++算法组件似乎相当慢.事实上，来回转换为Rcpp向量以便使用Rcpp/R sample函数要快得多.这让我很惊讶.

下面是一个可重复性最低的示例:

#include <Rcpp.h>
#include <random>
#include <algorithm>

// [[Rcpp::export]]

List test_cpp(int n, int x)  {

  List return_list(n);

  std::vector<int> v;
  v.reserve(x);

  for(int i = 0; i < x; ++i) {
    v.push_back(i);
  }

  std::random_device rd;
  std::mt19937 g(rd());

  for(int i = 0; i < n; ++i)  {
    std::shuffle(v.begin(), v.end(), g);
    return_list(i) = v;
  }

  return return_list;
}


// [[Rcpp::export]]

List test_r(int n,
            int x)  {

  List return_list(n);

  std::vector<int> v;
  v.reserve(x);

  for(int i = 0; i < x; ++i){
      v.push_back(i);
    }

  IntegerVector vs = wrap(v);

  for(int i = 0; i < n; ++i)  {
    IntegerVector s_v = sample(vs, v.size());
    std::vector<int> s_v_c = as<std::vector<int>>(s_v);
    return_list(i) = s_v_c;
  }

  return return_list;
}

使用C++shuffle的第一个函数要比使用Rcpp sample的版本慢得多，直到你洗牌了大约50000个元素的向量.对于一个更接近我的大多数用例的示例，下面生成的Rcpp sample的中值时间约为13 ms，而C++shuffle的中值时间约为20 ms.

n <- 1000
x <- 999

speed <- bench::mark(min_iterations = 100, 
                       check = FALSE,
                       cpp = test_cpp(n, x),
                       rcpp = test_r(n, x)
                       )

  ggplot2::autoplot(speed) +
    ggplot2::theme_minimal() +
    ggplot2::xlab(NULL) +
    ggplot2::ylab(NULL) 

很可能我把C++代码弄糟了.如果是的话，有人能告诉我我的错误吗？还是shuffle太慢了，我应该使用不同的C++算法？或者，在R/Rcpp之外调用一个算法/随机数生成器来解释性能上的差异，会有什么损失吗？感谢您的建议.

Edit为了说明C++版本的效率低下并不是因为必须将标准向量转换为整数，我修改了Rcpp版本，以便在采样后将整数多余地转换为标准向量(然后再转换回整数).

Update

我try 了一些替代的伪随机数生成器.This post表明我上面使用的Mersenne Twister伪随机数生成器与一些备选方案相比相对较慢.我try 了编码为in this post的伪随机数生成器，它们确实更快，但并没有显著提高性能.下面是我的简化测试函数.

// [[Rcpp::export]]

void test_pcg(int x)  {
  std::vector<int> v;   
  v.reserve(x);
  for(int i = 0; i < x; ++i) {
    v.push_back(i);
  }
  std::random_device rd;   
  pcg g(rd);
  std::shuffle(v.begin(), v.end(), g);
}


  // [[Rcpp::export]]

  void test_mt(int x)  {
    std::vector<int> v;
    v.reserve(x);
    for(int i = 0; i < x; ++i) {
      v.push_back(i);
    }
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(v.begin(), v.end(), g);
  }


// [[Rcpp::export]]

void test_splitmix(int x)  {
  std::vector<int> v;   
  v.reserve(x);
  for(int i = 0; i < x; ++i) {
    v.push_back(i);
  }
  std::random_device rd;   
  splitmix g(rd);   
  std::shuffle(v.begin(), v.end(), g);
}



// [[Rcpp::export]]

void test_xorshift(int x)  {
  std::vector<int> v;   
  v.reserve(x);
  for(int i = 0; i < x; ++i) {
    v.push_back(i);
  }
  std::random_device rd;   
  xorshift g(rd);
  std::shuffle(v.begin(), v.end(), g);
}


// [[Rcpp::export]]

void test_rcpp(int x)  {
  IntegerVector v = seq(0, x);   
  IntegerVector s_v = sample(v, x);
}

对于1000的向量，Rcpp版本仍然要快很多，大约13毫秒，而对于使用C++shuffle的速度最快的RNG，则要快20毫秒.

据我所知，C++shuffle实现了Fisher-Yates(Knuth)shuffle.我现在的猜测是，当所有元素都在不替换的情况下采样时，Rcpp样本函数不会实现Fisher-Yates洗牌，而是使用排序算法？对于我的应用程序来说，也许C++中有一种类似的算法比shuffle更快？