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

[NumPy Trac]

#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