[R] Fastest way to find the last index k such that x[k] < y in a sorted vector x?
Timothy H. Keitt
tklistaddr at keittlab.bio.sunysb.edu
Thu Jun 27 20:49:06 CEST 2002
There's also 'which.max()'.
T.
On Thu, 2002-06-27 at 12:47, Thomas Lumley wrote:
> 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"
> >
> > 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.
>
> Yes.
>
> > 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.
>
> You can use uniroot, eg.
> uniroot(function(i) (x[i]>y)-i/N,c(1,length(x)))$root-1
> where N>length(x)
>
> On the other hand, I had to go to vectors of length 10^5 to get any
> reproducible difference between this and
> max(which(x<y))
>
> -thomas
>
> -.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
> 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
> _._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._
-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
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