[mlpack-git] master: Use boost::heap::priority_queue instead of push_heap()/pop_heap(). (a79ae63)

[gitdub at mlpack.org]

Repository : https://github.com/mlpack/mlpack
On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/ef51b032f275266f781d42b9bd0aa50aa26a3077...8522b04c3d9a82fb7e964bafd72e70f0cd30bf4b

>---------------------------------------------------------------

commit a79ae634f673051ce6a8d319e5b36f182f23afc1
Author: MarcosPividori <marcos.pividori at gmail.com>
Date:   Tue Jul 26 16:29:19 2016 -0300

    Use boost::heap::priority_queue instead of push_heap()/pop_heap().


>---------------------------------------------------------------

a79ae634f673051ce6a8d319e5b36f182f23afc1
 src/mlpack/methods/fastmks/fastmks_rules.hpp      | 12 ++++---
 src/mlpack/methods/fastmks/fastmks_rules_impl.hpp | 43 +++++++++++------------
 2 files changed, 28 insertions(+), 27 deletions(-)

diff --git a/src/mlpack/methods/fastmks/fastmks_rules.hpp b/src/mlpack/methods/fastmks/fastmks_rules.hpp
index 9aca42d..49071c9 100644
--- a/src/mlpack/methods/fastmks/fastmks_rules.hpp
+++ b/src/mlpack/methods/fastmks/fastmks_rules.hpp
@@ -10,6 +10,7 @@
 #include <mlpack/core.hpp>
 #include <mlpack/core/tree/cover_tree/cover_tree.hpp>
 #include <mlpack/core/tree/traversal_info.hpp>
+#include <boost/heap/priority_queue.hpp>
 #include <vector>
 
 namespace mlpack {
@@ -129,17 +130,18 @@ class FastMKSRules
 
   //! Compare two candidates based on the value.
   struct CandidateCmp {
-    bool operator()(const Candidate& c1, const Candidate& c2)
+    bool operator()(const Candidate& c1, const Candidate& c2) const
     {
       return c1.first > c2.first;
     };
   };
 
   //! Use a min heap to represent the list of candidate points.
-  //! We will use a vector and the std functions: push_heap() pop_heap().
-  //! We can not use a priority queue because we need to iterate over all the
-  //! candidates and std::priority_queue doesn't provide that interface.
-  typedef std::vector<Candidate> CandidateList;
+  //! We will use a boost::heap::priority_queue instead of a std::priority_queue
+  //! because we need to iterate over all the candidates and std::priority_queue
+  //! doesn't provide that interface.
+  typedef boost::heap::priority_queue<Candidate,
+      boost::heap::compare<CandidateCmp>> CandidateList;
 
   //! Set of candidates for each point.
   std::vector<CandidateList> candidates;
diff --git a/src/mlpack/methods/fastmks/fastmks_rules_impl.hpp b/src/mlpack/methods/fastmks/fastmks_rules_impl.hpp
index 6efc9a7..fe6e09b 100644
--- a/src/mlpack/methods/fastmks/fastmks_rules_impl.hpp
+++ b/src/mlpack/methods/fastmks/fastmks_rules_impl.hpp
@@ -52,8 +52,11 @@ FastMKSRules<KernelType, TreeType>::FastMKSRules(
   // BaseCase() method.
   const Candidate def = std::make_pair(-DBL_MAX, size_t() - 1);
 
-  CandidateList cList(k, def);
-  std::vector<CandidateList> tmp(querySet.n_cols, cList);
+  CandidateList pqueue;
+  pqueue.reserve(k);
+  for (size_t i = 0; i < k; i++)
+    pqueue.push(def);
+  std::vector<CandidateList> tmp(querySet.n_cols, pqueue);
   candidates.swap(tmp);
 }
 
@@ -68,15 +71,11 @@ void FastMKSRules<KernelType, TreeType>::GetResults(
   for (size_t i = 0; i < querySet.n_cols; i++)
   {
     CandidateList& pqueue = candidates[i];
-    typedef typename CandidateList::iterator Iterator;
-
-    for (Iterator end = pqueue.end(); end != pqueue.begin(); --end)
-      std::pop_heap(pqueue.begin(), end, CandidateCmp());
-
-    for (size_t j = 0; j < k; j++)
+    for (size_t j = 1; j <= k; j++)
     {
-      indices(j, i) = pqueue[j].second;
-      products(j, i) = pqueue[j].first;
+      indices(k - j, i) = pqueue.top().second;
+      products(k - j, i) = pqueue.top().first;
+      pqueue.pop();
     }
   }
 }
@@ -126,7 +125,7 @@ double FastMKSRules<KernelType, TreeType>::Score(const size_t queryIndex,
                                                  TreeType& referenceNode)
 {
   // Compare with the current best.
-  const double bestKernel = candidates[queryIndex].front().first;
+  const double bestKernel = candidates[queryIndex].top().first;
 
   // See if we can perform a parent-child prune.
   const double furthestDist = referenceNode.FurthestDescendantDistance();
@@ -409,7 +408,7 @@ double FastMKSRules<KernelType, TreeType>::Rescore(const size_t queryIndex,
                                                    TreeType& /*referenceNode*/,
                                                    const double oldScore) const
 {
-  const double bestKernel = candidates[queryIndex].front().first;
+  const double bestKernel = candidates[queryIndex].top().first;
 
   return ((1.0 / oldScore) >= bestKernel) ? oldScore : DBL_MAX;
 }
@@ -457,10 +456,10 @@ double FastMKSRules<KernelType, TreeType>::CalculateBound(TreeType& queryNode)
   {
     const size_t point = queryNode.Point(i);
     const CandidateList& candidatesPoints = candidates[point];
-    if (candidatesPoints.front().first < worstPointKernel)
-      worstPointKernel = candidatesPoints.front().first;
+    if (candidatesPoints.top().first < worstPointKernel)
+      worstPointKernel = candidatesPoints.top().first;
 
-    if (candidatesPoints.front().first == -DBL_MAX)
+    if (candidatesPoints.top().first == -DBL_MAX)
       continue; // Avoid underflow.
 
     // This should be (queryDescendantDistance + centroidDistance) for any tree
@@ -475,10 +474,11 @@ double FastMKSRules<KernelType, TreeType>::CalculateBound(TreeType& queryNode)
     // where p_j^*(p_q) is the j'th kernel candidate for query point p_q and
     // k_j^*(p_q) is K(p_q, p_j^*(p_q)).
     double worstPointCandidateKernel = DBL_MAX;
-    for (size_t j = 0; j < candidatesPoints.size(); ++j)
+    typedef typename CandidateList::const_iterator iter;
+    for (iter it = candidatesPoints.begin(); it != candidatesPoints.end(); ++it)
     {
-      const double candidateKernel = candidatesPoints[j].first -
-          queryDescendantDistance * referenceKernels[candidatesPoints[j].second];
+      const double candidateKernel = it->first - queryDescendantDistance *
+          referenceKernels[it->second];
       if (candidateKernel < worstPointCandidateKernel)
         worstPointCandidateKernel = candidateKernel;
     }
@@ -526,12 +526,11 @@ inline void FastMKSRules<KernelType, TreeType>::InsertNeighbor(
     const double product)
 {
   CandidateList& pqueue = candidates[queryIndex];
-  if (product > pqueue.front().first)
+  if (product > pqueue.top().first)
   {
     Candidate c = std::make_pair(product, index);
-    std::pop_heap(pqueue.begin(), pqueue.end(), CandidateCmp());
-    pqueue.back() = c;
-    std::push_heap(pqueue.begin(), pqueue.end(), CandidateCmp());
+    pqueue.pop();
+    pqueue.push(c);
   }
 }