Czy data.table implementuje podzestawy szybkiego zasięgu oparte na wyszukiwaniu binarnym? Jaka jest ta składnia?

Question

Mam wektor pływaków. Chciałbym wielokrotnie znajdować podzestawy tego wektora w różnych zakresach. Moja aktualna składnia (DT[x > 1.8 & x < 2.9]) wydaje się skanować wektorowo (jest stosunkowo powolna).

Czy istnieje szybsza składnia wykorzystująca wyszukiwanie binarne dla podpozycji zakresu/interwału danych tabel?

Przykład:

set.seed(123L) 
x = runif(1E6) 
DT = data.table(x, key = "x") 

# For foverlaps() 
DT[,xtemp:=x] 
range = data.table(start = 0.04, end = 0.5, key=c("start", "end")) 


microbenchmark::microbenchmark(
    DT[x < 0.5 & x > 0.04], 
    x[x < 0.5 & x > 0.04], 
    foverlaps(DT, range, by.x = c("x", "xtemp")) 
    ) 

Unit: milliseconds 
             expr  min  lq  mean median  uq  max neval 
         DT[x < 0.5 & x > 0.04] 12.65391 16.10852 18.43412 17.23268 17.76868 104.1112 100 
         x[x < 0.5 & x > 0.04] 16.48126 19.63882 21.65813 20.31534 20.95264 113.7965 100 
foverlaps(DT, range, by.x = c("x", "xtemp")) 116.72732 131.93093 145.56821 140.09218 146.33287 226.6069 100 

Answer 1

Najnowsza wersja data.table dodała operatory %between% i %inrange%, które hermetyzują to zachowanie. Wydaje się być nieco wolniejszym niż rozwiązanie oparte na rolkach firmy Psidom, ale obsługuje wszystkie typy (numeryczne/całkowite) zgodnie z oczekiwaniami i jest znacznie bardziej zwięzłe. Zobacz poniżej.

# data.table version 1.10.4 
# R version 3.3.1 (2016-06-21) 

set.seed(123L) 
library(data.table) 
x = runif(1E6) 
DT = data.table(x) 

#Psidom Answer 
psidom <- function() DT[{ind <- DT[.(c(0.04, 0.5)), which=TRUE, roll=TRUE, on=.(x)]; (ind[1]+1):ind[2]}] 

# Unkeyed 
microbenchmark::microbenchmark(
    DT[x <= 0.5 & x >= 0.04], 
    x[x <= 0.5 & x >= 0.04], 
    DT[x %between% c(0.04, 0.5)], 
    DT[x %inrange% c(0.04, 0.5)], 
    DT[.(0.04, 0.5), on = .(x >= V1, x <= V2), .(x.x)] 
) 

# Unit: milliseconds 
#            expr  min   lq  mean median  uq  max neval cld 
#       DT[x <= 0.5 & x >= 0.04] 20.346712 23.983928 34.69493 25.21085 26.73657 281.4747 100 b 
#        x[x <= 0.5 & x >= 0.04] 19.581049 22.935144 31.61551 23.83557 25.99587 145.3632 100 b 
#      DT[x %between% c(0.04, 0.5)] 8.024091 9.293261 12.19035 11.38171 12.75843 116.5132 100 a 
#      DT[x %inrange% c(0.04, 0.5)] 77.108485 79.871207 91.05544 81.83722 84.66684 188.8674 100 c 
# DT[.(0.04, 0.5), on = .(x >= V1, x <= V2), .(x.x)] 189.488658 195.487681 217.55708 198.52696 205.80428 318.1696 100 d 

# Keyed 
setkey(DT,x) 

#Psidom Answer 
psidom <- function() DT[{ind <- DT[.(c(0.04, 0.5)), which=TRUE, roll=TRUE, on=.(x)]; (ind[1]+1):ind[2]}] 

microbenchmark::microbenchmark(
    DT[x <= 0.5 & x >= 0.04], 
    x[x <= 0.5 & x >= 0.04], 
    DT[x %between% c(0.04, 0.5)], 
    DT[x %inrange% c(0.04, 0.5)], 
    DT[.(0.04, 0.5), on = .(x >= V1, x <= V2), .(x.x)], 
    psidom() 
) 

# Unit: milliseconds 
#            expr  min  lq  mean median  uq  max neval cld 
#       DT[x <= 0.5 & x >= 0.04] 14.550788 18.092458 21.012992 18.934781 20.055428 123.1174 100 b 
#        x[x <= 0.5 & x >= 0.04] 19.403718 22.401709 27.296872 23.707688 24.608270 128.9123 100 b 
#      DT[x %between% c(0.04, 0.5)] 5.439340 6.819262 10.789330 9.490118 10.561789 111.6523 100 a 
#      DT[x %inrange% c(0.04, 0.5)] 12.871260 13.894918 21.434823 16.888748 18.128147 123.4275 100 b 
# DT[.(0.04, 0.5), on = .(x >= V1, x <= V2), .(x.x)] 49.277678 53.516350 61.422212 54.499675 55.869354 158.1861 100 c 
#           psidom() 4.615421 5.095880 9.482131 5.325707 8.316817 109.9318 100 a 

Answer 2

podstawie the answer here, to wydaje się być jakaś poprawa. Wartości równe 0,5 będą zawarte w tym przypadku jednak:

bs <- function() DT[{ind <- DT[.(c(0.04, 0.5)), which=TRUE, roll=TRUE]; (ind[1]+1):ind[2]}] 
vs <- function() x[x < 0.5 & x > 0.04] 

x = runif(1E6) 
DT = data.table(x, key = "x") 

microbenchmark::microbenchmark(
    bs(), 
    vs() 
) 

#Unit: milliseconds 
# expr  min  lq  mean median  uq  max neval 
# bs() 3.594993 4.150932 5.002947 4.44695 4.952283 9.750284 100 
# vs() 15.054460 16.217198 18.999877 17.45298 19.554958 113.623699 100 

Jeśli modyfikować vs() się:

vs <- function() x[x <= 0.5 & x > 0.04] 

Wyniki z dwóch metod są takie same:

identical(bs()$x, sort(vs())) 
# [1] TRUE