What's the fastest way to find the closest pair of three-dimensional points in a large set? That was the question posed for the most recent Hacker's Delight challenge.
We just released the results for Hacker's Delight #7: Nearest Neighbor. A little premature, it turns out, we misplaced a bunch of the entries. Once the remaining entries were found, I ran the tests before I came home tonight and Jim should be putting them up soon. It turns out that the missing entries don't really affect the outcome.
This is the third Hacker's Delight challenge I've blogged about. Challenge #6: 64 Choose 4 came from the post Let Me Count The Ways and, in full circle, Let Me Count The Ways (Part II) comes from the challenge. From Hacker's Delight #4: Primes came Sieve of Eratosthenes.
Alistair Milne from EA Montreal blew Nearest Neighbor out of the water with a blazingly fast and beautiful algorithm for finding the nearest two points in a cloud of points in three dimensional space. For comparison the very slow reference implementation is here. I wondered if I could get any more performance out of Alistair's algorithm and came up with an uglier but ~25% faster SIMD optimized version of his algorithm. Sadly, my own reasonably fast implementation for Nearest Neighbor is incorrect about 7% of the time.
My implementation, and many others we received were based on the canonical Nearest Neighbor algorithm as described in Cormen's Introduction to Algorithms. It seems that in every respect, Alistair's algorithm is superior. It's more elegant, it's much faster and it does less work.
Be sure to check it out.
1 comment:
Thank you for great tips. It was simple to read, but I'd like to add that if your software company needs to be updated try software development service.
Post a Comment