[Numpy-discussion] numpy.interp running time

[Eric Firing]

On 07/29/2011 11:18 AM, Timo Kluck wrote:
> Dear numpy developers,
>
> 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.
>
> In my personal use case, however, I needed the value of the
> interp(x0,xp,fp) in order to calculate the next point x1 where I wanted
> to calculate interp(x1,xp,fp). The current implementation gave a severe
> running time penalty.

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.

Eric

>
> I have looked at the source and I could easily produce a patch for this.
> Would you be interested in it?
>
> Cheers,
> Timo Kluck
>
>
>
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion