[R] Vectorizing closest match

[Thomas Lumley]

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.

	-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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._