为什么我的 Rcpp 代码并没有快多少?

本文介绍了为什么我的 Rcpp 代码并没有快多少?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

为了练习我的 C++，我正在尝试将一些 R 代码转换为 Rcpp.代码是在这个答案中实现的贪婪算法.

For practicing my C++, I'm trying to convert some R code to Rcpp. The code is a greedy algorithm implemented in this answer.

接下来，查看我的 Rcpp 代码(在 .cpp 文件中)，以及两个代码的一些基准:

Next, see my Rcpp code (in a .cpp file), and some benchmark of the two codes:

#include <Rcpp.h> using namespace Rcpp; // [[Rcpp::export]] List create_groups2(const NumericVector& x, double thr) { int n = x.size(); List res(n); int c = 0; double sum; std::list<double> x2(n); std::copy(x.begin(), x.end(), x2.begin()); // copy x in x2 x2.sort(std::greater<double>()); // sort in descending order std::list<double>::iterator it; NumericVector x3(n); int i = 0, c2; while (x2.size()) { sum = 0; c2 = 0; for (it = x2.begin(); it != x2.end();) { if ((sum + *it) <= thr) { sum += *it; x3[i] = *it; i++; c2++; it = x2.erase(it); if (sum >= thr) break; } else { it++; } } res[c] = x3[seq(i - c2, i - 1)]; c++; } return res[seq_len(c) - 1]; } /*** R y <- c(18, 15, 11, 9, 8, 7) create_groups2(sample(y), 34) create_groups <- function(input, threshold) { input <- sort(input, decreasing = TRUE) result <- vector("list", length(input)) sums <- rep(0, length(input)) for (k in input) { i <- match(TRUE, sums + k <= threshold) if (!is.na(i)) { result[[i]] <- c(result[[i]], k) sums[i] <- sums[i] + k } } result[sapply(result, is.null)] <- NULL result } x_big <- round(runif(1e4, min = 1, max = 34)) all.equal( create_groups(x_big, 34), create_groups2(x_big, 34) ) microbenchmark::microbenchmark( R = create_groups(x_big, 34), RCPP = create_groups2(x_big, 34), times = 20 ) */

对于这种类型的问题(在向量上循环)，我希望我的 Rcpp 版本要快得多，但我得到了这个基准测试结果:

For this type of problem (looping over and over a vector), I was expecting my Rcpp version to be much faster, but I get this result for the benchmark:

Unit: milliseconds expr min lq mean median uq max neval cld R 584.0614 590.6234 668.4479 717.1539 721.9939 729.4324 20 b RCPP 166.0554 168.1817 170.1019 170.3351 171.8251 174.9481 20 a

知道为什么我的 Rcpp 代码比 R 版本快不了多少吗?

推荐答案

好吧，70% 的时间都用于对列表进行排序 (x2.sort(std::greater());).我认为这是因为列表不是连续的数据(与向量相比).

Okay, 70% of the times is used for ordering the list (x2.sort(std::greater<double>());). I think this is because lists are not contiguous data (as compared to a vector).

因此，删除这一行并使用 create_groups2(sort(x_big,driving = TRUE), 34) 将性能提高 3，这使得 Rcpp 版本比 R 版本快 9-11.5 倍x_big 大小为1e4-1e5.

So, removing this line and using create_groups2(sort(x_big, decreasing = TRUE), 34) improve performance by 3, which makes the Rcpp version 9-11.5 times faster than the R version for x_big of size 1e4-1e5.

这更好，但我仍然期待更多.我认为我的算法在输入的大小上仍然是二次的，这就是为什么我不能得到显着的改进.

This is better, but I was still expecting much more. I think my algorithm is still quadratic in the size of the input, this is why I can't get dramatic improvements.