查找一系列 `n` TRUE 中第一个 TRUE 的位置

Question

来自 TRUE/FALSE

的矢量

set.seed(1)
x = rnorm(1503501) > 0

我正在寻找一种高性能（快速）方法来获取第一个 n TRUE 系列中第一个 TRUE 的位置。

我正在处理的向量 (x) 恰好包含 1503501 个元素（除了其中一些短得多的元素）。以下是我目前的解决方案。它使用 for 循环，但 for 循环在 R 中非常慢。是否有更好、尤其更快的解决方案？

n = 20

count = 0
solution = -1
for (i in 1:length(x)){
    if (x[i]){
        count = count + 1
        if (count == n){solution = i+1-n; break}
    } else {count = 0}
}
print(solution)
1182796

我正在考虑使用矢量化函数并做类似 y = which(x) 或最终 y = paste(which(x)) 的事情并寻找特定的模式，但我不确定该怎么做。

Answer 1

您可以使用您的矢量并在开头添加一个 FALSE（零）并删除结尾，然后将此增强矢量添加到您的原始矢量（作为 0/1 整数矢量），然后执行相同的操作再次通过在先前增强向量的开头添加一个 FALSE（零）并删除结尾，然后将其添加到您当前的滚动和向量（再次，添加为整数向量）并执行此操作直到您总共添加了 n转移了你的载体的副本。然后你可以做 which(sum_x == n) 其中 sum_x 是和向量并取 which() 返回的最小值，然后减去 n-1 这将让你开始第一个连续出现 n 个 TRUE。如果 n 与向量的长度相比有点小，这将工作得更快。

Answer 2

看看这个成绩单（只使用一个小得多的随机样本）。我认为很明显，很容易编写一个函数来挑选出满足联合条件的第一个位置，并在到该点的长度上使用 cumsum：

> x = rnorm(1500) > 0

> rle(x)
Run Length Encoding
  lengths: int [1:751] 1 1 1 2 1 3 1 2 2 1 ...
  values : logi [1:751] FALSE TRUE FALSE TRUE FALSE TRUE ...
> table( rle(x)$lengths )

  1   2   3   4   5   6   7   8   9 
368 193  94  46  33  10   2   4   1 
> table( rle(x)$lengths , rle(x)$values)

    FALSE TRUE
  1   175  193
  2   100   93
  3    47   47
  4    23   23
  5    21   12
  6     5    5
  7     2    0
  8     3    1
  9     0    1
> which( rle(x)$lengths==8 & rle(x)$values==TRUE)
[1] 542
> which( rle(x)$lengths==7 & rle(x)$values==TRUE)
integer(0)
> which( rle(x)$lengths==6 & rle(x)$values==TRUE)
[1]  12 484 510 720 744

这是我的候选函数：

 tpos <- function(x,pos) { rl <- rle(x); len <- rl$lengths; 
            sum(len[ 1:(which( len == pos & rl$values==TRUE)[1]-1)],1)}
 tpos(x,6)
#[1] 18

请注意，我从第一个索引中减去一个，因此不会添加第一个符合条件运行的 TRUE 的长度，然后将一个加到该总和中，以便第一个这样的 TRUE 的位置会被计算。我猜 n-TRUE 的第一个运行的位置将作为极值分布之一分布（尽管它并不总是单调增加）

>  tpos(x,8)
[1] 1045
> tpos(x,8)
[1] 1045
> tpos(x,9)
[1] 1417
> tpos(x,10)
[1] 4806
> tpos(x,11)
[1] 2845
> tpos(x,12)
Error in 1:(which(len == pos & rl$values == TRUE)[1] - 1) : 
  NA/NaN argument
> set.seed(1)
> x = rnorm(30000) > 0
> tpos(x,12)
[1] 23509

Answer 3

您可以使用 Rcpp:

library(Rcpp)
cppFunction('int fC(LogicalVector x, int n) {
  int xs = x.size();
  int count = 0;
  int solution = -1;
  for (int i = 0; i < xs; ++i) {
    if (x[i]){
      if (++count == n){solution = i+2-n; break;}
    } else {
      count = 0;
    }
  }
  return solution;
}')

这是一项小型基准研究：

f1 <- function(x,n) {
  count = 0
  solution = -1
  for (i in 1:length(x)){
    if (x[i]){
      count = count + 1
      if (count == n){solution = i+1-n; break}
    } else {count = 0}
  }
  solution
}


set.seed(1)
x = rnorm(150350100) > 0
n = 20

print(f1(x,n)==fC(x,n))
# [1] TRUE


library(rbenchmark)
benchmark(f1(x,n),fC(x,n))
#       test replications elapsed relative user.self sys.self user.child sys.child
# 1 f1(x, n)          100  80.038  180.673    63.300   16.686          0         0
# 2 fC(x, n)          100   0.443    1.000     0.442    0.000          0         0

[更新基准]

# Suggested by BondedDust
tpos <- function(x,pos) { rl <- rle(x); len <- rl$lengths; 
                          sum(len[ 1:(which( len == pos & rl$values==TRUE)[1]-1)],1)}

set.seed(1)
x = rnorm(1503501) > 0
n = 20

print(f1(x,n)==fC(x,n))
# [1] TRUE
print(f1(x,n)==tpos(x,n))
# [1] TRUE


benchmark(f1(x,n),fC(x,n),tpos(x,n),replications = 10)
#         test replications elapsed relative user.self sys.self user.child sys.child
# 1   f1(x, n)           10   4.756  110.605     4.735    0.020          0         0
# 2   fC(x, n)           10   0.043    1.000     0.043    0.000          0         0
# 3 tpos(x, n)           10   2.591   60.256     2.376    0.205          0         0

查找一系列 `n` TRUE 中第一个 TRUE 的位置

Finding position of the first TRUE of a series of `n` TRUEs

performance

boolean

r

count