我在 C++ 中实现了以下中位数，并通过 Rcpp 在 R 中使用它:

// [[Rcpp::export]]
double median2(std::vector<double> x){
  double median;
  size_t size = x.size();
  sort(x.begin(), x.end());
  if (size  % 2 == 0){
      median = (x[size / 2 - 1] + x[size / 2]) / 2.0;
  }
  else {
      median = x[size / 2];
  }
  return median;
}

如果我随后将性能与标准内置 R 中值函数进行比较，我将通过 microbenchmark

> x = rnorm(100)
> microbenchmark(median(x),median2(x))
Unit: microseconds
       expr    min     lq     mean median     uq     max neval
  median(x) 25.469 26.990 34.96888 28.130 29.081 518.126   100
 median2(x)  1.140  1.521  2.47486  1.901  2.281  47.897   100

为什么标准的中值函数这么慢？这不是我所期望的......

最佳答案

正如@joran 所指出的，您的代码非常专业，一般来说，不太通用的函数、算法等...通常性能更高。看看median.default :

median.default
# function (x, na.rm = FALSE) 
# {
#   if (is.factor(x) || is.data.frame(x)) 
#     stop("need numeric data")
#   if (length(names(x))) 
#     names(x) <- NULL
#   if (na.rm) 
#     x <- x[!is.na(x)]
#   else if (any(is.na(x))) 
#     return(x[FALSE][NA])
#   n <- length(x)
#   if (n == 0L) 
#     return(x[FALSE][NA])
#   half <- (n + 1L)%/%2L
#   if (n%%2L == 1L) 
#     sort(x, partial = half)[half]
#   else mean(sort(x, partial = half + 0L:1L)[half + 0L:1L])
# }

有几种操作可以适应缺失值的可能性，这些操作肯定会影响函数的整体执行时间。由于您的函数不会复制此行为，因此它可以消除一堆计算，但因此不会为具有缺失值的 vector 提供相同的结果:

median(c(1, 2, NA))
#[1] NA

median2(c(1, 2, NA))
#[1] 2

还有一些其他因素可能对NA 的处理没有那么大的影响。 s，但值得指出:

• median ，连同它使用的一些函数，都是 S3 泛型，因此在方法调度上花费了少量时间
• median将不仅仅使用整数和数字 vector ；它还将处理 Date , POSIXt ，可能还有一堆其他类，并正确保留属性:

median(Sys.Date() + 0:4)
#[1] "2016-01-15"

median(Sys.time() + (0:4) * 3600 * 24)
#[1] "2016-01-15 11:14:31 EST"

编辑: 我应该提到下面的函数将导致原始 vector 被排序因为NumericVector s 是代理对象。如果你想避免这种情况，你可以 Rcpp::clone输入 vector 并对克隆进行操作，或使用您的原始签名(带有 std::vector<double> )，这在从 SEXP 的转换中隐含地需要一个拷贝至 std::vector .

另请注意，使用 NumericVector 可以节省更多时间。而不是 std::vector<double> :

#include <Rcpp.h>

// [[Rcpp::export]]
double cpp_med(Rcpp::NumericVector x){
  std::size_t size = x.size();
  std::sort(x.begin(), x.end());
  if (size  % 2 == 0) return (x[size / 2 - 1] + x[size / 2]) / 2.0;
  return x[size / 2];
}

microbenchmark::microbenchmark(
  median(x),
  median2(x),
  cpp_med(x),
  times = 200L
)
# Unit: microseconds
#       expr    min      lq      mean  median      uq     max neval
#  median(x) 74.787 81.6485 110.09870 92.5665 129.757 293.810   200
# median2(x)  6.474  7.9665  13.90126 11.0570  14.844 151.817   200
# cpp_med(x)  5.737  7.4285  11.25318  9.0270  13.405  52.184   200

Yakk 在上面的评论中提出了一个很好的观点——Jerry Coffin 也对此进行了详细阐述——关于进行完整排序的效率低下。这是使用 std::nth_element 重写的，以更大的 vector 为基准:

#include <Rcpp.h>

// [[Rcpp::export]]
double cpp_med2(Rcpp::NumericVector xx) {
  Rcpp::NumericVector x = Rcpp::clone(xx);
  std::size_t n = x.size() / 2;
  std::nth_element(x.begin(), x.begin() + n, x.end());

  if (x.size() % 2) return x[n]; 
  return (x[n] + *std::max_element(x.begin(), x.begin() + n)) / 2.;
}

set.seed(123)
xx <- rnorm(10e5)

all.equal(cpp_med2(xx), median(xx))
all.equal(median2(xx), median(xx))

microbenchmark::microbenchmark(
  cpp_med2(xx), median2(xx), 
  median(xx), times = 200L
)
# Unit: milliseconds
#         expr      min       lq     mean   median       uq       max neval
# cpp_med2(xx) 10.89060 11.34894 13.15313 12.72861 13.56161  33.92103   200
#  median2(xx) 84.29518 85.47184 88.57361 86.05363 87.70065 228.07301   200
#   median(xx) 46.18976 48.36627 58.77436 49.31659 53.46830 250.66939   200

关于c++ - 为什么标准 R 中值函数比简单的 C++ 替代函数慢得多？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34771088/