[mlpack-git] [mlpack/mlpack] Heaps for mlpack! (#732)

[Ryan Curtin]

Great to hear that it's faster for k=1, too.

It's funny, this is kind of things coming full circle... a very long time ago, the NeighborSearch code (or AllkNN as the class was called) used to use `std::pair<>` to represent candidates:

https://github.com/mlpack/mlpack/blob/43ac2c8a0f165aecb91ef5a5e8f9e0e7e0b3bb55/fastlib/trunk/mlpack/allknn/allknn.h#L375
(it's crazy how different the code was then... I forget how far things have come.  It's fun to browse around that repository and contrast with now)

But it used `std::vector<std::pair<>>` and then used `std::sort()` to sort them and remove the last element, instead of the much more reasonable priority queue.  When I replaced that (back in 2011 sometime) with individual vectors for the neighbors and distances, I achieved an order-of-magnitude speedup or more, especially for large k.  Now we are back to using `std::pair<>` (or similar), but this time with the right data structure---a heap. :)

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/pull/732#issuecomment-234610062
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160722/05cfaef6/attachment.html>