Hacker News Reader

Comment by cschmidt | Hacker News Reader

It makes me slightly sad that the median routine just sorts the data, and looks at the middle. I was hoping for quickselect, which uses 4N comparisons in the average case.

http://www.ics.uci.edu/~eppstein/161/960125.html

or maybe Blum, Floyd, Pratt, Rivest, and Tarjan if you're being fancy, which is 24N comparisons in the worst case (but more than 4N for the average case).

http://www.ics.uci.edu/~eppstein/161/960130.html

View on HN

There's a comment about that over there: "# FIXME: investigate ways to calculate medians without sorting? Quickselect?"

http://hg.python.org/cpython/file/3.4/Lib/statistics.py (line 296)

I'm sure patches would be accepted as there's no reason the implementation of the function has to remain identical over releases.

A few months ago I wrote a C implementation of a lazy "sorted" function, (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

I 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.

I'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.

Not 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

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.

That'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.

Since this is pure Python performance you might want to give the different algorithms a try on PyPy

This 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.

http://hg.python.org/cpython/file/3.4/Lib/statistics.py

Thanks!

Tangential observation: most implementations of quickselect to find the median I've seen use 6N comparisons in the average case; for an even length list they select the middle values using two independent quickselects. The code to do it in a single quickselect gets hairy quite quickly.

Or maybe Introselect, which does Quickselect, but switches to Median-of-Medians (i.e., BFPRT) if the recursion depth gets too big. It has the average-case performance of Quickselect, but, like M-of-M, requires only O(n) comparisons when given a list of length n.

The whole statistics module seems very minimal to me, I was hoping for it to include distributions and random number generators etc. but it only includes a few very basic functions, and not even the best implementation of them. Hopefully it will expand in future releases, but I don't really see the point of including it with such limited functionality.

I think it intentionally started with things that people would tend to implement slightly incorrectly (rather than reaching for a 3rd party library).

Indeed, AFAIK this is the relevant pep:

http://legacy.python.org/dev/peps/pep-0450/

Note especially the pitfalls highlighted around naive diy solutions (not sure if this is actually taken care of in the module, but I hope so! :-).

People who need distributions and more advanced features probably want numpy anyway, which already has all of that. This just covers the very basics that people might run into while doing 'normal' non-statistical programming.

Reply on news.ycombinator.com