任何/所有的高效版本

Question

我经常遇到需要检查某个条件是否适用于非常大的向量或列表的任何或所有元素的情况.例如,检查列表是否包含NULL我将使用的任何/仅元素:

any(vapply(x, is.null, logical(1))
all(vapply(x, is.null, logical(1))

然而,这是低效的,因为它总是检查列表中的每个元素.更聪明的实现将停止检查何时找到第一个NULL或非NULL元素.即相当于:

is.null(x[[1]]) || is.null(x[[2]]) || is.null(x[[3]]) || ...
is.null(x[[1]]) && is.null(x[[2]]) && is.null(x[[3]]) && ...

用for循环执行此操作很慢.r-base提供了一些特殊情况,例如,这anyNA是一个有效的版本any(is.na(.)).但是我想知道我们是否可以更普遍地实现它并提供用于检查条件的优化函数:

all_fast(x, is.null)
any_fast(x, is.null)

但是也:

all_fast(x, function(z) {length(z) == 2})
all_fast(x, is, "POSIXt")

Answer 1

这是天真的方式,

all0 <- function(x, FUN)
    all(vapply(x, FUN, logical(1)))

和一个R循环......

all1 <- function(x, FUN) {
    for (xi in x)
        if (!FUN(xi))
            return(FALSE)
    TRUE
}

......可编译

library(compiler)
all1c <- cmpfun(all1)

......或用C写的

library(inline)
allc <- cfunction(signature(x="list", fun="function"), "
    SEXP call = PROTECT(lang2(fun, R_NilValue));
    int len = Rf_length(x);
    for (int i = 0; i < len; ++i) {
        SETCADR(call, VECTOR_ELT(x, i));
        if (!LOGICAL(eval(call, R_GlobalEnv))[0]) {
            UNPROTECT(1);
            return Rf_ScalarLogical(FALSE);
        }
    }
    UNPROTECT(1);
    return Rf_ScalarLogical(TRUE);")

我们需要衡量绩效,所以

library(microbenchmark)

最坏的情况似乎是条件通过

n <- 100000
x0 <- x <- vector("list", n)
microbenchmark(all0(x, is.null), all1(x, is.null), all1c(x, is.null),
               allc(x, is.null))
## Unit: milliseconds
##               expr      min       lq   median       uq      max neval
##   all0(x, is.null) 47.48038 50.58960 52.34946 54.10116 61.94736   100
##   all1(x, is.null) 41.52370 44.40024 45.25135 46.68218 53.22317   100
##  all1c(x, is.null) 33.76666 35.03008 35.71738 36.41944 45.37174   100
##   allc(x, is.null) 13.95340 14.43153 14.78244 15.94688 19.41072   100

因此,与编译的R版本相比,C的速度只有C的2倍 - 每个测试都有一个函数调用,因此我们只保留循环本身.最好的情况是当我们立即退出并清楚地显示循环的优点时,但是编译和C代码都没有帮助我们

x[[1]] <- FALSE
microbenchmark(all0(x, is.null), all1(x, is.null), all1c(x, is.null),
               allc(x, is.null))
## Unit: microseconds
##               expr       min         lq     median        uq       max neval
##   all0(x, is.null) 45376.760 45772.5020 46108.5795 46655.005 54242.687   100
##   all1(x, is.null)     1.566     1.9550     2.6335    12.015    14.177   100
##  all1c(x, is.null)     1.367     1.7340     2.0345     9.359    17.438   100
##   allc(x, is.null)     1.229     1.6925     4.6955    11.628    23.378   100

这是一个中间案例,它并没有真正包含任何意外 - C循环比编译的R循环快约2倍,因此可以快速地获得大约2倍.

x <- x0
x[[length(x)/2]] <- FALSE
microbenchmark(all0(x, is.null), all1(x, is.null), all1c(x, is.null),
               allc(x, is.null))
## Unit: milliseconds
##               expr      min       lq    median        uq       max neval
##   all0(x, is.null) 46.85690 49.92969 51.045519 52.653137 59.445611   100
##   all1(x, is.null) 20.90066 21.92357 22.582636 23.077863 25.974395   100
##  all1c(x, is.null) 16.51897 17.44539 17.825551 18.119202 20.535709   100
##   allc(x, is.null)  6.98468  7.18392  7.312575  8.290859  9.460558   100

在C级(VECTOR_ELT(x, i) == R_NilValue)上显式测试NULL 非常快,因此将值与NULL进行比较的C代码比相应的R代码快大约100倍.如果速度至关重要,似乎allNULL可能是值得推广的,但是通用C级的情况似乎并不那么引人注目.当然,C代码不处理NA或错误条件.