[R] Fastest way to find the last index k such that x[k] < y in a sorted vector x?
Göran Broström
gb at stat.umu.se
Thu Jun 27 18:41:09 CEST 2002
On Thu, 27 Jun 2002, Henrik Bengtsson wrote:
> 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"
How about
> k <- max(which(x < y))
Haven't done any benchmarking, though.
Göran
>
> 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
> _._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._
>
--
Göran Broström tel: +46 90 786 5223
professor fax: +46 90 786 6614
Department of Statistics http://www.stat.umu.se/egna/gb/
Umeå University
SE-90187 Umeå, Sweden e-mail: gb at stat.umu.se
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
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