[Numpy-discussion] numpy.interp running time

Timo Kluck tkluck at infty.nl
Sun Jul 31 20:56:07 EDT 2011


2011/7/30 Eric Firing <efiring at hawaii.edu>

> On 07/29/2011 11:18 AM, Timo Kluck wrote:
>
> The current implementation of numpy.interp(x,xp,fp) comes down to: first
> > calculating all the slopes of the linear interpolant (these are
> > len(xp)-1), then use a binary search to find where x is in xp (running
> > time log(len(xp)). So we obtain a running time of
> >
> > O( len(xp) + len(x)*log(len(xp) )
> >
> > We could improve this to just
> >
> > O( len(x)*log(len(xp) )
> >
> > by not caching the slopes. The point is, of course, that this is
> > slightly slower in the common use case where x is is refinement of xp,
> > and where you will have to compute all the slopes anyway.
>
> Maybe the thing to do is to pre-calculate if len(xp) <= len(x), or some
> such guess as to which method would be more efficient.
>
> What you're suggesting is reasonable. The cutoff at len(xp) <= len(x) can
distinguish between the 'refinement' case and the 'just one value' case.
I'll implement it for a start.

I'm not sure if it is the optimal cutoff in other cases -- or even if it is
possible to define such an optimal cutoff.

I'll try to get some numerical evidence to see what kind of speed
differences we're talking about. I'll post back here when I have more info.

Cheers,
Timo
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20110801/b79fbb31/attachment.html>


More information about the NumPy-Discussion mailing list