4 ms·

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 av

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 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 http://www.ics.uci.edu/~eppstein/161/960130.html

ggchappell 13y ago
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.
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 ago
  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.
  - jabagawee 13y ago
    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.
    - cschmidt 13y ago
      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.
    - schmichael 13y ago
      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 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 ago
      Since this is pure Python performance you might want to give the different algorithms a try on PyPy
- fnbr 13y ago
  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.
  - cschmidt 13y ago
    http://hg.python.org/cpython/file/3.4/Lib/statistics.py http://hg.python.org/cpython/file/3.4/Lib/statistics.py
    - fnbr 13y ago
      Thanks!
- naftaliharris 13y ago
  A 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
ajanuary 13y ago
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.
andlima 13y ago
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 http://hg.python.org/cpython/file/3.4/Lib/statistics.py (line 296)
unfamiliar 13y ago
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.
- maxerickson 13y ago
  I think it intentionally started with things that people would tend to implement slightly incorrectly (rather than reaching for a 3rd party library).
  - e12e 13y ago
    Indeed, AFAIK this is the relevant pep: http://legacy.python.org/dev/peps/pep-0450/ 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! :-).
- dagw 13y ago
  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.

ggchappell 13y ago

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.

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 ago
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.
- jabagawee 13y ago
  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.
  - cschmidt 13y ago
    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.
  - schmichael 13y ago
    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 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 ago
    Since this is pure Python performance you might want to give the different algorithms a try on PyPy
fnbr 13y ago
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.
- cschmidt 13y ago
  http://hg.python.org/cpython/file/3.4/Lib/statistics.py http://hg.python.org/cpython/file/3.4/Lib/statistics.py
  - fnbr 13y ago
    Thanks!
naftaliharris 13y ago
A 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

ajanuary 13y ago

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.

andlima 13y ago

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 http://hg.python.org/cpython/file/3.4/Lib/statistics.py (line 296)

unfamiliar 13y ago

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.

maxerickson 13y ago
I think it intentionally started with things that people would tend to implement slightly incorrectly (rather than reaching for a 3rd party library).
- e12e 13y ago
  Indeed, AFAIK this is the relevant pep: http://legacy.python.org/dev/peps/pep-0450/ 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! :-).
dagw 13y ago
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.