[R] Vectorizing closest match
tlumley at u.washington.edu
Thu Mar 28 18:04:01 CET 2002
On Thu, 28 Mar 2002, Mike Lonergan wrote:
> 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
<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