<p>Hi,<br>
I realized in many parts of the code, we keep track of the best k candidates visited.<br>
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.<br>
So, instead of maintaining a sorted list, a better approach is to use a priority queue.<br>
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.<br>
If we use a greater value of k, the difference in performance is greater and we have a considerably faster algorithm.<br>
Thanks!<br>
Marcos</p>
<hr>
<h4>You can view, comment on, or merge this pull request online at:</h4>
<p> <a href='https://github.com/mlpack/mlpack/pull/732'>https://github.com/mlpack/mlpack/pull/732</a></p>
<h4>Commit Summary</h4>
<ul>
<li>Use a priority queue (heap) to store the list of candidates while searching.</li>
<li>Add more documentation for NeighborSearchRules.</li>
<li>Remove unnecesary fill (they will be filled when calling GetResults()).</li>
<li>Use a priority queue (heap) to store the list of candidates while searching.</li>
<li>Remove unnecesary fill (they will be filled when calling GetResults()).</li>
<li>Add more documentation to the RASearchRules class.</li>
<li>Detail in the documentation of BaseCase().</li>
<li>Use a priority queue (heap) to search for the best valued recommendations.</li>
<li>Use a priority queue (heap) to store the list of candidates while searching.</li>
<li>Use a priority queue (heap) to store the list of candidates while searching fastmks.</li>
<li>Remove unnecessary method from SortPolicies.</li>
<li>Add more documentation for FastMKSRules.</li>
<li>Add more documentation for RangeSearchRules.</li>
</ul>
<h4>File Changes</h4>
<ul>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-0">src/mlpack/methods/cf/cf.cpp</a>
(75)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-1">src/mlpack/methods/cf/cf.hpp</a>
(34)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-2">src/mlpack/methods/fastmks/fastmks.hpp</a>
(30)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-3">src/mlpack/methods/fastmks/fastmks_impl.hpp</a>
(107)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-4">src/mlpack/methods/fastmks/fastmks_rules.hpp</a>
(76)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-5">src/mlpack/methods/fastmks/fastmks_rules_impl.hpp</a>
(104)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-6">src/mlpack/methods/lsh/lsh_search.hpp</a>
(48)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-7">src/mlpack/methods/lsh/lsh_search_impl.hpp</a>
(98)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-8">src/mlpack/methods/neighbor_search/CMakeLists.txt</a>
(2)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-9">src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp</a>
(32)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-10">src/mlpack/methods/neighbor_search/neighbor_search_rules.hpp</a>
(78)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-11">src/mlpack/methods/neighbor_search/neighbor_search_rules_impl.hpp</a>
(81)
</li>
<li>
<strong>D</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-12">src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.cpp</a>
(27)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-13">src/mlpack/methods/neighbor_search/sort_policies/furthest_neighbor_sort.hpp</a>
(18)
</li>
<li>
<strong>D</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-14">src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.cpp</a>
(27)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-15">src/mlpack/methods/neighbor_search/sort_policies/nearest_neighbor_sort.hpp</a>
(18)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-16">src/mlpack/methods/range_search/range_search_rules.hpp</a>
(7)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-17">src/mlpack/methods/rann/ra_search_impl.hpp</a>
(40)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-18">src/mlpack/methods/rann/ra_search_rules.hpp</a>
(88)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-19">src/mlpack/methods/rann/ra_search_rules_impl.hpp</a>
(90)
</li>
<li>
<strong>M</strong>
<a href="https://github.com/mlpack/mlpack/pull/732/files#diff-20">src/mlpack/tests/sort_policy_test.cpp</a>
(72)
</li>
</ul>
<h4>Patch Links:</h4>
<ul>
<li><a href='https://github.com/mlpack/mlpack/pull/732.patch'>https://github.com/mlpack/mlpack/pull/732.patch</a></li>
<li><a href='https://github.com/mlpack/mlpack/pull/732.diff'>https://github.com/mlpack/mlpack/pull/732.diff</a></li>
</ul>
<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">—<br />You are receiving this because you are subscribed to this thread.<br />Reply to this email directly, <a href="https://github.com/mlpack/mlpack/pull/732">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFNnN99uJjl5Omn09N-qKk6MoqMbQks5qYFKngaJpZM4JScnZ">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFC1nADV3MyMO6ZN1-ce1NC_D7Bz3ks5qYFKngaJpZM4JScnZ.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
<div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
<link itemprop="url" href="https://github.com/mlpack/mlpack/pull/732"></link>
<meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>