更快的替代`range(which(..))`

Question

设R中的序列为TRUE和FALSE

v = c(F,F,F,F,F,F,T,F,T,T,F,T,T,T,T,T,F,T,F,T,T,F,F,F,T,F,F,F,F,F)

我想获得第一个和最后一个TRUE的位置.实现这一目标的一种方法是

range(which(v)) # 7 25

但是这个解决方案相对较慢,因为它必须检查向量的每个元素以获得每个TRUE的位置然后遍历所有位置,if在每个位置评估两个语句(我认为)以获得最大值和最小值.从头开始搜索第一个TRUE,从头开始搜索第一个TRUE并返回那些位置将更具战略意义.

有更快的替代方案range(which(..))吗？

Answer 1

我能想到的最简单的方法是不涉及搜索整个向量,这将是一个Rcpp解决方案:

library(Rcpp)
cppFunction(
"NumericVector rangeWhich(LogicalVector x) {
  NumericVector ret(2, NumericVector::get_na());
  int n = x.size();
  for (int idx=0; idx < n; ++idx) {
    if (x[idx]) {
      ret[0] = idx+1;  // 1-indexed for R
      break;
    }
  }
  if (R_IsNA(ret[0]))  return ret;  // No true values
  for (int idx=n-1; idx >= 0; --idx) {
    if (x[idx]) {
      ret[1] = idx + 1;  // 1-indexed for R
      break;
    }
  }
  return ret;
}")
rangeWhich(v)
# [1]  7 25

我们可以使用随机条目对相当长的向量(长度为100万)进行基准测试.我们希望通过不搜索整个事物来获得相当大的效率提升which:

set.seed(144)
bigv <- sample(c(F, T), 1000000, replace=T)
library(microbenchmark)
# range_find from @PierreLafortune
range_find <- function(v) {
i <- 1
while(!v[i]) {
  i <- i +1
}
j <- length(v)
while(!v[j]) {
  j <- j-1
}
c(i,j)
}
# shortCircuit from @JoshuaUlrich
shortCircuit <- compiler::cmpfun({
  function(x) {
    first <- 1
    while(TRUE) if(x[first]) break else first <- first+1
    last <- length(x)
    while(TRUE) if(x[last]) break else last <- last-1
    c(first, last)
  }
})
microbenchmark(rangeWhich(bigv), range_find(bigv), shortCircuit(bigv), range(which(bigv)))
# Unit: microseconds
#                expr      min        lq        mean     median         uq       max neval
#    rangeWhich(bigv)    1.476    2.4655     9.45051     9.0640    13.7585    46.286   100
#    range_find(bigv)    1.445    2.2930     8.06993     7.2055    11.8980    26.893   100
#  shortCircuit(bigv)    1.114    1.6920     7.30925     7.0440    10.2210    30.758   100
#  range(which(bigv)) 6821.180 9389.1465 13991.84613 10007.9045 16698.2230 58112.490   100

Rcpp解决方案的速度要快得多(速度提高500倍以上),max(which(v))因为它不需要遍历整个矢量which.对于此示例,它与range_find@PierreLafortune和shortCircuit@JoshuaUlrich 具有几乎相同的运行时(实际上稍慢).

使用约书亚的一些最坏情况行为的优秀例子,其中真值是在向量的中间(我正在重复他对所有提议函数的实验,所以我们可以看到整个图片),我们看到一个非常不同的情况:

bigv2 <- rep(FALSE, 1e6)
bigv2[5e5-1] <- TRUE
bigv2[5e5+1] <- TRUE
microbenchmark(rangeWhich(bigv2), range_find(bigv2), shortCircuit(bigv2), range(which(bigv2)))
# Unit: microseconds
#                 expr        min          lq        mean      median         uq        max neval
#    rangeWhich(bigv2)    546.206    555.3820    593.1385    575.3790    599.055    979.924   100
#    range_find(bigv2) 400057.083 406449.0075 434515.1142 411881.4145 427487.041 697529.163   100
#  shortCircuit(bigv2)  74942.612  75663.7835  79095.3795  76761.5325  79703.265 125054.360   100
#  range(which(bigv2))    632.086    679.0955    761.9610    700.1365    746.509   3924.941   100

对于这个向量,循环基R解决方案比原始解决方案慢得多(慢100-600倍),并且Rcpp解决方案几乎不快range(which(bigv2))(这是有意义的,因为它们都在整个向量中循环一次).

像往常一样,这需要一个免责声明 - 你需要编译你的Rcpp函数,这也需要时间,所以这只有一个好处,如果你有非常大的向量或多次重复此操作.从您对问题的评论来看,您确实拥有大量的大型向量,因此这对您来说可能是一个不错的选择.

Answer 2

match 当它找到搜索的值时停止很快:

c(match(T,v),length(v)-match(T,rev(v))+1)
[1]  7 25

但你必须测试速度.

更新:

range_find <- function(v) {
i <- 1
j <- length(v)
while(!v[i]) {
  i <- i+1
}
while(!v[j]) {
  j <- j-1
}
c(i,j)
}

基准

v <- rep(v, 5e4)
microbenchmark(
  rangeWhich = rangeWhich(v),
  range_find = range_find(v),
  richwhich = {w <- which(v)
               w[c(1L, length(w))]},
  match = c(match(T,v),length(v)-match(T,rev(v))+1)
)
Unit: microseconds
       expr       min         lq        mean    median         uq        max neval
 rangeWhich     1.284     3.2090    16.50914    20.211    26.7875     29.836   100
 range_find     9.945    21.4945    32.02652    26.948    34.1660    144.042   100
  richwhich  2941.756  3022.5975  3243.02081  3130.227  3247.6405   5403.911   100
      match 45696.329 46771.8175 50662.45708 47359.526 48718.6055 131439.661   100

此方法符合您提出的策略:

"从头开始搜索第一个TRUE,从头开始搜索第一个TRUE,然后返回那些位置将会更具战略意义."