Binary Search Tools.

bsearchtools

Binary search tools for R.

The bsearchtools package exposes the binary search based functions of the C++ standard library (std::lower_bound, std::upper_bound) plus other convenience functions, allowing faster lookups on sorted vectors.

It also includes DFI, a lightweight data.frame/matrix wrapper, which automatically creates indexes on the columns for faster lookups.

These functions are especially designed to be used in non-vectorized operations (e.g. inside loops).
For vectorized operations the great data.table package already fullfills basically every R programmer needs.

Installation

The package is available on CRAN : https://cran.r-project.org/package=bsearchtools

Examples :

• Get lower and upper bound indexes :

sortedVec <- c(1,3,3,5,7,12,15,42)

lb(sortedVec,3) # returns 2
ub(sortedVec,3) # returns 4

• Get indexes of elements equal to a value / in a [from,to] range :

sortedVec <- c(1,3,3,5,7,12,15,42)

indexesEqualTo(sortedVec,3) # returns c(2,3)
indexesInRange(sortedVec,5,15) # returns c(4,5,6,7)

• DFI data.frame wrapper

DF <- data.frame(Name=c('John','Jennifer','John','Emily','Peter','Anna','Emily'), 
                 Age=c(30,50,15,27,25,35,70),
                 stringsAsFactors = FALSE)

# create a DFI object from a data.frame (you can also use as.DFI)
DFIobj <- DFI(DF)

# select rows with this filter : 
# (Name == 'John' | Name == 'Emily') & Age >= 25 & Age <= 60
res <- DFI.subset(DFIobj, AND(OR(EQ('Name','John'),EQ('Name','Emily')),RG('Age',25,60)))
# returns :
> res
   Name Age
1  John  30
4 Emily  27

Benchmarks :

• Tested on :

R: 3.2.5 64bit   
OS: Window 10  
CPU: i5 6600K @3.5 Ghz  
RAM: 16 GB

• Get indexes of elements in range [7000,7500] of a random numeric vector of 1e6 elements :

set.seed(123) # for reproducibility
sortedValues <- sort(sample(1:1e4,1e6,replace=TRUE))

# measure time difference doing same operation 500 times
tm1 <- system.time( for(i in 1:500) res1 <- which(sortedValues >= 7000 & sortedValues <= 7500))
tm2 <- system.time( for(i in 1:500) res2 <- indexesInRangeInteger(sortedValues,7000,7500))

> tm1
   user  system elapsed 
  10.87    2.72   13.61 

> tm2
   user  system elapsed 
   0.04    0.00    0.04

• Subset a data.frame with 1e6 rows, performing a range selection on a numeric column :

set.seed(123) # for reproducibility
DF <- data.frame(LT=sample(LETTERS,1e6,replace=TRUE),
                 Values=sample(1:1e4,1e6,replace=TRUE),
                 stringsAsFactors = FALSE)
# we want to index only 'Values' column, by default all columns are indexed
DFIobj <- DFI(DF,indexes.col.names = 'Values') 

# measure time difference doing same operation 500 times
tm1 <- system.time( for(i in 1:500) res1 <- DF[DF$Values >= 4500 & DF$Values <= 5000, 'LT' ] )
tm2 <- system.time( for(i in 1:500) res2 <- DFI.subset(DFIobj,filter=RG('Values',4500,5000),colFilter='LT') )

# and if you're not interested in keeping the original row order : 
tm3 <- system.time( for(i in 1:500) res3 <- DFI.subset(DFIobj,filter=RG('Values',4500,5000),colFilter='LT', 
                                                       sort.indexes = FALSE) )

> tm1
   user  system elapsed 
  14.80    1.84   16.64 
> tm2
   user  system elapsed 
   1.86    0.00    1.86 
> tm3
   user  system elapsed 
   0.29    0.00    0.30

N.B.

If the original vector/data.frame is small, or the size of the filtered result is very similar to original vector/data.frame size, the performance gain of bsearchtools functions will become negligible or possibly worse than base R. So, these functions should be used when appropriate and after testing carefully both the possibilities.

License

GPL (>= 2)

Possible improvements

• Accept a filter like 'A <= 3 & B == 5' etc. (a fast and reliable parser is needed)
• Improve DFI.subset function, in particular on complex filter
• Better NA support ?