r - 加速代码: reducing 'user' time

Question

我有一个将被大量调用的函数(在优化中每次迭代大约调用 10^11 次，用于一些不同的实验)。我已经实现了一个快速版本，但我正在努力了解如何提高性能。 “系统”时间最少，而用户时间却很高。

这是代码，它接受一个整数并返回一个向量，该向量表示该整数是不同的基数计数系统(例如，base = 2 给出二进制，base = 10 给出标准结果)。参数k给出了要返回的向量的长度，因此前面可能有很多零。

正如您将看到的，这些函数需要 5 或 7 秒才能运行，但都不是系统时间。我想了解为什么，以及是否有方法可以加快速度。我对其他函数也有同样的问题(99% 的时间都花在循环中的一个函数上，但将其加速 200 倍只使运行时间减半)，但为了清楚起见，我展示了这个。

library(Rcpp)
library(microbenchmark)

# Rcpp version of the function
cppFunction('
NumericVector convert10tobase_c(double number_b10, int k, int base = 4){
    if(number_b10 >= pow(base, k)){
        stop("k is not large enough to contain the number in this base");
    }
    NumericVector ret(k);
    if(k == 1){
        return number_b10;
    }
    for (int i = 1 ;i < k; i++){
        double entry = floor(number_b10 / pow(base, (k - i)));
        ret[i-1] = entry;
        number_b10 = number_b10 - entry * pow(base, (k - i));
    }
    ret[k-1] = number_b10;
    return ret;
}')

# R version of the function
convert10tobase <- function(number_b10, k, base = 5){
    if(number_b10 >= base ^ k){
        stop("k is not large enough to contain the number in this base")
    }
    ret <- rep(0, k)
    if(k == 1){
        return(number_b10)
    }
    for (i in 1:(k - 1)){
        entry <- floor(number_b10 / base^(k-i))
        ret[i] <- entry
        number_b10 <- number_b10 - entry * (base ^ (k - i))
    }
    ret[k] <- number_b10
    return(ret)
}

# generate test data one hundred, thousand and million integers
set.seed(1)
base <- 4
k <- 8
ints_short <- floor(runif(1e2) * (base^k))
ints_long <- floor(runif(1e4) * (base^k))
ints_v_long <- floor(runif(1e6) * (base^k))

# benchmark the Rcpp version
microbenchmark(
    one = convert10tobase_c(ints_short[1], k, base),
    hundred = sapply(1:length(ints_short), function(i) convert10tobase_c(ints_short[i], k, base)),
    ten_thous = sapply(1:length(ints_long), function(i) convert10tobase_c(ints_long[i], k, base)),
    times = 100)

# test R and Rcpp times
r_start <- proc.time()
t <- sapply(1:length(ints_v_long), function(i) convert10tobase(ints_v_long[i], k, base))
r_stop <- proc.time()

c_start <- proc.time()
t <- sapply(1:length(ints_v_long), function(i) convert10tobase_c(ints_v_long[i], k, base))
c_stop <- proc.time()

# results - little time in 'system'
r_stop - r_start
c_stop - c_start

顺便说一句，我还对调用该函数一次、一百次和十万次进行了比较。一百次调用的时间比一次慢三百倍，一万次调用比一百次调用慢三十倍。我想了解原因，并感谢任何可以解释它的资源。

谢谢!

Answer 1

R 非常擅长高效地对多个相似的事物执行相同的操作。因此，如果在执行某些操作之前将相似的内容组合在一起，您的代码会变得更加高效。一开始这可能有点棘手，尤其是当您来自其他编码背景时。

这是一个解决方案，其中您的函数在 R 中进行矢量化(不确定这与 C++ 循环有何关系，可能是内部的东西)。它可能可以进一步优化，但它比对每个单独的数字使用 sapply 快 100 倍。它返回一个矩阵，其中输入的每个数字占一行，每个条目占一列。当数字大于base ^k时，将返回一行 NA。在进一步处理输出时，可以轻松识别该行。

convert10tobase_v <- function(number_b10, k, base = 5){
  orig_b10 <- number_b10 #save original for check after
  if(k == 1){
    return(number_b10)
  }
  #initialize matrix to store results
  ret <- matrix(0, ncol=k, nrow=length(number_b10))
  #tiny-forloop, won't influenc performance and makes
  #storing results/modifying number_b10 easier
  for (i in 1:(k - 1)){
    entry <- floor(number_b10 / base^(k-i))
    ret[,i] <- entry
    number_b10 <- number_b10 - entry * (base ^ (k - i))
  }
  ret[,k] <- number_b10
  ret[orig_b10 >= base ^ k,] <- NA #set 'too large' numbers to missing
  return(ret)
}

微基准测试:

Unit: microseconds
              expr        min          lq         mean     median          uq        max neval cld
        one_single     20.216     25.1910     31.94323     29.079     37.6310     58.469   100 a  
   hundred_singles   2217.461   2317.9145   2499.23338   2386.336   2498.4525   4436.476   100  b 
 ten_thous_singles 240467.874 246613.1635 253205.12598 249890.060 252432.2090 307050.155   100   c
             one_v     22.703     26.5910     33.09706     30.323     36.3875     62.823   100 a  
         hundred_v     53.181     56.9135     68.05703     61.889     75.5740    129.066   100 a  
       ten_thous_v   2641.359   2707.2920   2806.83843   2744.613   2827.9620   4645.160   100  b