Início / coding / Perguntas / 79125870
Accepted
noNameTed
Asked: 2024-10-25 21:16:35 +0800 CST

Existe uma maneira mais rápida de encontrar o primeiro valor que não é NA em um vetor grande usando a base R?

  • 772

Assim como a pergunta diz. Existe uma maneira mais rápida de fazer o que é feito abaixo quando o tamanho do vetor é muito grande (> 10M entradas) usando a base R?

O código abaixo funciona, mas quando o tamanho do vetor cresce, ele se torna lento por razões que deveriam ser óbvias. Neste exemplo em particular, um loop for pode ser mais rápido, mas se o primeiro valor NA estiver muito longe do início do vetor, talvez não...

set.seed(1)
x <- c(rep(NA, 3), sample(c(T,F), size=5e7, replace=T))
min(which(!is.na(x))) #4

5 respostas

  1. Best Answer

    Um Rcpploop for deve ser rápido mesmo se o primeiro non- NAvalue não estiver particularmente próximo do início. A ideia básica é que você não precisa continuar iterando depois de ter encontrado o primeiro valor.

    Rcpp::cppFunction("
int which_non_na(LogicalVector x) {
    R_xlen_t n = x.size();
    for (R_xlen_t i = 0; i < n; ++i) {
        if (!LogicalVector::is_na(x[i])) {
            return i + 1; // +1 for 1-indexing in R
        }
    }
    return NA_INTEGER; // if no non-NA values are found
}
")

which_non_na(x) # 4

    Referências

    Aqui estão alguns benchmarks para alguns vetores de comprimento 1e3para 1e8. Para um vetor de comprimento 1.000, isso é cerca de 9 vezes mais rápido do que a abordagem R. Para um vetor de comprimento 100.000.000, é em média mais de um milhão de vezes mais rápido. Adicionei as outras respostas ao benchmark também. which.min()é mais rápido do que min(which()), mas para o maior vetor aqui, isso ainda é cerca de 200.000 vezes mais rápido do que isso.

    bench::press(
    vec_length = 10^(3:8),
    {
        # set probability of NA (so it won't necessarily be early)
        prob_na <- min(0.9, log10(vec_length) / 10)
        probs <- c(prob_na, (1 - prob_na) / 2, (1 - prob_na) / 2)

        set.seed(1)
        x <- sample(c(NA, TRUE, FALSE), size = vec_length, replace = TRUE, prob = probs)

        bench::mark(
            relative = TRUE,
            base_r = min(which(!is.na(x))),
            which_min = which.min(is.na(x)),
            which_1 = which(!is.na(x))[1],
            rcpp = which_non_na(x)
        )
    }
)

    Saída:

       expression vec_length        min     median  `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time
   <bch:expr>      <dbl>      <dbl>      <dbl>      <dbl>     <dbl>    <dbl> <int> <dbl>   <bch:tm>
 1 base_r           1000       7.77       9.04       1          Inf      Inf  9999     1    32.37ms
 2 which_min        1000       1.76       2.14       4.75       Inf      NaN 10000     0     6.82ms
 3 which_1          1000       6.69       7.60       1.34       Inf      NaN 10000     0    24.17ms
 4 rcpp             1000       1          1          9.77       NaN      NaN 10000     0     3.31ms
 5 base_r          10000      71.2      121.         1          Inf      Inf  9998     2   451.83ms
 6 which_min       10000      10.3       10.1       11.1        Inf      NaN 10000     0    40.78ms
 7 which_1         10000      63.6       59.0        1.99       Inf      Inf  9998     2   227.42ms
 8 rcpp            10000       1          1        117.         NaN      NaN 10000     0     3.87ms
 9 base_r         100000    1216.      1030.         1.03       Inf      Inf  1288     2   493.42ms
10 which_min      100000     101.        99.5        7.46       Inf      Inf  8903     4   471.91ms
11 which_1        100000    1159.      1002.         1          Inf      Inf  1252     2   494.89ms
12 rcpp           100000       1          1        980.         NaN      NaN 10000     0     4.03ms
13 base_r        1000000   11177.      9625.         1          Inf      Inf   132     3   483.53ms
14 which_min     1000000     962.       970.         9.26       Inf      Inf  1226     6   485.01ms
15 which_1       1000000   10905.      9247.         1.06       Inf      Inf   142     2   489.28ms
16 rcpp          1000000       1          1       8581.         NaN      NaN 10000     0     4.27ms
17 base_r       10000000  108934.     87149.         1.04       Inf      Inf    12     3   408.38ms
18 which_min    10000000   13676.     17399.         5.78       Inf      Inf    75     5   458.28ms
19 which_1      10000000  105301.     95828.         1          Inf      Inf    13     2   459.48ms
20 rcpp         10000000       1          1      84229.         NaN      NaN 10000     0      4.2ms
21 base_r      100000000 1238681.   1224252.         1          Inf      Inf     2     3   749.38ms
22 which_min   100000000  222405.    224765.         5.39       Inf      Inf     8     4   555.68ms
23 which_1     100000000 1067243.   1053431.         1.16       Inf      Inf     2     4   644.82ms
24 rcpp        100000000       1          1    1116208.         NaN      NaN 10000     0     3.36ms
    • 8

  2. Você pode usar which.minand which.max(sem is.na()), pois como diz o manual:

    Valores ausentes e NaN são descartados.

    set.seed(1)
x <- c(rep(NA, 3), sample(c(T, F), size = 5e7, replace = T))

f1 <- \() min(which(!is.na(x)))
f2 <- \() which.min(is.na(x))
f3 <- \() min(which.min(x), which.max(x), Inf)
microbenchmark(
  f1 = f1(),
  f2 = f2(),
  f3 = f3(),
  unit = "relative",
  check = "equal"
)

    e você verá

    Unit: relative
 expr      min       lq      mean    median        uq       max neval
   f1 931928.5 596652.0 12690.309 31796.371 33326.273 232.24601   100
   f2 139656.2  98002.5  2770.152  5879.894  8057.321  84.39669   100
   f3      1.0      1.0     1.000     1.000     1.000   1.00000   100

    Observação

    Do ponto de vista de benchmarking, parece is.naser um operador caro do ponto de vista da velocidade, especialmente quando o tamanho do array aumenta

    • 6

  3. Cheguei muito atrasado na festa, mas não vi ninguém mencionar Position(), que faz o que você está procurando e interrompe a varredura assim que uma correspondência é encontrada:

    Position(\(x) !is.na(x), x) # 4
    • 3

  4. Um pouco mais rápido do que usar mine basear R

    which(!is.na(x))[1]

    encontra o primeiro valor não-NA entre 100.000.000 de valores em menos de um segundo, mesmo em uma CPU ruim.

    • 1

  5. em um Intel Mac, OS 13.5.2

    Editar: reteste com entrada puramente lógica

     x <- as.logical(c(NA,NA,NA,rep(1,times=20), rep(NA,times=5),rep(1,times=biglen)))
Rgames> microbenchmark(which_non_na(x),nonNA(x))
Unit: nanoseconds
            expr   min      lq     mean  median      uq    max neval
 which_non_na(x)   691   735.0  1192.88   898.0  1342.5  16088   100
        nonNA(x) 45624 46285.5 47195.47 46569.5 46928.5 102274   100

    Não sei como o C++ se sairia se fosse executado em entradas numéricas, mas não declarasse "lógico".

    nonNA <- function(x) {
    for(jn in 1:length(x)) {
        if(!is.na(x[jn])) return( jn)
    }
    return('not found')
}

biglen=1e6
x <- c(NA,NA,NA,rep(1,times=20), rep(NA,times=5),rep(1,times=biglen))

microbenchmark(which_non_na(x),nonNA(x))
Unit: microseconds
            expr      min       lq       mean    median       uq       max neval
 which_non_na(x) 1432.809 1596.131 2398.95178 1606.1205 1615.342 11521.484   100
        nonNA(x)   46.436   47.125   55.06929   47.8625   56.734   111.771   100

biglen=1e8
 x <- c(NA,NA,NA,rep(1,times=20), rep(NA,times=5),rep(1,times=biglen))
microbenchmark(which_non_na(x),nonNA(x))
Unit: microseconds
            expr        min          lq         mean      median         uq        max neval
 which_non_na(x) 322243.196 327702.4310 349913.34584 353146.7080 370955.373 385839.443   100
        nonNA(x)     46.642     48.3305     86.83075    100.3525    115.982    256.817   100
    • 0

relate perguntas