[R] findInterval(), binary search, log(N) complexity

[Duncan Murdoch]

On 9/22/2008 1:51 PM, Markus Loecher wrote:
> Dear R users,
> the help for findInterval(x,vec) suggests a logarithmic dependence on N
> (=length(vec)), which would imply a binary search type algorithm.
> However, when I "test" this hypothesis, in the following manner:

R is open source.  Why test things this way, when you can look at the 
source?  You don't even need to go to C code for this:

 > findInterval
function (x, vec, rightmost.closed = FALSE, all.inside = FALSE)
{
     if (any(is.na(vec)))
         stop("'vec' contains NAs")
     if (is.unsorted(vec))
         stop("'vec' must be sorted non-decreasingly")
     if (has.na <- any(ix <- is.na(x)))
         x <- x[!ix]
     nx <- length(x)
     index <- integer(nx)
     .C("find_interv_vec", xt = as.double(vec), n = 
as.integer(length(vec)),
         x = as.double(x), nx = as.integer(nx), 
as.logical(rightmost.closed),
         as.logical(all.inside), index, DUP = FALSE, NAOK = TRUE,
         PACKAGE = "base")
     if (has.na) {
         ii <- as.integer(ix)
         ii[ix] <- NA
         ii[!ix] <- index
         ii
     }
     else index
}
<environment: namespace:base>

Notice the "is.unsorted" test.  How could that be anything other than 
linear execution time in N? Similarly for any(ix <- is.na(x)).

If you know the answers to those tests (as you do in your simulation), 
you could presumably get O(log(n)) behaviour by writing a new function 
that skipped them.  But you could take a look at the source code (in 
https://svn.r-project.org/R/trunk/src/appl/interv.c) if you want to 
check, or if you notice any weird timings.

Duncan Murdoch


> 
> set.seed(-3645);
> l <- vector();
> N.seq <- c(5000, 500000, 1000000, 10000000, 50000000);k <- 1
> for (N in N.seq){
>   tmp <- sort(round(stats::rt(N, df=2), 2));
>   l[k] <- system.time(it3 <- findInterval(-1, tmp))[2];k <- k + 1;
> }
> plot(N.seq,l,type="b",xlab="length(vec)", ylab="CPU time");
> 
> the resulting plot suggests a linear relationship.
> I must be missing sth. here ?
> 
> Thanks !
> 
> Markus
> 
> 	[[alternative HTML version deleted]]
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.