更有效的策略()或匹配()

Question

我有一个正数和负数的向量

vec<-c(seq(-100,-1), rep(0,20), seq(1,100))

向量大于示例,并采用一组随机值.我必须重复找到载体中的负数的数量......我发现这是非常低效的.

由于我只需要找到负数的数量,并且向量被排序,我只需要知道前0或正数的索引(实际随机向量中可能没有0).

目前我正在使用此代码来查找长度

length(which(vec<0))

但这迫使R遍历整个向量,但由于它已经排序,所以没有必要.

我可以用

match(0, vec)

但我的矢量并不总是0

所以我的问题是,是否有某种match()函数应用条件而不是查找特定值？或者是否有更有效的方法来运行我的which()代码？

谢谢

Answer 1

到目前为止提供的解决方案都意味着创建logical(length(vec))并对此进行全部或部分扫描.如您所知,矢量已排序.我们可以通过二进制搜索来利用它.我开始认为我是超级聪明的并且在C中以更高的速度实现它,但是在调试算法的索引时遇到了麻烦(这是棘手的部分!).所以我在R中写了它:

f3 <- function(x) {
    imin <- 1L
    imax <- length(x)
    while (imax >= imin) {
        imid <- as.integer(imin + (imax - imin) / 2)
        if (x[imid] >= 0)
            imax <- imid - 1L
        else
            imin <- imid + 1L
    }
    imax
}

与其他建议进行比较

f0 <- function(v) length(which(v < 0))
f1 <- function(v) sum(v < 0)
f2 <- function(v) which.min(v < 0) - 1L

为了好玩

library(compiler)
f3.c <- cmpfun(f3)

导致

> vec <- c(seq(-100,-1,length.out=1e6), rep(0,20), seq(1,100,length.out=1e6))
> identical(f0(vec), f1(vec))
[1] TRUE
> identical(f0(vec), f2(vec))
[1] TRUE
> identical(f0(vec), f3(vec))
[1] TRUE
> identical(f0(vec), f3.c(vec))
[1] TRUE
> microbenchmark(f0(vec), f1(vec), f2(vec), f3(vec), f3.c(vec))
Unit: microseconds
      expr       min        lq     median         uq       max neval
   f0(vec) 15274.275 15347.870 15406.1430 15605.8470 19890.903   100
   f1(vec) 15513.807 15575.229 15651.2970 17064.8830 18326.293   100
   f2(vec) 21473.814 21558.989 21679.3210 22733.1710 27435.889   100
   f3(vec)    51.715    56.050    75.4495    78.5295   100.730   100
 f3.c(vec)    11.612    17.147    28.5570    31.3160    49.781   100

可能有一些棘手的边缘情况我错了!搬到C,我做到了

library(inline)
f4 <- cfunction(c(x = "numeric"), "
    int imin = 0, imax = Rf_length(x) - 1, imid;
    while (imax >= imin) {
        imid = imin + (imax - imin) / 2;
        if (REAL(x)[imid] >= 0)
            imax = imid - 1;
        else
            imin = imid + 1;
    }
    return ScalarInteger(imax + 1);
")

同

> identical(f3(vec), f4(vec))
[1] TRUE
> microbenchmark(f3(vec), f3.c(vec), f4(vec))
Unit: nanoseconds
      expr   min      lq  median      uq   max neval
   f3(vec) 52096 53192.0 54918.5 55539.0 69491   100
 f3.c(vec) 10924 12233.5 12869.0 13410.0 20038   100
   f4(vec)   553   796.0   893.5  1004.5  2908   100

findInterval在R-help列表中提出类似问题时出现了.它很慢但很安全,检查vec实际已经排序并处理NA值.如果一个人想要生活在边缘(可能没有比实施f3或f4更糟糕)那么

f5.i <- function(v)
    .Internal(findInterval(v, 0 - .Machine$double.neg.eps, FALSE, FALSE))

几乎和C实现一样快,但可能更强大和矢量化(即,在第二个参数中查找值向量,以便进行类似范围的计算).