5 ms·
I'm sure patches would be accepted as there's no reason the implementation of the function has to remain identical over releases.
by schmichael 13y ago
I'm sure patches would be accepted as there's no reason the implementation of the function has to remain identical over releases.
- cschmidt 13y agoI haven't got time at the moment, but I would consider contributing an implementation in the long run, if no one else does by then. It just shouldn't be O(n log(n)) when it doesn't have to be.
- jabagawee 13y agoI've just spent the morning implementing various "faster" median algorithms, and it seems that constant factors, function call overhead (for recursive quickselects), etc make all alternative approaches quite slow. The sort-then-select approach is pretty damn fast, especially since I also think / am pretty sure sorted() is implemented in C... So far I've tried median-of-medians, recursive quickselect, iterative quickselect tracking indices and partitioning in place, and heapq.nlargest. The implementation in Python 3.4.0 is both cleaner/easier to read and faster than anything I can make by an order of magnitude for 10,000 element lists. I'm sure someone else here can do better than me, but (s)he'd have a hard time beating CPython, imo.
- cschmidt 13y agoThat's very interesting. I used a C implementation of quickselect in that past that was way faster than sorting. That said, my data was also larger than 10,000 elements. FWIW, here is some old timing data on a 2008 era Mac: * approx timing on my Mac * n, time in ms * 10, <1 * 100, <1 * 1000, <1 * 10000, <1 * 100000, 30 * 1000000, 230 * 10000000, 2530 * 100000000, 33000 You are probably right that pure python will have trouble competing with a C sort, except for quite large N.
- schmichael 13y agoNot only is sorting a Python list implemented in C, the algorithm was sufficiently impressive to be picked up by Java for non-primitives: http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 The reason it's for non-primitives is because it's optimized for sorting lists where comparison is relatively expensive , such as the dereferencing Python does on every item and Java does for non-primitive items. Thanks for putting the effort in and testing it! Very interesting results.
- pjenvey 13y agoSince this is pure Python performance you might want to give the different algorithms a try on PyPy
- fnbr 13y agoThis might be a stupid question, but would you know where the the source for the statistics module can be found? I would be quite interested in submitting a patch, but I can't seem to find the source.
- naftaliharris 13y agoA few months ago I wrote a C implementation of a lazy "sorted" function, (https://github.com/naftaliharris/lazysort https://github.com/naftaliharris/lazysort). One of the things you can use it for is computing medians, with the same "sort-then-take-the-middle-element" algorithm that the statistics module uses. Internally, however, what will happen is that the lazy data-structure that results from a call to the lazy "sorted" function will find the middle element with quickselect. For lists of size 10M, I got a 7.3x speedup vs using the sorted function, and a 1.6x speedup vs using numpy.median. The sorted function was faster up until lists of size 100, presumably due to lower overhead. (The lazily-sorted list data-structure also keeps track of the pivots resulting from partitions, so that later method calls run faster by exploiting the partially-sorted structure that remains from earlier method calls). Here's a plot of the time to compute the median for these different algorithms, (taken from a paper I wrote that's under review): http://imgur.com/oX1QLnS http://imgur.com/oX1QLnS