3 ms·
> Quickselect gets us linear performance, but only in the average case. What if we aren’t happy to be average, but instead want to guarantee that our algorithm
by kccqzy 2y ago
> Quickselect gets us linear performance, but only in the average case. What if we aren’t happy to be average, but instead want to guarantee that our algorithm is linear time, no matter what?
I don't agree with the need for this guarantee. Note that the article already says the selection of the pivot is by random. You can simply choose a very good random function to avoid an attacker crafting an input that needs quadratic time. You'll never be unlucky enough for this to be a problem. This is basically the same kind of mindset that leads people into thinking, what if I use SHA256 to hash these two different strings to get the same hash?
- mitthrowaway2 2y agoIt's a very important guarantee for use in real-time signal processing applications.
- forrestthewoods 2y ago> I don't agree with the need for this guarantee. You don’t get to agree with it or not. It depends on the project! Clearly there exist some projects in the world where it’s important. But honestly it doesn’t matter. Because as the article shows with random data that median-of-medians is strictly better than random pivot. So even if you don’t need the requirement there is zero loss to achieve it.
- kccqzy 2y agoThe median-of-median comes at a cost for execution time. Chances are, sorting each five-element chunk is a lot slower than even running a sophisticated random number generator.
- Quekid5 2y agoSlowness (lower throughput) is often the tradeoff for more predictable run time.
- forrestthewoods 2y agoDid you read the article? Median-of-median results in fewer comparisons than random.