|
|
|
|
|
|
by throwaway294531
700 days ago
|
|
|
If you're selecting the n:th element, where n is very small (or large), using median-of-medians may not be the best choice. Instead, you can use a biased pivot as in [1] or something I call "j:th of k:th". Floyd-Rivest can also speed things up. I have a hobby project that gets 1.2-2.0x throughput when compared to a well implemented quickselect, see: https://github.com/koskinev/turboselect If anyone has pointers to fast generic & in-place selection algorithms, I'm interested. [1] https://doi.org/10.4230/LIPIcs.SEA.2017.24 |
|
|