search

Bersaelor / KDTree

Swift implementation of a k-dimensional binary space partitioning tree.
MIT License
153 stars 26 forks source link

Implement Hoare's partitioning algorithm to replace Lomuto's algorithm #48

Closed peteraisher closed 4 years ago

peteraisher commented 4 years ago

Implement Hoare's partitioning algorithm to replace Lomuto's algorithm, thereby reducing the expected number of calls to MutableCollection.swapAt(_:_:).

For random unsorted input data, the expected number of swaps is ~ 3x times lower for Hoare's algorithm.

Bersaelor commented 4 years ago

Oh wow, thats really cool @peteraisher !

Can we do some performance analysis with this? If you run the Unit Tests target of the macos example there are already statistics being assembled, we can compare the results?

@hsnetzer already did a similar graph for his PR here: https://github.com/Bersaelor/KDTree/pull/38#issuecomment-425217070

peteraisher commented 4 years ago

Thanks!

Can we do some performance analysis with this?

I tweaked the code in KDTree_OSX_ExampleTests.PerformanceTests testPerformanceExample to build the tree ten times and take the average elapsed time, and got these results:

Performance Comparison Lomuto vs Hoare

n.b. I used identical random data ten times, but the data between runs (i.e. for the two different algorithms) was not the same. I guess a rigorous comparison would have used ten different sets of input data but used identical data for both algorithms. I think the general outcome looks promising though.

Bersaelor commented 4 years ago

Thank you, that looks great!