pdqselect?

[tcbrindle]

I'm using pqdsort in my ranges library (slightly modified to support projections, proxy iterators and constexpr evaluation). I think it's fantastic, and it's proven almost always faster (and never slower) than both libc++ and libstdc++ std::sort() in every benchmark I've tried.

Have you given any thought to writing a companion "pdqselect" algorithm to implement std::nth_element()? As far as I know all the mainstream C++ implementations of nth_element use introselect, but it seems that (in principle at least) this algorithm could benefit from the same optimisations that pdqsort uses relative to introsort.

(A quick Google turned up this Rust crate, but it doesn't seem to be part of the Rust standard library yet.)

[Morwenn]

I remember having tried that at some point when implementing a derivative of QuickXSort without noticing significant benefits compared to the libc++ implementation of std::nth_element. Now it was whipped together super quickly for the tests, but even though nth_element wasn't dominating the complexity of the QuickXSort algorithm, I should have been able to notice a difference. Unfortunately I can't find the benchmarks (which also included Andrei Alexandrescu's own implementation of its QuickselectAdaptive algorithm described in Fast Deterministic Selection) and got rid of the code a few weeks ago.

Now if another try proved to be faster than my old benchmarks it would be welcome.

[orlp]

I've thought about it, but haven't put in the time. It should be a fairly simple modification from pdqsort though. I don't know if it's worth it.

[alexey-milovidov]

We also need something like pdq_partial_sort for https://github.com/yandex/ClickHouse/

[Morwenn]

This project provides a pdqselect implementation and a comparison to other selection algorithms: https://github.com/danlark1/miniselect