[mlpack-git] master: Don't use auxiliary structures; find the best node with O(1) storage. Minor speed improvement. (e0ef801)

[gitdub at big.cc.gt.atl.ga.us]

Repository : https://github.com/mlpack/mlpack

On branch  : master
Link       : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40

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

commit e0ef80103b8197ca67a9883a2476cdaed176580c
Author: Ryan Curtin <ryan at ratml.org>
Date:   Tue Aug 19 01:18:31 2014 +0000

    Don't use auxiliary structures; find the best node with O(1) storage.  Minor
    speed improvement.


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

e0ef80103b8197ca67a9883a2476cdaed176580c
 .../r_tree_descent_heuristic_impl.hpp              | 67 ++++------------------
 1 file changed, 12 insertions(+), 55 deletions(-)

diff --git a/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp b/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
index c8b21e9..38ce3a0 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
@@ -17,11 +17,9 @@ template<typename TreeType>
 inline size_t RTreeDescentHeuristic::ChooseDescentNode(const TreeType* node,
                                                        const arma::vec& point)
 {
-  std::vector<double> scores(node->NumChildren());
-  std::vector<int> vols(node->NumChildren());
   double minScore = DBL_MAX;
   int bestIndex = 0;
-  bool tied = false;
+  double bestVol = 0.0;
 
   for (size_t i = 0; i < node->NumChildren(); i++)
   {
@@ -39,35 +37,16 @@ inline size_t RTreeDescentHeuristic::ChooseDescentNode(const TreeType* node,
 
     assert(v2 - v1 >= 0);
 
-    vols[i] = v1;
-    scores[i] = v2 - v1;
-
-    if (v2 - v1 < minScore)
+    if ((v2 - v1) < minScore)
     {
       minScore = v2 - v1;
+      bestVol = v1;
       bestIndex = i;
     }
-    else if (v2 - v1 == minScore)
-    {
-      tied = true;
-    }
-  }
-
-  if (tied)
-  {
-    // We break ties by choosing the smallest bound.
-    double minVol = DBL_MAX;
-    bestIndex = 0;
-    for (int i = 0; i < scores.size(); i++)
+    else if ((v2 - v1) == minScore && v1 < bestVol)
     {
-      if (scores[i] == minScore)
-      {
-        if (vols[i] < minVol)
-        {
-          minVol = vols[i];
-          bestIndex = i;
-        }
-      }
+      bestVol = v1;
+      bestIndex = i;
     }
   }
 
@@ -79,12 +58,9 @@ inline size_t RTreeDescentHeuristic::ChooseDescentNode(
     const TreeType* node,
     const TreeType* insertedNode)
 {
-  std::vector<double> scores(node->NumChildren());
-  std::vector<int> vols(node->NumChildren());
-
   double minScore = DBL_MAX;
   int bestIndex = 0;
-  bool tied = false;
+  double bestVol = 0.0;
 
   for (size_t i = 0; i < node->NumChildren(); i++)
   {
@@ -105,35 +81,16 @@ inline size_t RTreeDescentHeuristic::ChooseDescentNode(
 
     assert(v2 - v1 >= 0);
 
-    vols[i] = v1;
-    scores[i] = v2 - v1;
-
-    if (v2 - v1 < minScore)
+    if ((v2 - v1) < minScore)
     {
       minScore = v2 - v1;
+      bestVol = v1;
       bestIndex = i;
     }
-    else if (v2 - v1 == minScore)
+    else if ((v2 - v1) == minScore && v1 < bestVol)
     {
-      tied = true;
-    }
-  }
-
-  if (tied)
-  {
-    // We break ties by choosing the smallest bound.
-    double minVol = DBL_MAX;
-    bestIndex = 0;
-    for (int i = 0; i < scores.size(); i++)
-    {
-      if (scores[i] == minScore)
-      {
-        if(vols[i] < minVol)
-        {
-          minVol = vols[i];
-          bestIndex = i;
-        }
-      }
+      bestVol = v1;
+      bestIndex = i;
     }
   }