After profiling your code as:
import cProfile, pstats, StringIO
pr = cProfile.Profile()
for it in range(0,10000):
getAlignmentData(source, sequence, sstart, tresholds)
s = StringIO.StringIO()
sortby = 'cumulative'
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
You will get:
First off, you should not be using Python 2 anymore, if at all possible. It will be deprecated next year. The major differences (important for this code) are that xrange is now range and print is a function.
Next, since I am currently on mobile I do not have access to numba. But since you said it does not yield any performance gain anyways, I just removed ...
Just a few quick points on your code:
any future imports should be at the top of any code. Are you using this intentionally (2to3?) or this is leftover code?
your loop to generate test data overrides i in two secondary loops - this is bad coding practice.
you're using xrange, which is pretty much deprecated since Python 2.3. Are you really using Python 2....
There is some overhead to numpy, and even more overhead to pandas. You won't be able to attain the performance of Method1 using pandas.
I'll comment on the methods one at a time:
There is no need to initialize x, y, and z.
You don't deal with the case where a is negative
For me, Method1 is twice as fast when I leave off the @numba decorator.
I have twisted the problem a little and find a way of optimize it at the cost of only get the information of one level of subdivision.
Whith this I mean that the bellow method obtains the same result as the method posted on the question (it assings 1 unique index to all the points that are inside a node) but instead of having a concatenation of the indexes ...
The single most important feature of merge sort is stability: elements comparing equal retain their original order. As coded merge loses stability: shall src_arr[i0] and src_arr[i1] compared equal, src_arr[i1] is copied first. A standard remedy is to compare them backwards; in pseudocode:
if (src_arr[i1] < src_arr[i0])