[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
 >   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

More information about the NumPy-Tickets mailing list