Início / coding / Perguntas / 79593117
Accepted
Bogaso
Asked: 2025-04-26 02:20:01 +0800 CST

Método eficiente para estimar a composição do grupo

  • 772

Abaixo está o código para estimar a associação de grupo de cada elemento de um grande vetor

Interval = data.frame(lowerLimit = c(0, c(13.31, 14.1, 14.52, 15.9, 17.88, 20.85, 22.14, 22.6, 23.49, 
24.31, 26.54, 27.29, 32.41, 33.49, 35.08, 38.25, 41.84, 46, 47.35, 
47.85, 48.13, 48.25, 48.8, 50.83, 51.55, 53.22, 54.21, 55.94, 
56.31, 58.09, 58.35, 59.92, 60.78, 64.9, 68.7, 72.79, 77.27, 
78.38, 79.04, 80.61, 85.52, 86.25, 86.63, 88.05, 90.07, 90.25, 
95.13, 96.88, 98.47, 99.77)), upperLimit = c(13.31, 14.1, 14.52, 15.9, 17.88, 20.85, 22.14, 22.6, 23.49, 
24.31, 26.54, 27.29, 32.41, 33.49, 35.08, 38.25, 41.84, 46, 47.35, 
47.85, 48.13, 48.25, 48.8, 50.83, 51.55, 53.22, 54.21, 55.94, 
56.31, 58.09, 58.35, 59.92, 60.78, 64.9, 68.7, 72.79, 77.27, 
78.38, 79.04, 80.61, 85.52, 86.25, 86.63, 88.05, 90.07, 90.25, 
95.13, 96.88, 98.47, 99.77, 100))

set.seed(1)
Num = runif(100000, 0, 100)
sapply(Num, function(i) which(Interval$lowerLimit <= i & Interval$upperLimit > i))

Embora o código acima possa estimar a associação de grupo para cada elemento de Num, gostaria de saber se existe algum método mais eficiente e rápido disponível. Para vetores grandes, este código está demorando muito.

Muito obrigado pela sua sugestão.

4 respostas

  1. Se a eficiência estiver em jogo e Intervalnão for necessariamente contíguo, podemos escrever nossa própria {Rcpp}função:

    library(Rcpp)
library(inline)

findIntervalGroup <- cxxfunction(
  signature(numVec = "numeric", lower = "numeric", upper = "numeric"),
  body = '
    Rcpp::NumericVector numVec_cpp(numVec);
    Rcpp::NumericVector lower_cpp(lower);
    Rcpp::NumericVector upper_cpp(upper);
    int n = numVec_cpp.size();
    int m = lower_cpp.size();
    Rcpp::IntegerVector groups(n);

    for (int i = 0; i < n; ++i) {
      double val = numVec_cpp[i];
      int group = 0;
      for (int j = 0; j < m; ++j) {
        if (val >= lower_cpp[j] && val < upper_cpp[j]) {
          group = j + 1;
          break;
        }
      }
      groups[i] = group;
    }
    return groups;
  ',
  plugin = "Rcpp"
)

    microbenchmark::microbenchmark(
  baseCut = {inter <- cut(Num, c(0, Interval[[2]])); 
              strtoi(labels(inter)[inter])},
  baseBCd = {.bincode(Num, c(0L, Interval[[2L]]))},
  rcppBiS = {find_intervals_rcpp(Num, Interval$upperLimit)},
  rcppFI = {findIntervalGroup(Num, Interval$lowerLimit,Interval$upperLimit)},
  baseFI = {findInterval(Num, c(0, Interval[[2]]))},
  baseSA = {sapply(Num, \(i) which(Interval$lowerLimit <= i & 
                                     Interval$upperLimit > i))},
  
  times = 100, check = 'equal') -> res

res

ggplot2::autoplot(res) +
  ggplot2::theme_bw()

    Unit: milliseconds
    expr      min        lq       mean    median        uq      max neval cld
 baseCut  10.3266  11.01865  12.197729  11.50990  12.14965  27.4334   100   a  
 baseBCd   2.2855   2.40300   2.576206   2.55875   2.69000   3.4296   100   b 
 rcppBiS   2.0098   2.14510   2.274777   2.26160   2.38125   2.7139   100   b 
  rcppFI   2.1290   2.25605   2.395644   2.37650   2.53820   2.8357   100   b 
  baseFI   2.2844   2.40860   2.565380   2.54750   2.69365   3.1281   100   b 
  baseSA 299.1572 372.26620 391.161054 391.48015 408.90770 574.8040   100   c

    • 6

  2. Se você tiver um número maior de intervalos (pense em 100 mil ou mais), você deve (provavelmente) usar a busca binária, já que seus intervalos são contíguos e já estão classificados.

    Rcpp::cppFunction("IntegerVector find_intervals_rcpp(const NumericVector i, const NumericVector upper) {
    // Assumes upper is sorted upper bounds and searches using binary search
    const double* ptr = &upper[0];
    int n = upper.size();
    int m = i.size();
    IntegerVector res(m);
    for (int k = 0; k < m; k++) {
      res[k] = std::upper_bound(ptr, ptr + n, i[k]) - ptr + 1;
      if (res[k] > n) res[k] = NA_INTEGER; // Could be removed
    }
    return res;
}")

    Uso

    find_intervals_rcpp(head(Num, 10), Interval$upperLimit)
# [1] 12 16 30 47  6 45 47 35 34  1
    • 5
  3. Best Answer

    Como seu Intervalcontém intervalos contíguos, você pode usar findInterval.

    grp1 <- findInterval(Num, c(0, Interval[[2]]))
grp2 <- sapply(Num, function(i) which(Interval$lowerLimit <= i & Interval$upperLimit > i))
identical(grp1, grp2)
# [1] TRUE
bench::mark(
  fi = findInterval(Num, c(0, Interval[[2]])),
  sa = sapply(Num, function(i) which(Interval$lowerLimit <= i & Interval$upperLimit > i))
)
# Warning: Some expressions had a GC in every iteration; so filtering is disabled.
# # A tibble: 2 × 13
#   expression      min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result          memory                   time             gc                
#   <bch:expr> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list>          <list>                   <list>           <list>            
# 1 fi           1.62ms    1.7ms    584.       391KB     0      292     0      500ms <int [100,000]> <Rprofmem [2 × 3]>       <bench_tm [292]> <tibble [292 × 3]>
# 2 sa         207.93ms  210.9ms      4.61     101MB     7.69     3     5      650ms <int [100,000]> <Rprofmem [400,215 × 3]> <bench_tm [3]>   <tibble [3 × 3]>

    Parece findIntervalser cerca de 100x mais rápido e com os mesmos resultados.

    • 3

  4. BaseR

    1) cut()

    Para completar, cut()foi mencionado pelo usuário @AkselA em um comentário abaixo da pergunta.

    grp3 = cut(Num, c(0L, Interval[[2L]]))

    > grp1 = findInterval(Num, c(0L, Interval[[2L]])) # r2evans's answer 
> identical(strtoi(labels(grp3)[grp3]), grp1)
[1] TRUE

    É necessária coerção para corresponder à saída grp1. Isso não precisa ser o caso em aplicações reais.

    2) .bincode()

    Um barebone interessante e cut()relacionado é , que deve funcionar aqui e parece ser tão rápido quanto ..bincode()findInterval()

    grp4 = .bincode(Num, c(0L, Interval[[2L]]))

    > identical(grp4, grp1)
[1] TRUE
    • 2

relate perguntas