r - 任何/所有的有效版本

Question

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

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

然而这是低效的，因为它总是检查列表中的每个元素。当第一个 NULL 出现时，更智能的实现将停止检查或非 NULL元素被发现。 IE。相当于:

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 中的速度只有 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 级 all 的情况似乎并不那么引人注目。当然，C 代码不处理 NA 或错误条件。