Как эффективно проверить, находится ли вектор чисел в интервале, заданном фреймом данных - PullRequest
Новая
       25

Как эффективно проверить, находится ли вектор чисел в интервале, заданном фреймом данных

0 голосов
/ 30 мая 2019

У меня следующая проблема: у меня есть один вектор n1, который содержит определенные значения (в качестве примера я рандомизировал значения в коде). У меня есть фрейм данных df.int, который содержит один столбец верхних пределов для интервалов и один столбец с определенными значениями (снова это рандомизировано, в действительности значения являются режимами чего-то еще). Я хочу проверить для каждой записи n1, в каком интервале фрейма данных она находится, а затем перезаписать значение n1 значением второго столбца соответствующего интервала.

В общем, мой код должен работать, но как n1 и интервалы довольно длинные, мой скрипт выполняется слишком долго. Поэтому я хочу спросить, как я могу настроить свой код так, чтобы он работал более эффективно.

Вот код: 

set.seed(123)
seq.vec <- c(seq(400,800000,by=200))
n1 <- sample(100:800000, 2000, replace=TRUE)
df.int <- data.frame(matrix( nrow=length(seq.vec), ncol=2))
df.names <- c("Upper.Limit", "Value")
colnames(df.int) <- df.names
df.int$Upper.Limit <- seq.vec
df.int$Value <- sample(100:800000, length(seq.vec), replace=TRUE)
j <- 1
m <- 1
for (k in seq_len(n1)){
  for (i in seq_len(df.int$Upper.Limit)){
    if (j==1) {
      n1[m] <- ifelse(n1<=df.int$Upper.Limit[j],df.int$Value[j],n1[m])
    } else{
      n1[m] <- ifelse(n1<=df.int$Upper.Limit[j] & n1>df.int$Upper.Limit[j-1]
                            ,df.int$Value[j],n1[m])
    }
    j <- j+1
  }
  m <- m+1
}

Спасибо!

Ответы [ 3 ]

0 голосов
/ 30 мая 2019

Функция findInterval имеет хорошую производительность и может выполнять работу.
Посмотрите сначала, как это работает только с первым элементом n1

i <- findInterval(n1[1], c(df.int$Upper.Limit, Inf))
j <- findInterval(n1[1], c(-Inf, df.int$Upper.Limit))

df.int$Upper.Limit[i]
#[1] 189000
n1[1]
#[1] 189041
df.int$Upper.Limit[j]
#[1] 189200

df.int$Upper.Limit[i] < n1[1] & n1[1] <= df.int$Upper.Limit[j]
#[1] TRUE

Теперь решение общего назначения. 

subsInterval <- function(x, DF, colLimits = 1, colValues = 2, lower = TRUE){
  vec <- if(lower) 
    c(DF[[colLimits]], Inf) 
  else 
    c(-Inf, DF[[colLimits]])
  i <- findInterval(x, vec, left.open = TRUE)
  DF[[colValues]][i]
}


system.time(
  n2 <- subsInterval(n1, df.int)
)
#     user    system   elapsed 
#    0.000     0.000     0.001 


system.time(
  n3 <- subsInterval(n1, df.int, lower = FALSE)
)
#     user    system   elapsed 
#        0         0         0
0 голосов
/ 31 мая 2019

Если я правильно понимаю, OP ищет эффективный метод для выбора значения из соответствующего правого закрытого интервала, где заданы верхние пределы.

Для больших наборов данных скользящее соединение может стоить посмотреть: 

library(data.table)
setDT(df.int)[data.table(n1), on = .(Upper.Limit = n1), roll = -Inf]$Value

или, заменив n1 по желанию на OP 

n1 <- setDT(df.int)[data.table(n1), on = .(Upper.Limit = n1), roll = -Inf]$Value

Поскольку ОП требует эффективности, вотбенчмарк с различными размерами проблем, который сравнивает методы, опубликованные до сих пор: 

library(data.table)
bm <- bench::press(
  n_int = 10*c(1e2L, 1e4L, 1e6L),
  n_n1 = 10*c(1e2L, 1e4L, 1e6L),
  {
  seq.vec <- seq(400L, length.out = n_int, by = 200L)
  df.int <- data.frame(Upper.Limit = seq.vec,
                       Value = seq_along(seq.vec))
  set.seed(123)
  n0 <- sample(400:max(seq.vec), n_n1, replace = TRUE)
  # include edge cases
  n0[1:5] <- c(seq.vec[1L] - 1L, seq.vec[1L], seq.vec[2L], 
               max(seq.vec), max(seq.vec) + 1L)
  n1 <- data.table::copy(n0)

    bench::mark(
      rollJoin = {
        setDT(df.int)[data.table(n1), on = .(Upper.Limit = n1), roll = -Inf]$Value
      }
      , findInt = {
        i <- findInterval(n1, df.int$Upper.Limit, left.open = TRUE)
        df.int[["Value"]][i+1]
      }
      , approx = {
      approx(x = df.int$Upper.Limit, 
             y = df.int$Value, 
             xout = n1, 
             method = "constant",  
             f = 1,                
             rule = 2:1             ## extrapolation behavior outside domain
      )$y
    }
    , subsInt = {
      subsInterval <- function(x, DF, colLimits = 1, colValues = 2, lower = TRUE){
        vec <- if(lower)
          c(DF[[colLimits]], Inf)
        else
          c(-Inf, DF[[colLimits]])
        i <- findInterval(x, vec, left.open = TRUE)
        DF[[colValues]][i]
      }
      subsInterval(n1, df.int, lower = FALSE)
    }
    , min_time = 1.5
    , check = TRUE
  )
  }
)

, который возвращает следующие значения времени 

print(bm, n = Inf)

# A tibble: 36 x 15
   expression  n_int   n_n1      min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result memory time  gc   
   <bch:expr>  <dbl>  <dbl> <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list> <list> <lis> <lis>
 1 rollJoin   1.00e3 1.00e3   1.84ms   2.24ms   4.31e+2  144.57KB   1.37     630     2      1.46s <int ~ <Rpro~ <bch~ <tib~
 2 findInt    1.00e3 1.00e3   73.9us   77.2us   1.15e+4   35.44KB   2.31    9998     2   866.63ms <int ~ <Rpro~ <bch~ <tib~
 3 approx     1.00e3 1.00e3  124.9us  129.7us   7.04e+3   63.16KB   2.11    9997     3      1.42s <dbl ~ <Rpro~ <bch~ <tib~
 4 subsInt    1.00e3 1.00e3   71.8us     74us   1.23e+4   23.63KB   1.23    9999     1   813.65ms <int ~ <Rpro~ <bch~ <tib~
 5 rollJoin   1.00e5 1.00e3   3.17ms   3.65ms   2.65e+2  918.01KB   1.35     392     2      1.48s <int ~ <Rpro~ <bch~ <tib~
 6 findInt    1.00e5 1.00e3  455.7us  603.6us   1.58e+3  808.88KB   5.99    2107     8      1.34s <int ~ <Rpro~ <bch~ <tib~
 7 approx     1.00e5 1.00e3   4.26ms   5.28ms   1.88e+2    4.83MB   4.46     253     6      1.35s <dbl ~ <Rpro~ <bch~ <tib~
 8 subsInt    1.00e5 1.00e3    516us  659.4us   1.46e+3  797.07KB   5.94    1960     8      1.35s <int ~ <Rpro~ <bch~ <tib~
 9 rollJoin   1.00e7 1.00e3  80.21ms  83.39ms   1.12e+1   76.43MB   2.64      17     4      1.52s <int ~ <Rpro~ <bch~ <tib~
10 findInt    1.00e7 1.00e3  37.72ms  48.19ms   1.66e+1   76.32MB   7.98      25    12       1.5s <int ~ <Rpro~ <bch~ <tib~
11 approx     1.00e7 1.00e3  931.5ms 934.27ms   1.07e+0  509.49MB   2.14       2     4      1.87s <dbl ~ <Rpro~ <bch~ <tib~
12 subsInt    1.00e7 1.00e3  46.98ms  49.05ms   1.64e+1   76.31MB   4.59      25     7      1.53s <int ~ <Rpro~ <bch~ <tib~
13 rollJoin   1.00e3 1.00e5   9.05ms  10.56ms   9.42e+1    3.16MB   0.683    138     1      1.47s <int ~ <Rpro~ <bch~ <tib~
14 findInt    1.00e3 1.00e5    6.6ms   7.17ms   1.37e+2    2.68MB   0.680    202     1      1.47s <int ~ <Rpro~ <bch~ <tib~
15 approx     1.00e3 1.00e5   6.95ms   7.54ms   1.31e+2    1.57MB   0.682    192     1      1.47s <dbl ~ <Rpro~ <bch~ <tib~
16 subsInt    1.00e3 1.00e5   5.78ms   6.35ms   1.56e+2    1.53MB   0.681    229     1      1.47s <int ~ <Rpro~ <bch~ <tib~
17 rollJoin   1.00e5 1.00e5  13.24ms  14.34ms   6.93e+1    3.92MB   0.686    101     1      1.46s <int ~ <Rpro~ <bch~ <tib~
18 findInt    1.00e5 1.00e5  20.74ms  22.21ms   4.48e+1    3.43MB   0         68     0      1.52s <int ~ <Rpro~ <bch~ <tib~
19 approx     1.00e5 1.00e5  17.69ms   19.4ms   5.14e+1    6.34MB   1.41      73     2      1.42s <dbl ~ <Rpro~ <bch~ <tib~
20 subsInt    1.00e5 1.00e5  20.17ms  21.29ms   4.39e+1    2.29MB   0         66     0       1.5s <int ~ <Rpro~ <bch~ <tib~
21 rollJoin   1.00e7 1.00e5   98.3ms  104.8ms   9.02e+0   79.45MB   1.29      14     2      1.55s <int ~ <Rpro~ <bch~ <tib~
22 findInt    1.00e7 1.00e5 202.72ms 204.44ms   4.47e+0   78.97MB   1.28       7     2      1.57s <int ~ <Rpro~ <bch~ <tib~
23 approx     1.00e7 1.00e5    1.11s    1.14s   8.76e-1     511MB   2.19       2     5      2.28s <dbl ~ <Rpro~ <bch~ <tib~
24 subsInt    1.00e7 1.00e5 208.82ms 211.26ms   4.57e+0   77.82MB   0.653      7     1      1.53s <int ~ <Rpro~ <bch~ <tib~
25 rollJoin   1.00e3 1.00e7    1.02s    1.12s   8.93e-1  305.29MB   1.34       2     3      2.24s <int ~ <Rpro~ <bch~ <tib~
26 findInt    1.00e3 1.00e7 797.56ms 807.58ms   1.24e+0  267.04MB   1.86       2     3      1.61s <int ~ <Rpro~ <bch~ <tib~
27 approx     1.00e3 1.00e7 747.18ms 844.75ms   1.18e+0  152.63MB   0.592      2     1      1.69s <dbl ~ <Rpro~ <bch~ <tib~
28 subsInt    1.00e3 1.00e7  639.3ms 642.26ms   1.53e+0   152.6MB   0.510      3     1      1.96s <int ~ <Rpro~ <bch~ <tib~
29 rollJoin   1.00e5 1.00e7    1.68s    1.68s   5.95e-1  306.04MB   1.19       1     2      1.68s <int ~ <Rpro~ <bch~ <tib~
30 findInt    1.00e5 1.00e7    2.34s    2.34s   4.27e-1  267.79MB   0.427      1     1      2.34s <int ~ <Rpro~ <bch~ <tib~
31 approx     1.00e5 1.00e7    1.45s    1.46s   6.86e-1   157.4MB   0.343      2     1      2.92s <dbl ~ <Rpro~ <bch~ <tib~
32 subsInt    1.00e5 1.00e7    2.08s    2.08s   4.81e-1  153.35MB   0          1     0      2.08s <int ~ <Rpro~ <bch~ <tib~
33 rollJoin   1.00e7 1.00e7    1.82s    1.82s   5.49e-1  381.57MB   0.549      1     1      1.82s <int ~ <Rpro~ <bch~ <tib~
34 findInt    1.00e7 1.00e7   18.21s   18.21s   5.49e-2  343.32MB   0.110      1     2     18.21s <int ~ <Rpro~ <bch~ <tib~
35 approx     1.00e7 1.00e7     6.2s     6.2s   1.61e-1  662.06MB   0.323      1     2       6.2s <dbl ~ <Rpro~ <bch~ <tib~
36 subsInt    1.00e7 1.00e7   16.57s   16.57s   6.03e-2  228.88MB   0.0603     1     1     16.57s <int ~ <Rpro~ <bch~ <tib~

library(ggplot2)
autoplot(bm)

enter image description here

Обратите внимание на логарифмическую шкалу времени.

Для задач меньшего размера findInterval() или функция, которая включает findInterval(), кажется наиболее быстрым методом, в то время как дляувеличивающиеся размеры проблем подвижное соединение занимает ведущее место.

При больших размерах проблем распределение памяти (см. таблицу) может стать проблемой, которая также может повлиять на производительность.

0 голосов
/ 30 мая 2019

Вы можете использовать approx с method = "constant" и указать, какие ограничения использовать, установив аргумент f: 

## dummy data
n1 <- runif(10, 0, 100)
df.int <- data.frame(
   upper = seq(1, 100, by = 1), 
   value = runif(100, 0, 100)
)


approx(x = df.int$upper, 
       y = df.int$value, 
       xout = n1, 
       method = "constant",  
       f = 1,                
       rule = 2             ## extrapolation behavior outside domain
)
...