[issue21592] Make statistics.median run in linear time

[Steven D'Aprano]

Steven D'Aprano added the comment:

On Wed, May 28, 2014 at 02:43:29PM +0000, Thomas Dybdahl Ahle wrote:

> I have written some proof of concept code here [1], I would appreciate 
> you commenting on it, before I turn it into a patch, as I haven't 
> contributed code to Python before.

Thanks Thomas! I will try to look at this over the weekend (today is 
Thursday my time). If I haven't responded by Monday your time, please 
feel free to send me a reminder.

> I have tried to write it as efficiently as possible, but it is of 
> course possible that the c-implemented `sorted()` code will be faster 
> than even the smartest python-implemented select.

My quick-and-dirty tests suggest that you need at least 10 million items 
in the list before a pure Python median-of-median algorithm is as fast 
as the median algorithm based on sorting in C.

> [1]: http://pastebin.com/30x0j39a

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue21592>
_______________________________________