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

[MarcosPividori]

Hi,
I realized in many parts of the code, we keep track of  the best k candidates visited.
In this situation, it is not necessary to keep a sorted list of the k elements. We only need to know the value of the worst candidate, so we can compare it with new elements and know if we must insert them to this list.
So, instead of maintaining a sorted list, a better approach is to use a priority queue.
When we finish looking for the best k candidates, we can easily get a sorted list from the priority queue, taking the top elements and saving them in reverse order.
If we use a greater value of k, the difference in performance is greater and we have a considerably faster algorithm.
Thanks!
Marcos
You can view, comment on, or merge this pull request online at:

  https://github.com/mlpack/mlpack/pull/732

-- Commit Summary --

  * Use a priority queue (heap) to store the list of candidates while searching.
  * Add more documentation for NeighborSearchRules.
  * Remove unnecesary fill (they will be filled when calling GetResults()).
  * Use a priority queue (heap) to store the list of candidates while searching.
  * Remove unnecesary fill (they will be filled when calling GetResults()).
  * Add more documentation to the RASearchRules class.
  * Detail in the documentation of BaseCase().
  * Use a priority queue (heap) to search for the best valued recommendations.
  * Use a priority queue (heap) to store the list of candidates while searching.
  * Use a priority queue (heap) to store the list of candidates while searching fastmks.
  * Remove unnecessary method from SortPolicies.
  * Add more documentation for FastMKSRules.
  * Add more documentation for RangeSearchRules.

-- File Changes --

    M src/mlpack/methods/cf/cf.cpp (75)
    M src/mlpack/methods/cf/cf.hpp (34)
    M src/mlpack/methods/fastmks/fastmks.hpp (30)
    M src/mlpack/methods/fastmks/fastmks_impl.hpp (107)
    M src/mlpack/methods/fastmks/fastmks_rules.hpp (76)
    M src/mlpack/methods/fastmks/fastmks_rules_impl.hpp (104)
    M src/mlpack/methods/lsh/lsh_search.hpp (48)
    M src/mlpack/methods/lsh/lsh_search_impl.hpp (98)
    M src/mlpack/methods/neighbor_search/CMakeLists.txt (2)
    M src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp (32)
    M src/mlpack/methods/neighbor_search/neighbor_search_rules.hpp (78)
    M src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp (81)
    D src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.cpp (27)
    M src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp (18)
    D src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.cpp (27)
    M src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp (18)
    M src/mlpack/methods/range_search/range_search_rules.hpp (7)
    M src/mlpack/methods/rann/ra_search_impl.hpp (40)
    M src/mlpack/methods/rann/ra_search_rules.hpp (88)
    M src/mlpack/methods/rann/ra_search_rules_impl.hpp (90)
    M src/mlpack/tests/sort_policy_test.cpp (72)

-- Patch Links --

https://github.com/mlpack/mlpack/pull/732.patch
https://github.com/mlpack/mlpack/pull/732.diff

---
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160721/88e09da9/attachment-0001.html>