# [NumPy-Tickets] [NumPy] #1920: Improve numpy.interp running time

NumPy Trac numpy-tickets@scipy....
Tue Aug 16 16:57:31 CDT 2011

```#1920: Improve numpy.interp running time
-------------------------------------------------------+--------------------
Reporter:  tkluck                                     |       Owner:  somebody
Type:  enhancement                                |      Status:  new
Priority:  normal                                     |   Milestone:  Unscheduled
Component:  numpy.core                                 |     Version:  1.6.0
Keywords:  patch; linear interpolation; running time  |
-------------------------------------------------------+--------------------

Comment(by tkluck):

Replying to [comment:1 rgommers]:
> I'm not 100% sure I understand the statements on speed.  You have two
cases:
>
>   1. len(xp) <= len(x)
>   2. len(xp) > len(x)
>
> The new code is almost unchanged for case 1, and is "slightly slower".
> For case 2, caching the slopes is removed, resulting in a 10% speed-up.
Correct or not? If so, I'm not sure I'd call that a "severe speed
penalty". Can you provide a snippet used to measure the speed difference?

Thanks for commenting.

The 'severe running time penalty' refers to case 2: pre-calculating the
slopes requires a loop that is executed len(xp) times. When this is large
(as compared to len(x)), there is no need to calculate that many slopes --
it can happen that you calculate 40,000 slopes just to find the
interpolation at a single point x.

So, in terms of asymptotical running time, it is optimal *not* to pre-
calculate any slopes. My first idea, therefore, was to do away with pre-
calculating the slopes entirely. This results in optimal asymptotical
running time.

However, it is probably very common that x is a refinement of xp. In that
case, pre-caching the slopes does make a difference -- effectively, you're
replacing a floating point calculation by a memory lookup. I measured a
10% speed increase (I'll try to find my tests again and post them here).
Therefore, I decided to introduce the branching depending on which case
we're in.

>
> Looking at the tests, only case 1 is tested. So your patch would need
some tests. Also a few more comments in the code about that the if/else is
there for speed reasons etc. would be helpful.
I'm not familiar yet with the test suite. I'll try to look into that and
update my patch accordingly.

--
Ticket URL: <http://projects.scipy.org/numpy/ticket/1920#comment:2>
NumPy <http://projects.scipy.org/numpy>
My example project
```