[mlpack-git] master: First pass: line length, bracket surgery (similar to rocket surgery). (c413bcc)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:58:17 EST 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40
>---------------------------------------------------------------
commit c413bcc04a2e42b7f4da265511328932fa023145
Author: Ryan Curtin <ryan at ratml.org>
Date: Sun Aug 17 06:31:45 2014 +0000
First pass: line length, bracket surgery (similar to rocket surgery).
>---------------------------------------------------------------
c413bcc04a2e42b7f4da265511328932fa023145
.../r_star_tree_descent_heuristic.hpp | 18 +--
.../r_star_tree_descent_heuristic_impl.hpp | 121 +++++++++++++++------
2 files changed, 97 insertions(+), 42 deletions(-)
diff --git a/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp b/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp
index 035b85f..8a1db44 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic.hpp
@@ -2,8 +2,8 @@
* @file r_star_tree_descent_heuristic.hpp
* @author Andrew Wells
*
- * Definition of RStarTreeDescentHeuristic, a class that chooses the best child of a node in
- * an R tree when inserting a new point.
+ * Definition of RStarTreeDescentHeuristic, a class that chooses the best child
+ * of a node in an R tree when inserting a new point.
*/
#ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_DESCENT_HEURISTIC_HPP
#define __MLPACK_CORE_TREE_RECTANGLE_TREE_R_STAR_TREE_DESCENT_HEURISTIC_HPP
@@ -11,19 +11,22 @@
#include <mlpack/core.hpp>
namespace mlpack {
-namespace tree /** Trees and tree-building procedures. */ {
+namespace tree {
/**
- * When descending a Rectangle tree to insert a point, we need to have a way to choose
- * a child node when the point isn't enclosed by any of them. This heuristic is used to do so.
+ * When descending a Rectangle tree to insert a point, we need to have a way to
+ * choose a child node when the point isn't enclosed by any of them. This
+ * heuristic is used to do so.
*/
class RStarTreeDescentHeuristic
{
public:
/**
* Evaluate the node using a hueristic. The heuristic guarantees two things:
+ *
* 1. If point is contained in (or on) bound, the value returned is zero.
- * 2. If the point is not contained in (or on) bound, the value returned is greater than zero.
+ * 2. If the point is not contained in (or on) bound, the value returned is
+ * greater than zero.
*
* @param bound The bound used for the node that is being evaluated.
* @param point The point that is being inserted.
@@ -32,7 +35,8 @@ class RStarTreeDescentHeuristic
static size_t ChooseDescentNode(const TreeType* node, const arma::vec& point);
template<typename TreeType>
- static size_t ChooseDescentNode(const TreeType* node, const TreeType* insertedNode);
+ static size_t ChooseDescentNode(const TreeType* node,
+ const TreeType* insertedNode);
};
}; // namespace tree
diff --git a/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp b/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp
index 15e5bc5..e7f8bc8 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_star_tree_descent_heuristic_impl.hpp
@@ -14,36 +14,51 @@ namespace mlpack {
namespace tree {
template<typename TreeType>
-inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(const TreeType* node, const arma::vec& point)
+inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(
+ const TreeType* node,
+ const arma::vec& point)
{
bool tiedOne = false;
std::vector<double> originalScores(node->NumChildren());
double origMinScore = DBL_MAX;
- if (node->Children()[0]->IsLeaf()) { // If its children are leaf nodes, use minimum overlap to choose.
+ if (node->Children()[0]->IsLeaf())
+ {
+ // If its children are leaf nodes, use minimum overlap to choose.
double bestIndex = 0;
- for (size_t i = 0; i < node->NumChildren(); i++) {
+ for (size_t i = 0; i < node->NumChildren(); i++)
+ {
double sc = 0;
- for (size_t j = 0; j < node->NumChildren(); j++) {
- if (j != i) {
+ for (size_t j = 0; j < node->NumChildren(); j++)
+ {
+ if (j != i)
+ {
double overlap = 1.0;
double newOverlap = 1.0;
- for (size_t k = 0; k < node->Bound().Dim(); k++) {
- double newHigh = std::max(point[k], node->Children()[i]->Bound()[k].Hi());
- double newLow = std::min(point[k], node->Children()[i]->Bound()[k].Lo());
+ for (size_t k = 0; k < node->Bound().Dim(); k++)
+ {
+ double newHigh = std::max(point[k],
+ node->Children()[i]->Bound()[k].Hi());
+ double newLow = std::min(point[k],
+ node->Children()[i]->Bound()[k].Lo());
overlap *= node->Children()[i]->Bound()[k].Hi() < node->Children()[j]->Bound()[k].Lo() || node->Children()[i]->Bound()[k].Lo() > node->Children()[j]->Bound()[k].Hi() ? 0 : std::min(node->Children()[i]->Bound()[k].Hi(), node->Children()[j]->Bound()[k].Hi()) - std::max(node->Children()[i]->Bound()[k].Lo(), node->Children()[j]->Bound()[k].Lo());
newOverlap *= newHigh < node->Children()[j]->Bound()[k].Lo() || newLow > node->Children()[j]->Bound()[k].Hi() ? 0 : std::min(newHigh, node->Children()[j]->Bound()[k].Hi()) - std::max(newLow, node->Children()[j]->Bound()[k].Lo());
}
sc += newOverlap - overlap;
}
}
+
originalScores[i] = sc;
- if (sc < origMinScore) {
+ if (sc < origMinScore)
+ {
origMinScore = sc;
bestIndex = i;
- } else if (sc == origMinScore)
+ }
+ else if (sc == origMinScore)
+ {
tiedOne = true;
+ }
}
if (!tiedOne)
@@ -52,40 +67,58 @@ inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(const TreeType* node,
// We do this if it is not on the second level or if there was a tie.
std::vector<double> scores(node->NumChildren());
- if(tiedOne) { // If the first heuristic was tied, we need to eliminate garbage values.
- for(size_t i = 0; i < scores.size(); i++)
+ if (tiedOne)
+ {
+ // If the first heuristic was tied, we need to eliminate garbage values.
+ for (size_t i = 0; i < scores.size(); i++)
scores[i] = DBL_MAX;
}
+
std::vector<int> vols(node->NumChildren());
double minScore = DBL_MAX;
int bestIndex = 0;
bool tied = false;
- for (size_t i = 0; i < node->NumChildren(); i++) {
- if (!tiedOne || originalScores[i] == origMinScore) {
+ for (size_t i = 0; i < node->NumChildren(); i++)
+ {
+ if (!tiedOne || originalScores[i] == origMinScore)
+ {
double v1 = 1.0;
double v2 = 1.0;
- for (size_t j = 0; j < node->Bound().Dim(); j++) {
+ for (size_t j = 0; j < node->Bound().Dim(); j++)
+ {
v1 *= node->Children()[i]->Bound()[j].Width();
v2 *= node->Children()[i]->Bound()[j].Contains(point[j]) ? node->Children()[i]->Bound()[j].Width() : (node->Children()[i]->Bound()[j].Hi() < point[j] ? (point[j] - node->Children()[i]->Bound()[j].Lo()) :
- (node->Children()[i]->Bound()[j].Hi() - point[j]));
+ (node->Children()[i]->Bound()[j].Hi() - point[j]));
}
+
assert(v2 - v1 >= 0);
vols[i] = v1;
scores[i] = v2 - v1;
- if (v2 - v1 < minScore) {
+
+ if (v2 - v1 < minScore)
+ {
minScore = v2 - v1;
bestIndex = i;
- } else if (v2 - v1 == minScore)
+ }
+ else if (v2 - v1 == minScore)
+ {
tied = true;
+ }
}
}
- if (tied) { // We break ties by choosing the smallest bound.
+
+ 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) {
+ for (int i = 0; i < scores.size(); i++)
+ {
+ if (scores[i] == minScore)
+ {
+ if (vols[i] < minVol)
+ {
minVol = vols[i];
bestIndex = i;
}
@@ -97,12 +130,16 @@ inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(const TreeType* node,
}
/**
- * We simplify this to the same code as is used in the regular R tree, since the inserted node should always be above
- * the leaf level. If the tree is eventually changed to support rectangles, this could be changed to match the above code;
- * however, the paper's explanation for their algorithm seems to indicate the above is more for points than for rectangles.
+ * We simplify this to the same code as is used in the regular R tree, since the
+ * inserted node should always be above the leaf level. If the tree is
+ * eventually changed to support rectangles, this could be changed to match the
+ * above code; however, the paper's explanation for their algorithm seems to
+ * indicate the above is more for points than for rectangles.
*/
template<typename TreeType>
-inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(const TreeType* node, const TreeType* insertedNode)
+inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(
+ const TreeType* node,
+ const TreeType* insertedNode)
{
std::vector<double> scores(node->NumChildren());
std::vector<int> vols(node->NumChildren());
@@ -110,29 +147,43 @@ inline size_t RStarTreeDescentHeuristic::ChooseDescentNode(const TreeType* node,
int bestIndex = 0;
bool tied = false;
- for (size_t i = 0; i < node->NumChildren(); i++) {
+ for (size_t i = 0; i < node->NumChildren(); i++)
+ {
double v1 = 1.0;
double v2 = 1.0;
- for (size_t j = 0; j < node->Children()[i]->Bound().Dim(); j++) {
+ for (size_t j = 0; j < node->Children()[i]->Bound().Dim(); j++)
+ {
v1 *= node->Children()[i]->Bound()[j].Width();
v2 *= node->Children()[i]->Bound()[j].Contains(insertedNode->Bound()[j]) ? node->Children()[i]->Bound()[j].Width() :
(insertedNode->Bound()[j].Contains(node->Children()[i]->Bound()[j]) ? insertedNode->Bound()[j].Width() : (insertedNode->Bound()[j].Lo() < node->Children()[i]->Bound()[j].Lo() ? (node->Children()[i]->Bound()[j].Hi() - insertedNode->Bound()[j].Lo()) : (insertedNode->Bound()[j].Hi() - node->Children()[i]->Bound()[j].Lo())));
}
+
assert(v2 - v1 >= 0);
vols[i] = v1;
- scores[i] = v2-v1;
- if (v2 - v1 < minScore) {
+ scores[i] = v2 - v1;
+
+ if (v2 - v1 < minScore)
+ {
minScore = v2 - v1;
bestIndex = i;
- } else if(v2 - v1 == minScore)
+ }
+ else if (v2 - v1 == minScore)
+ {
tied = true;
+ }
}
- if(tied) { // We break ties by choosing the smallest bound.
+
+ 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) {
+ for (int i = 0; i < scores.size(); i++)
+ {
+ if (scores[i] == minScore)
+ {
+ if (vols[i] < minVol)
+ {
minVol = vols[i];
bestIndex = i;
}
More information about the mlpack-git
mailing list