search

mourner / kdbush

A fast static index for 2D points
ISC License
638 stars 69 forks source link

Wikipedia version of the algorithm is slow #27

Closed lain-dono closed 5 years ago

lain-dono commented 5 years ago

https://stackoverflow.com/questions/29592546/floyd-rivest-vs-introselect-algorithm-performance says:

The original Floyd-Rivest paper gives an example implementation of their algorithm (this is the implementation listed on Wikipedia, at the time of writing this). However, this is a simplified version. From my tests, the simplified version is actually pretty slow! If you want a fast implementation, I think you'll need to implement the full algorithm. I recommend reading the paper "On Floyd and Rivest's SELECT algorithm" by Krzysztof C. Kiwiel. He gives a pretty good description of how to implement a fast Floyd-Rivest selection.

I also found a more correct version here: https://softwareengineering.stackexchange.com/questions/284767/kth-selection-routine-floyd-algorithm-489

However, there may also be bugs. At least with FloydWirth_kth, something is wrong.

mourner commented 5 years ago

I don't believe the version here is slow (StackOverflow can often be misleading), but you're welcome to prove me wrong by submitting a pull request with an improved implementation that outperforms the current one.