[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
More information about the NumPy-Tickets
mailing list