r - 为什么我的 Rcpp 代码没有快多少？

Question

为了练习我的 C++，我尝试将一些 R 代码转换为 Rcpp。代码是this answer中实现的贪心算法.

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

#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 版本要快得多，但我得到了这个基准测试结果:

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 版本快多少吗？

Answer 1

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

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

这更好，但我仍然期待更多。我认为我的算法仍然是输入大小的二次方，这就是为什么我无法获得显着改进的原因。