Comment by jabagawee | Hacker News Reader

Comment by jabagawee | Hacker News Reader

Parent Full thread

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

Reply on news.ycombinator.com