Does data.table support a fast subset of a range based on a binary search? What is this syntax?

Question

I have a vector of floats. I would like to repeatedly find subsets of this vector in different ranges. My current syntax ( DT[x > 1.8 & x < 2.9] ) is displayed in vector mode (it is relatively slow).

Is there a faster syntax using binary search to substitute data.tables parameters based on range / intervals?

Example:

 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

The latest version of data.table has added the %between% and %inrange% that encapsulate this behavior. It seems like this solution based on the Psidom movie is a bit slower, but handles all types (numeric / integer) as expected, and much more concise. See below.

 # 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), .(xx)] ) # 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), .(xx)] 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), .(xx)], 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), .(xx)] 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

Based on the answer here , this seems to be a kind of improvement. values ​​of 0.5 will be included in this scenario:

 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 

If we change vs() as follows:

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

The results of the two methods are the same:

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