Rcpp 样本与 C++ shuffle 的效率对比

Question

我正在尝试优化 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 的版本要慢得多，直到您对包含约 50,000 个元素的向量进行洗牌。对于更接近我的大多数用例的示例，以下生成的 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 之外调用 algorithm/random 数字生成器是否有一些惩罚来解释这种性能差异？感谢您的任何建议。

编辑为了说明 C++ 版本的低效率并不是因为必须将标准向量转换为 IntegerVectors，我修改了 Rcpp 版本，以便在对 IntegerVectors 进行采样之后过度转换为标准向量（然后返回 IntegerVectors）。

更新

我对替代伪随机数生成器进行了一些试验。 This post suggest that the Mersenne Twister pseudo random number generator I use above is relatively slow compared to some alternatives. I tried the pseudo random number generators coded 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);
}

对于 1,000 的矢量，Rcpp 版本仍然快得多，大约 13 毫秒，而使用 C++ 洗牌的最快 RNG 为 20 毫秒。

据我了解，C++ shuffle 实现了 Fisher - Yates (Knuth) shuffle。我现在的猜想是，当所有元素都被无放回地采样时，Rcpp 采样函数没有实现 Fisher-Yates 洗牌，而是利用排序算法？也许 C++ 中有一个类似的算法，它比我的应用程序的 shuffle 更快？

Answer 1

正如我在评论中提到的，您的函数可能 'do too much'。这是一个简化的示例（这也是荒谬的，因为我们可能每次都会更改输入向量）但它将您的问题提炼为 'is sample faster than shuffle from the standard library'。而事实并非如此。

我修改后的代码如下。

代码

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

// [[Rcpp::export]]
Rcpp::IntegerVector shuffle_cpp(Rcpp::IntegerVector x)  {
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(x.begin(), x.end(), g);
    return x;
}

// [[Rcpp::export]]
Rcpp::IntegerVector sample_rcpp(Rcpp::IntegerVector x)  {
    return sample(x, x.size());
}

/*** R
v <- seq(1, 1e6)
res <- bench::mark(min_iterations = 100, check = FALSE, shuffle_cpp(v), sample_rcpp(v))
res
ggplot2::autoplot(res) + ggplot2::theme_minimal() + ggplot2::ylab(NULL)
*/

Rcpp 样本与 C++ shuffle 的效率对比

Efficiency of Rcpp sample v. C++ shuffle

c++

r

rcpp

shuffle

代码