find-interval.cpp

// [[Rcpp::plugins(cpp11)]]

#include <Rcpp.h>

using namespace Rcpp;

// [[Rcpp::export]]
IntegerVector findInterval2(const NumericVector& x, const NumericVector& breaks) {
    std::size_t n = x.size();
    IntegerVector out = no_init(n);
    auto breaks_it = breaks.begin(), breaks_end = breaks.end();
    for(std::size_t i = 0; i < n; ++i) {
        auto ubound = std::upper_bound(breaks_it, breaks_end, x[i]);
        out[i] = std::distance(breaks_it, ubound);
    }
    return out;
}

// [[Rcpp::export]]
IntegerVector findInterval3(const NumericVector& x, const NumericVector& breaks) {
    std::size_t x_n = x.size();
    std::size_t b_n = breaks.size();
    IntegerVector out = no_init(x_n);
    for(std::size_t i = 0; i < x_n; ++i) {
        for (std::size_t j = 0, k = b_n - 1; j <= k; ++j, --k) {
            if (x[i] < breaks[j]) {
                out[i] = j;
                break;
            } else if (x[i] >= breaks[k]) {
                out[i] = k + 1;
                break;
            }
        }
    }
    return out;
}

// [[Rcpp::export]]
IntegerVector findInterval4(const NumericVector& x, const NumericVector& breaks) {
    std::size_t x_n = x.size();
    std::size_t b_n = breaks.size();
    IntegerVector out = no_init(x_n);
    for(std::size_t i = 0; i < x_n; ++i) {
        if (x[i] >= breaks[b_n - 1])
            out[i] = b_n;
        else {
            for (std::size_t j = 0; j < b_n; ++j) {
                if (x[i] < breaks[j]) {
                    out[i] = j;
                    break;
                }
            }
        }
    }
    return out;
}

/*** R
x <- runif(1e6,1,10)

identical2 <- function(...) {
    length(unique(list(...))) == 1L
}

library(microbenchmark)

identical2(
    findInterval(x, c(2, 4, 8)),
    findInterval2(x, c(2, 4, 8)),
    findInterval3(x, c(2, 4, 8)),
    findInterval4(x, c(2, 4, 8))
)

microbenchmark(
    findInterval(x, c(2, 4, 8)),
    findInterval2(x, c(2, 4, 8)),
    findInterval3(x, c(2, 4, 8)),
    findInterval4(x, c(2, 4, 8))
)
*/

> x <- runif(1e6,1,10)

> identical2 <- function(...) {
+     length(unique(list(...))) == 1L
+ }

> library(microbenchmark)

> identical2(
+     findInterval(x, c(2, 4, 8)),
+     findInterval2(x, c(2, 4, 8)),
+     findInterval3(x, c(2, 4, 8)),
+     findInterval4(x, c(2, 4 .... [TRUNCATED] 
[1] TRUE

> microbenchmark(
+     findInterval(x, c(2, 4, 8)),
+     findInterval2(x, c(2, 4, 8)),
+     findInterval3(x, c(2, 4, 8)),
+     findInterval4(x, c( .... [TRUNCATED] 
Unit: milliseconds
                         expr       min        lq      mean    median        uq      max neval  cld
  findInterval(x, c(2, 4, 8)) 13.101228 14.301146 14.645107 14.384439 14.658423 18.54847   100    d
 findInterval2(x, c(2, 4, 8)) 10.060454 11.034496 11.397468 11.145611 11.447766 18.23698   100   c 
 findInterval3(x, c(2, 4, 8))  8.129608  9.044007  9.415876  9.141411  9.742189 16.31924   100  b  
 findInterval4(x, c(2, 4, 8))  7.482195  8.547419  8.781005  8.642741  8.788266 12.89239   100 a