¿Por qué mi código Rcpp no es mucho más rápido?
Para practicar mi C ++, estoy tratando de convertir un código R a Rcpp. El código es un algoritmo codicioso implementado enesta respuesta.
A continuación, vea mi código Rcpp (en un archivo .cpp) y algunos puntos de referencia de los dos códigos:
#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
)
*/
Para este tipo de problema (bucle una y otra vez sobre un vector), esperaba que mi versión Rcpp fuera mucho más rápida, pero obtengo este resultado para el punto de referencia:
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
¿Alguna idea de por qué mi código Rcpp no es mucho más rápido que la versión R?