[R] Fastest way to find the last index k such that x[k] < y in a sorted vector x?
Henrik Bengtsson
hb at maths.lth.se
Thu Jun 27 17:12:17 CEST 2002
Hi, I am trying to find the fastest way to
"find the last index k such that x[k] < y in a *sorted* vector x"
These are my two alternatives:
x <- sort(rnorm(1e4))
y <- 0.2
# Alt 1
k <- max(1, sum(x < y))
# Alt 2 "divide and conquer"
lastIndexLessThan <- function(x, y) {
k0 <- 1; k1 <- length(x)
while ((dk <- (k1 - k0)) > 1) {
k <- k0 + dk %/% 2
if (x[k] < y) k0 <- k else k1 <- k
}
k0
}
k <- lastIndexLessThan(x, y)
Simple benchmarking shows that alternative 1 is faster for short vectors and
alternative 2 is faster for long vectors. I believe this is because alt 1 is
implemented internally. Is there an internal function of alternative 2 that
I don't know about? It would be great because then it would probably be the
fastest one on both short and long vectors.
Best
Henrik Bengtsson
Dept. of Mathematical Statistics @ Centre for Mathematical Sciences
Lund Institute of Technology/Lund University, Sweden (+2h UTC)
Office: P316, +46 46 222 9611 (phone), +46 46 222 4623 (fax)
h b @ m a t h s . l t h . s e, http://www.maths.lth.se/bioinformatics/
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !) To: r-help-request at stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._
More information about the R-help
mailing list