Binary Search Tools

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


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 :
   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 ?

News

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("bsearchtools")

0.0.61 by Marco Giuliano, 2 years ago


https://github.com/digEmAll/bsearchtools


Report a bug at https://github.com/digEmAll/bsearchtools/issues


Browse source code at https://github.com/cran/bsearchtools


Authors: Marco Giuliano


Documentation:   PDF Manual  


GPL (>= 2) license


Imports Rcpp

Linking to Rcpp


See at CRAN