[R] Vectorizing closest match

Thomas Lumley tlumley at u.washington.edu
Thu Mar 28 18:04:01 CET 2002

On Thu, 28 Mar 2002, Mike Lonergan wrote:

> Frank,
> Apologies if I'm being very stupid, but I'd guess that reducing the overall
> complexity would help for large datasets. The following is not vectorised,
> but should be linear apart from the order() operations, which are hopefully
> O(nlogn):
<snip actual code>
> It is all based on sorting the data first so that only m+n comparisons are
> needed rather than mn.

Looking at how findInterval is defined it seems that my solution is
roughly O(m logn) if n>>m but roughly O(m+n) if n<=m, so there's not that
much to choose between them in asymptotic complexity.


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