scikit-learn/scikit-learn — pull request #2747 by larsmans (2014-01-13 22:03:53+00:00)
Title: [WIP] faster sorting in trees; random forests almost 2× as fast

Changed the heapsort in the tree learners into a quicksort and gave it cache-friendlier data access. Speeds up RF longer almost two-fold. In fact, profiling with @fabianp's `yep` tool show the time taken by sort to go down from 65% to <10% of total running time in the covertype benchmark.

This is taking longer than I thought but I figured I should at least show @glouppe and @pprett what I've got so far.

TODO:
* more benchmarks, esp. on a denser dataset than covertype (sparse data is easy :)
* clean up code
* decide on the final algorithm: quicksort takes O(n²) time in the worst case, which can be avoided by [introsort](https://en.wikipedia.org/wiki/Introsort) at the expense of more code.