You might want to look at this first: https://github.com/numpy/numpy/issues/1811
Yes it is possible to compute the median faster by doing quickselect instead of quicksort. Best case O(n) for quickselect, O(n log n) for quicksort. But adding selection and partial sorting to NumPy is a bigger issue than just computing medians and percentiles faster. If we are to do this I think we should add partial sorting and selection to npysort, not patch in some C or Cython quickselect just for the median. When npysort has quickselect, changing the Python code to use it for medians and percentiles is a nobrainer. https://github.com/numpy/numpy/tree/master/numpy/core/src/npysort Sturla On 15.01.2013 20:31, Jerome Caron wrote: > Dear all, > I am new to the Numpy-discussion list. > I would like to follow up some possibly useful information about > calculating median. > The message below was posted today on the AstroPy mailing list. > Kind regards > Jerome Caron > #---------------------------------------- > I think the calculation of median values in Numpy is not optimal. I > don't know if there are other libraries that do better? > On my machine I get these results: > >>> data = numpy.random.rand(5000,5000) > >>> t0=time.time();print numpy.ma.median(data);print time.time()-t0 > 0.499845739822 > 15.1949999332 > >>> t0=time.time();print numpy.median(data);print time.time()-t0 > 0.499845739822 > 4.32100009918 > >>> t0=time.time();print aspylib.astro.get_median(data);print > time.time()-t0 > [ 0.49984574] > 0.90499997139 > >>> > The median calculation in Aspylib is using C code from Nicolas Devillard > (can be found here: http://ndevilla.free.fr/median/index.html > <http://ndevilla.free.fr/median/index.html>) interfaced with ctypes. > It could be easily re-used for other, more official packages. I think > the code also finds quantiles efficiently. > See: http://www.aspylib.com/ > > > _______________________________________________ > NumPy-Discussion mailing list > NumPy-Discussion@scipy.org > http://mail.scipy.org/mailman/listinfo/numpy-discussion _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
