[mlpack-git] mlpack-2.0.x: Replace SortStruct by std::pair (bbf092e)
gitdub at mlpack.org
gitdub at mlpack.org
Wed Jul 20 15:21:18 EDT 2016
Repository : https://github.com/mlpack/mlpack
On branch : mlpack-2.0.x
Link : https://github.com/mlpack/mlpack/compare/e434bc4ac042534529a2a440a44d86935b4d7164...fc4195d27bb9e642356a384d1fa6fe10cbdf89a6
>---------------------------------------------------------------
commit bbf092e4443c6fa8f7607a8e11ad7345af9b8095
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date: Tue Jul 12 15:45:38 2016 +0300
Replace SortStruct by std::pair
(ported changes to HRectBound also)
>---------------------------------------------------------------
bbf092e4443c6fa8f7607a8e11ad7345af9b8095
src/mlpack/core/tree/hrectbound.hpp | 27 +-
src/mlpack/core/tree/hrectbound_impl.hpp | 85 +++++-
.../core/tree/rectangle_tree/r_star_tree_split.hpp | 20 --
.../tree/rectangle_tree/r_star_tree_split_impl.hpp | 269 ++++++++-----------
.../core/tree/rectangle_tree/x_tree_split.hpp | 21 --
.../core/tree/rectangle_tree/x_tree_split_impl.hpp | 297 +++++++++------------
6 files changed, 338 insertions(+), 381 deletions(-)
diff --git a/src/mlpack/core/tree/hrectbound.hpp b/src/mlpack/core/tree/hrectbound.hpp
index cf9f31a..7a0823f 100644
--- a/src/mlpack/core/tree/hrectbound.hpp
+++ b/src/mlpack/core/tree/hrectbound.hpp
@@ -5,13 +5,6 @@
*
* This file describes the interface for the HRectBound class, which implements
* a hyperrectangle bound.
- *
- * This file is part of mlpack 2.0.2.
- *
- * mlpack is free software; you may redistribute it and/or modify it under the
- * terms of the 3-clause BSD license. You should have received a copy of the
- * 3-clause BSD license along with mlpack. If not, see
- * http://www.opensource.org/licenses/BSD-3-Clause for more information.
*/
#ifndef MLPACK_CORE_TREE_HRECTBOUND_HPP
#define MLPACK_CORE_TREE_HRECTBOUND_HPP
@@ -190,6 +183,26 @@ class HRectBound
bool Contains(const VecType& point) const;
/**
+ * Determines if this bound partially contains a bound.
+ */
+ bool Contains(const HRectBound& bound) const;
+
+ /**
+ * Returns the intersection of this bound and another.
+ */
+ HRectBound operator&(const HRectBound& bound) const;
+
+ /**
+ * Intersects this bound with another.
+ */
+ HRectBound& operator&=(const HRectBound& bound);
+
+ /**
+ * Returns the volume of overlap of this bound and another.
+ */
+ ElemType Overlap(const HRectBound& bound) const;
+
+ /**
* Returns the diameter of the hyperrectangle (that is, the longest diagonal).
*/
ElemType Diameter() const;
diff --git a/src/mlpack/core/tree/hrectbound_impl.hpp b/src/mlpack/core/tree/hrectbound_impl.hpp
index 758b621..ccfa026 100644
--- a/src/mlpack/core/tree/hrectbound_impl.hpp
+++ b/src/mlpack/core/tree/hrectbound_impl.hpp
@@ -5,13 +5,6 @@
* Template parameter Power is the metric to use; use 2 for Euclidean (L2).
*
* @experimental
- *
- * This file is part of mlpack 2.0.2.
- *
- * mlpack is free software; you may redistribute it and/or modify it under the
- * terms of the 3-clause BSD license. You should have received a copy of the
- * 3-clause BSD license along with mlpack. If not, see
- * http://www.opensource.org/licenses/BSD-3-Clause for more information.
*/
#ifndef MLPACK_CORE_TREE_HRECTBOUND_IMPL_HPP
#define MLPACK_CORE_TREE_HRECTBOUND_IMPL_HPP
@@ -150,7 +143,12 @@ inline ElemType HRectBound<MetricType, ElemType>::Volume() const
{
ElemType volume = 1.0;
for (size_t i = 0; i < dim; ++i)
+ {
+ if (bounds[i].Lo() >= bounds[i].Hi())
+ return 0;
+
volume *= (bounds[i].Hi() - bounds[i].Lo());
+ }
return volume;
}
@@ -438,6 +436,79 @@ inline bool HRectBound<MetricType, ElemType>::Contains(const VecType& point) con
}
/**
+ * Determines if this bound partially contains a bound.
+ */
+template<typename MetricType, typename ElemType>
+inline bool HRectBound<MetricType, ElemType>::Contains(
+ const HRectBound& bound) const
+{
+ for (size_t i = 0; i < dim; i++)
+ {
+ const math::RangeType<ElemType>& r_a = bounds[i];
+ const math::RangeType<ElemType>& r_b = bound.bounds[i];
+
+ if (r_a.Hi() <= r_b.Lo() || r_a.Lo() >= r_b.Hi()) // If a does not overlap b at all.
+ return false;
+ }
+
+ return true;
+}
+
+/**
+ * Returns the intersection of this bound and another.
+ */
+template<typename MetricType, typename ElemType>
+inline HRectBound<MetricType, ElemType> HRectBound<MetricType, ElemType>::
+operator&(const HRectBound& bound) const
+{
+ HRectBound<MetricType, ElemType> result(dim);
+
+ for (size_t k = 0; k < dim; k++)
+ {
+ result[k].Lo() = std::max(bounds[k].Lo(), bound.bounds[k].Lo());
+ result[k].Hi() = std::min(bounds[k].Hi(), bound.bounds[k].Hi());
+ }
+ return result;
+}
+
+/**
+ * Intersects this bound with another.
+ */
+template<typename MetricType, typename ElemType>
+inline HRectBound<MetricType, ElemType>& HRectBound<MetricType, ElemType>::
+operator&=(const HRectBound& bound)
+{
+ for (size_t k = 0; k < dim; k++)
+ {
+ bounds[k].Lo() = std::max(bounds[k].Lo(), bound.bounds[k].Lo());
+ bounds[k].Hi() = std::min(bounds[k].Hi(), bound.bounds[k].Hi());
+ }
+ return *this;
+}
+
+/**
+ * Returns the volume of overlap of this bound and another.
+ */
+template<typename MetricType, typename ElemType>
+inline ElemType HRectBound<MetricType, ElemType>::Overlap(
+ const HRectBound& bound) const
+{
+ ElemType volume = 1.0;
+
+ for (size_t k = 0; k < dim; k++)
+ {
+ ElemType lo = std::max(bounds[k].Lo(), bound.bounds[k].Lo());
+ ElemType hi = std::min(bounds[k].Hi(), bound.bounds[k].Hi());
+
+ if ( hi <= lo)
+ return 0;
+
+ volume *= hi - lo;
+ }
+ return volume;
+}
+
+/**
* Returns the diameter of the hyperrectangle (that is, the longest diagonal).
*/
template<typename MetricType, typename ElemType>
diff --git a/src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp b/src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp
index 8159943..a91cd87 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_star_tree_split.hpp
@@ -53,26 +53,6 @@ class RStarTreeSplit
private:
/**
- * Class to allow for faster sorting.
- */
- template<typename ElemType>
- struct SortStruct
- {
- ElemType d;
- int n;
- };
-
- /**
- * Comparator for sorting with SortStruct.
- */
- template<typename ElemType>
- static bool StructComp(const SortStruct<ElemType>& s1,
- const SortStruct<ElemType>& s2)
- {
- return s1.d < s2.d;
- }
-
- /**
* Insert a node into another node.
*/
static void InsertNodeIntoTree(TreeType* destTree, TreeType* srcNode);
diff --git a/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp b/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp
index 962aeb5..2f5c008 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_star_tree_split_impl.hpp
@@ -33,6 +33,7 @@ void RStarTreeSplit<TreeType>::SplitLeafNode(TreeType *tree,std::vector<bool>& r
{
// Convenience typedef.
typedef typename TreeType::ElemType ElemType;
+ typedef bound::HRectBound<metric::EuclideanDistance, ElemType> BoundType;
// If we are splitting the root node, we need will do things differently so
// that the constructor and other methods don't confuse the end user by giving
@@ -69,23 +70,29 @@ void RStarTreeSplit<TreeType>::SplitLeafNode(TreeType *tree,std::vector<bool>& r
return;
}
- std::vector<SortStruct<ElemType>> sorted(tree->Count());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->Count());
arma::Col<ElemType> center;
tree->Bound().Center(center); // Modifies centroid.
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Metric().Evaluate(center,
+ sorted[i].first = tree->Metric().Evaluate(center,
tree->LocalDataset().col(i));
- sorted[i].n = i;
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), StructComp<ElemType>);
- std::vector<int> pointIndices(p);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
+ std::vector<size_t> pointIndices(p);
+
for (size_t i = 0; i < p; i++)
{
// We start from the end of sorted.
- pointIndices[i] = tree->Points()[sorted[sorted.size() - 1 - i].n];
- root->DeletePoint(tree->Points()[sorted[sorted.size() - 1 - i].n],
+ pointIndices[i] = tree->Points()[sorted[sorted.size() - 1 - i].second];
+ root->DeletePoint(tree->Points()[sorted[sorted.size() - 1 - i].second],
relevels);
}
@@ -108,14 +115,19 @@ void RStarTreeSplit<TreeType>::SplitLeafNode(TreeType *tree,std::vector<bool>& r
{
ElemType axisScore = 0.0;
// Since we only have points in the leaf nodes, we only need to sort once.
- std::vector<SortStruct<ElemType>> sorted(tree->Count());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->Count());
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->LocalDataset().col(i)[j];
- sorted[i].n = i;
+ sorted[i].first = tree->LocalDataset().col(i)[j];
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), StructComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
// We'll store each of the three scores for each distribution.
std::vector<ElemType> areas(tree->MaxLeafSize() - 2 * tree->MinLeafSize() +
@@ -140,46 +152,21 @@ void RStarTreeSplit<TreeType>::SplitLeafNode(TreeType *tree,std::vector<bool>& r
size_t cutOff = tree->MinLeafSize() + i;
- // We'll calculate the max and min in each dimension by hand to save time.
- std::vector<ElemType> maxG1(tree->Bound().Dim());
- std::vector<ElemType> minG1(maxG1.size());
- std::vector<ElemType> maxG2(maxG1.size());
- std::vector<ElemType> minG2(maxG1.size());
- for (size_t k = 0; k < tree->Bound().Dim(); k++)
- {
- minG1[k] = maxG1[k] = tree->LocalDataset().col(sorted[0].n)[k];
- minG2[k] = maxG2[k] =
- tree->LocalDataset().col(sorted[sorted.size() - 1].n)[k];
+ BoundType bound1(tree->Bound().Dim());
+ BoundType bound2(tree->Bound().Dim());
- for (size_t l = 1; l < tree->Count() - 1; l++)
- {
- if (l < cutOff)
- {
- if (tree->LocalDataset().col(sorted[l].n)[k] < minG1[k])
- minG1[k] = tree->LocalDataset().col(sorted[l].n)[k];
- else if (tree->LocalDataset().col(sorted[l].n)[k] > maxG1[k])
- maxG1[k] = tree->LocalDataset().col(sorted[l].n)[k];
- }
- else
- {
- if (tree->LocalDataset().col(sorted[l].n)[k] < minG2[k])
- minG2[k] = tree->LocalDataset().col(sorted[l].n)[k];
- else if (tree->LocalDataset().col(sorted[l].n)[k] > maxG2[k])
- maxG2[k] = tree->LocalDataset().col(sorted[l].n)[k];
- }
- }
- }
+ for (size_t l = 0; l < cutOff; l++)
+ bound1 |= tree->LocalDataset().col(sorted[l].second);
- ElemType area1 = 1.0, area2 = 1.0;
- ElemType oArea = 1.0;
- for (size_t k = 0; k < maxG1.size(); k++)
- {
- margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
- area1 *= maxG1[k] - minG1[k];
- area2 *= maxG2[k] - minG2[k];
- oArea *= (maxG1[k] < minG2[k] || maxG2[k] < minG1[k]) ? 0.0 :
- (std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]));
- }
+ for (size_t l = cutOff; l < tree->Count(); l++)
+ bound2 |= tree->LocalDataset().col(sorted[l].second);
+
+ ElemType area1 = bound1.Volume();
+ ElemType area2 = bound2.Volume();
+ ElemType oArea = bound1.Overlap(bound2);
+
+ for (size_t k = 0; k < bound1.Dim(); k++)
+ margins[i] += bound1[k].Width() + bound2[k].Width();
areas[i] += area1 + area2;
overlapedAreas[i] += oArea;
@@ -212,14 +199,19 @@ void RStarTreeSplit<TreeType>::SplitLeafNode(TreeType *tree,std::vector<bool>& r
}
}
- std::vector<SortStruct<ElemType>> sorted(tree->Count());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->Count());
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->LocalDataset().col(i)[bestAxis];
- sorted[i].n = i;
+ sorted[i].first = tree->LocalDataset().col(i)[bestAxis];
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), StructComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
TreeType* treeOne = new TreeType(tree->Parent());
TreeType* treeTwo = new TreeType(tree->Parent());
@@ -229,9 +221,9 @@ void RStarTreeSplit<TreeType>::SplitLeafNode(TreeType *tree,std::vector<bool>& r
for (size_t i = 0; i < tree->Count(); i++)
{
if (i < bestAreaIndexOnBestAxis + tree->MinLeafSize())
- treeOne->InsertPoint(tree->Points()[sorted[i].n]);
+ treeOne->InsertPoint(tree->Points()[sorted[i].second]);
else
- treeTwo->InsertPoint(tree->Points()[sorted[i].n]);
+ treeTwo->InsertPoint(tree->Points()[sorted[i].second]);
}
}
else
@@ -239,9 +231,9 @@ void RStarTreeSplit<TreeType>::SplitLeafNode(TreeType *tree,std::vector<bool>& r
for (size_t i = 0; i < tree->Count(); i++)
{
if (i < bestOverlapIndexOnBestAxis + tree->MinLeafSize())
- treeOne->InsertPoint(tree->Points()[sorted[i].n]);
+ treeOne->InsertPoint(tree->Points()[sorted[i].second]);
else
- treeTwo->InsertPoint(tree->Points()[sorted[i].n]);
+ treeTwo->InsertPoint(tree->Points()[sorted[i].second]);
}
}
@@ -281,6 +273,7 @@ bool RStarTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
{
// Convenience typedef.
typedef typename TreeType::ElemType ElemType;
+ typedef bound::HRectBound<metric::EuclideanDistance, ElemType> BoundType;
// If we are splitting the root node, we need will do things differently so
// that the constructor and other methods don't confuse the end user by giving
@@ -372,14 +365,19 @@ bool RStarTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
ElemType axisScore = 0.0;
// We'll do Bound().Lo() now and use Bound().Hi() later.
- std::vector<SortStruct<ElemType>> sorted(tree->NumChildren());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->NumChildren());
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Children()[i]->Bound()[j].Lo();
- sorted[i].n = i;
+ sorted[i].first = tree->Children()[i]->Bound()[j].Lo();
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), StructComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
// We'll store each of the three scores for each distribution.
std::vector<ElemType> areas(tree->MaxNumChildren() -
@@ -404,49 +402,21 @@ bool RStarTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
size_t cutOff = tree->MinNumChildren() + i;
- // We'll calculate the max and min in each dimension by hand to save time.
- std::vector<ElemType> maxG1(tree->Bound().Dim());
- std::vector<ElemType> minG1(maxG1.size());
- std::vector<ElemType> maxG2(maxG1.size());
- std::vector<ElemType> minG2(maxG1.size());
- for (size_t k = 0; k < tree->Bound().Dim(); k++)
- {
- minG1[k] = tree->Children()[sorted[0].n]->Bound()[k].Lo();
- maxG1[k] = tree->Children()[sorted[0].n]->Bound()[k].Hi();
- minG2[k] =
- tree->Children()[sorted[sorted.size() - 1].n]->Bound()[k].Lo();
- maxG2[k] =
- tree->Children()[sorted[sorted.size() - 1].n]->Bound()[k].Hi();
-
- for (size_t l = 1; l < tree->NumChildren() - 1; l++)
- {
- if (l < cutOff)
- {
- if (tree->Children()[sorted[l].n]->Bound()[k].Lo() < minG1[k])
- minG1[k] = tree->Children()[sorted[l].n]->Bound()[k].Lo();
- else if (tree->Children()[sorted[l].n]->Bound()[k].Hi() > maxG1[k])
- maxG1[k] = tree->Children()[sorted[l].n]->Bound()[k].Hi();
- }
- else
- {
- if (tree->Children()[sorted[l].n]->Bound()[k].Lo() < minG2[k])
- minG2[k] = tree->Children()[sorted[l].n]->Bound()[k].Lo();
- else if (tree->Children()[sorted[l].n]->Bound()[k].Hi() > maxG2[k])
- maxG2[k] = tree->Children()[sorted[l].n]->Bound()[k].Hi();
- }
- }
- }
+ BoundType bound1(tree->Bound().Dim());
+ BoundType bound2(tree->Bound().Dim());
- ElemType area1 = 1.0, area2 = 1.0;
- ElemType oArea = 1.0;
- for (size_t k = 0; k < maxG1.size(); k++)
- {
- margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
- area1 *= maxG1[k] - minG1[k];
- area2 *= maxG2[k] - minG2[k];
- oArea *= (maxG1[k] < minG2[k] || maxG2[k] < minG1[k]) ? 0.0 :
- (std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]));
- }
+ for (size_t l = 0; l < cutOff; l++)
+ bound1 |= tree->Child(sorted[l].second).Bound();
+
+ for (size_t l = cutOff; l < tree->NumChildren(); l++)
+ bound2 |= tree->Child(sorted[l].second).Bound();
+
+ ElemType area1 = bound1.Volume();
+ ElemType area2 = bound2.Volume();
+ ElemType oArea = bound1.Overlap(bound2);
+
+ for (size_t k = 0; k < bound1.Dim(); k++)
+ margins[i] += bound1[k].Width() + bound2[k].Width();
areas[i] += area1 + area2;
overlapedAreas[i] += oArea;
@@ -483,15 +453,19 @@ bool RStarTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
{
ElemType axisScore = 0.0;
- // We'll do Bound().Lo() now and use Bound().Hi() later.
- std::vector<SortStruct<ElemType>> sorted(tree->NumChildren());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->NumChildren());
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Children()[i]->Bound()[j].Hi();
- sorted[i].n = i;
+ sorted[i].first = tree->Children()[i]->Bound()[j].Hi();
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), StructComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
// We'll store each of the three scores for each distribution.
std::vector<ElemType> areas(tree->MaxNumChildren() -
@@ -516,51 +490,21 @@ bool RStarTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
size_t cutOff = tree->MinNumChildren() + i;
- // We'll calculate the max and min in each dimension by hand to save time.
- std::vector<ElemType> maxG1(tree->Bound().Dim());
- std::vector<ElemType> minG1(maxG1.size());
- std::vector<ElemType> maxG2(maxG1.size());
- std::vector<ElemType> minG2(maxG1.size());
+ BoundType bound1(tree->Bound().Dim());
+ BoundType bound2(tree->Bound().Dim());
- for (size_t k = 0; k < tree->Bound().Dim(); k++)
- {
- minG1[k] = tree->Children()[sorted[0].n]->Bound()[k].Lo();
- maxG1[k] = tree->Children()[sorted[0].n]->Bound()[k].Hi();
- minG2[k] =
- tree->Children()[sorted[sorted.size() - 1].n]->Bound()[k].Lo();
- maxG2[k] =
- tree->Children()[sorted[sorted.size() - 1].n]->Bound()[k].Hi();
-
- for (size_t l = 1; l < tree->NumChildren() - 1; l++)
- {
- if (l < cutOff)
- {
- if (tree->Children()[sorted[l].n]->Bound()[k].Lo() < minG1[k])
- minG1[k] = tree->Children()[sorted[l].n]->Bound()[k].Lo();
- else if (tree->Children()[sorted[l].n]->Bound()[k].Hi() > maxG1[k])
- maxG1[k] = tree->Children()[sorted[l].n]->Bound()[k].Hi();
- }
- else
- {
- if (tree->Children()[sorted[l].n]->Bound()[k].Lo() < minG2[k])
- minG2[k] = tree->Children()[sorted[l].n]->Bound()[k].Lo();
- else if (tree->Children()[sorted[l].n]->Bound()[k].Hi() > maxG2[k])
- maxG2[k] = tree->Children()[sorted[l].n]->Bound()[k].Hi();
- }
- }
- }
+ for (size_t l = 0; l < cutOff; l++)
+ bound1 |= tree->Child(sorted[l].second).Bound();
- ElemType area1 = 1.0, area2 = 1.0;
- ElemType oArea = 1.0;
+ for (size_t l = cutOff; l < tree->NumChildren(); l++)
+ bound2 |= tree->Child(sorted[l].second).Bound();
- for (size_t k = 0; k < maxG1.size(); k++)
- {
- margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
- area1 *= maxG1[k] - minG1[k];
- area2 *= maxG2[k] - minG2[k];
- oArea *= (maxG1[k] < minG2[k] || maxG2[k] < minG1[k]) ? 0.0 :
- (std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]));
- }
+ ElemType area1 = bound1.Volume();
+ ElemType area2 = bound2.Volume();
+ ElemType oArea = bound1.Overlap(bound2);
+
+ for (size_t k = 0; k < bound1.Dim(); k++)
+ margins[i] += bound1[k].Width() + bound2[k].Width();
areas[i] += area1 + area2;
overlapedAreas[i] += oArea;
@@ -594,25 +538,30 @@ bool RStarTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
}
}
- std::vector<SortStruct<ElemType>> sorted(tree->NumChildren());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->NumChildren());
if (lowIsBest)
{
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Children()[i]->Bound()[bestAxis].Lo();
- sorted[i].n = i;
+ sorted[i].first = tree->Children()[i]->Bound()[bestAxis].Lo();
+ sorted[i].second = i;
}
}
else
{
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Children()[i]->Bound()[bestAxis].Hi();
- sorted[i].n = i;
+ sorted[i].first = tree->Children()[i]->Bound()[bestAxis].Hi();
+ sorted[i].second = i;
}
}
- std::sort(sorted.begin(), sorted.end(), StructComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
TreeType* treeOne = new TreeType(tree->Parent());
TreeType* treeTwo = new TreeType(tree->Parent());
@@ -622,9 +571,9 @@ bool RStarTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
for (size_t i = 0; i < tree->NumChildren(); i++)
{
if (i < bestAreaIndexOnBestAxis + tree->MinNumChildren())
- InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].second]);
else
- InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].second]);
}
}
else
@@ -632,9 +581,9 @@ bool RStarTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
for (size_t i = 0; i < tree->NumChildren(); i++)
{
if (i < bestOverlapIndexOnBestAxis + tree->MinNumChildren())
- InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].second]);
else
- InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].second]);
}
}
diff --git a/src/mlpack/core/tree/rectangle_tree/x_tree_split.hpp b/src/mlpack/core/tree/rectangle_tree/x_tree_split.hpp
index 3028df1..e859b36 100644
--- a/src/mlpack/core/tree/rectangle_tree/x_tree_split.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/x_tree_split.hpp
@@ -91,27 +91,6 @@ class XTreeSplit
SplitHistoryStruct splitHistory;
/**
- * Class to allow for faster sorting.
- */
- template<typename ElemType>
- class sortStruct
- {
- public:
- ElemType d;
- int n;
- };
-
- /**
- * Comparator for sorting with sortStruct.
- */
- template<typename ElemType>
- static bool structComp(const sortStruct<ElemType>& s1,
- const sortStruct<ElemType>& s2)
- {
- return s1.d < s2.d;
- }
-
- /**
* Insert a node into another node.
*/
static void InsertNodeIntoTree(TreeType* destTree, TreeType* srcNode);
diff --git a/src/mlpack/core/tree/rectangle_tree/x_tree_split_impl.hpp b/src/mlpack/core/tree/rectangle_tree/x_tree_split_impl.hpp
index 79b7cc8..2865fc5 100644
--- a/src/mlpack/core/tree/rectangle_tree/x_tree_split_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/x_tree_split_impl.hpp
@@ -59,6 +59,7 @@ void XTreeSplit<TreeType>::SplitLeafNode(TreeType* tree,
{
// Convenience typedef.
typedef typename TreeType::ElemType ElemType;
+ typedef bound::HRectBound<metric::EuclideanDistance, ElemType> BoundType;
// If we are splitting the root node, we need will do things differently so
// that the constructor and other methods don't confuse the end user by giving
@@ -95,23 +96,29 @@ void XTreeSplit<TreeType>::SplitLeafNode(TreeType* tree,
return;
}
- std::vector<sortStruct<ElemType>> sorted(tree->Count());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->Count());
arma::Col<ElemType> center;
tree->Bound().Center(center); // Modifies centroid.
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Metric().Evaluate(center,
+ sorted[i].first = tree->Metric().Evaluate(center,
tree->LocalDataset().col(i));
- sorted[i].n = i;
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), structComp<ElemType>);
- std::vector<int> pointIndices(p);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
+ std::vector<size_t> pointIndices(p);
+
for (size_t i = 0; i < p; i++)
{
// We start from the end of sorted.
- pointIndices[i] = tree->Points()[sorted[sorted.size() - 1 - i].n];
- root->DeletePoint(tree->Points()[sorted[sorted.size() - 1 - i].n],
+ pointIndices[i] = tree->Points()[sorted[sorted.size() - 1 - i].second];
+ root->DeletePoint(tree->Points()[sorted[sorted.size() - 1 - i].second],
relevels);
}
@@ -145,13 +152,18 @@ void XTreeSplit<TreeType>::SplitLeafNode(TreeType* tree,
{
ElemType axisScore = 0.0;
// Since we only have points in the leaf nodes, we only need to sort once.
- std::vector<sortStruct<ElemType>> sorted(tree->Count());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->Count());
for (size_t i = 0; i < sorted.size(); i++) {
- sorted[i].d = tree->LocalDataset().col(i)[j];
- sorted[i].n = i;
+ sorted[i].first = tree->LocalDataset().col(i)[j];
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), structComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
// We'll store each of the three scores for each distribution.
std::vector<ElemType> areas(tree->MaxLeafSize() -
@@ -173,46 +185,23 @@ void XTreeSplit<TreeType>::SplitLeafNode(TreeType* tree,
// another. Then we calculate the three scores for that distribution.
size_t cutOff = tree->MinLeafSize() + i;
- // We'll calculate the max and min in each dimension by hand to save time.
- std::vector<ElemType> maxG1(tree->Bound().Dim());
- std::vector<ElemType> minG1(maxG1.size());
- std::vector<ElemType> maxG2(maxG1.size());
- std::vector<ElemType> minG2(maxG1.size());
- for (size_t k = 0; k < tree->Bound().Dim(); k++)
- {
- minG1[k] = maxG1[k] = tree->LocalDataset().col(sorted[0].n)[k];
- minG2[k] = maxG2[k] = tree->LocalDataset().col(
- sorted[sorted.size() - 1].n)[k];
- for (size_t l = 1; l < tree->Count() - 1; l++)
- {
- if (l < cutOff)
- {
- if (tree->LocalDataset().col(sorted[l].n)[k] < minG1[k])
- minG1[k] = tree->LocalDataset().col(sorted[l].n)[k];
- else if (tree->LocalDataset().col(sorted[l].n)[k] > maxG1[k])
- maxG1[k] = tree->LocalDataset().col(sorted[l].n)[k];
- }
- else
- {
- if (tree->LocalDataset().col(sorted[l].n)[k] < minG2[k])
- minG2[k] = tree->LocalDataset().col(sorted[l].n)[k];
- else if (tree->LocalDataset().col(sorted[l].n)[k] > maxG2[k])
- maxG2[k] = tree->LocalDataset().col(sorted[l].n)[k];
- }
- }
- }
+ BoundType bound1(tree->Bound().Dim());
+ BoundType bound2(tree->Bound().Dim());
+
+ for (size_t l = 0; l < cutOff; l++)
+ bound1 |= tree->LocalDataset().col(sorted[l].second);
+
+ for (size_t l = cutOff; l < tree->Count(); l++)
+ bound2 |= tree->LocalDataset().col(sorted[l].second);
+
+ ElemType area1 = bound1.Volume();
+ ElemType area2 = bound2.Volume();
+ ElemType oArea = bound1.Overlap(bound2);
+
+ for (size_t k = 0; k < bound1.Dim(); k++)
+ margins[i] += bound1[k].Width() + bound2[k].Width();
- ElemType area1 = 1.0, area2 = 1.0;
- ElemType oArea = 1.0;
- for (size_t k = 0; k < maxG1.size(); k++)
- {
- margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
- area1 *= maxG1[k] - minG1[k];
- area2 *= maxG2[k] - minG2[k];
- oArea *= ((maxG1[k] < minG2[k]) || (maxG2[k] < minG1[k])) ? 0.0 :
- std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]);
- }
areas[i] += area1 + area2;
overlapedAreas[i] += oArea;
axisScore += margins[i];
@@ -243,14 +232,19 @@ void XTreeSplit<TreeType>::SplitLeafNode(TreeType* tree,
}
}
- std::vector<sortStruct<ElemType>> sorted(tree->Count());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->Count());
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->LocalDataset().col(i)[bestAxis];
- sorted[i].n = i;
+ sorted[i].first = tree->LocalDataset().col(i)[bestAxis];
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), structComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
TreeType* treeOne = new TreeType(tree->Parent(), NormalNodeMaxNumChildren());
TreeType* treeTwo = new TreeType(tree->Parent(), NormalNodeMaxNumChildren());
@@ -263,9 +257,9 @@ void XTreeSplit<TreeType>::SplitLeafNode(TreeType* tree,
for (size_t i = 0; i < tree->Count(); i++)
{
if (i < bestAreaIndexOnBestAxis + tree->MinLeafSize())
- treeOne->InsertPoint(tree->Points()[sorted[i].n]);
+ treeOne->InsertPoint(tree->Points()[sorted[i].second]);
else
- treeTwo->InsertPoint(tree->Points()[sorted[i].n]);
+ treeTwo->InsertPoint(tree->Points()[sorted[i].second]);
}
}
else
@@ -273,9 +267,9 @@ void XTreeSplit<TreeType>::SplitLeafNode(TreeType* tree,
for (size_t i = 0; i < tree->Count(); i++)
{
if (i < bestOverlapIndexOnBestAxis + tree->MinLeafSize())
- treeOne->InsertPoint(tree->Points()[sorted[i].n]);
+ treeOne->InsertPoint(tree->Points()[sorted[i].second]);
else
- treeTwo->InsertPoint(tree->Points()[sorted[i].n]);
+ treeTwo->InsertPoint(tree->Points()[sorted[i].second]);
}
}
@@ -331,6 +325,7 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
{
// Convenience typedef.
typedef typename TreeType::ElemType ElemType;
+ typedef bound::HRectBound<metric::EuclideanDistance, ElemType> BoundType;
// If we are splitting the root node, we need will do things differently so
// that the constructor and other methods don't confuse the end user by giving
@@ -413,14 +408,19 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
ElemType axisScore = 0.0;
// We'll do Bound().Lo() now and use Bound().Hi() later.
- std::vector<sortStruct<ElemType>> sorted(tree->NumChildren());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->NumChildren());
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Children()[i]->Bound()[j].Lo();
- sorted[i].n = i;
+ sorted[i].first = tree->Children()[i]->Bound()[j].Lo();
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), structComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
// We'll store each of the three scores for each distribution.
std::vector<ElemType> areas(tree->MaxNumChildren() -
@@ -443,48 +443,23 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
// another. Then we calculate the three scores for that distribution.
size_t cutOff = tree->MinNumChildren() + i;
- // We'll calculate the max and min in each dimension by hand to save time.
- std::vector<ElemType> maxG1(tree->Bound().Dim());
- std::vector<ElemType> minG1(maxG1.size());
- std::vector<ElemType> maxG2(maxG1.size());
- std::vector<ElemType> minG2(maxG1.size());
- for (size_t k = 0; k < tree->Bound().Dim(); k++)
- {
- minG1[k] = tree->Children()[sorted[0].n]->Bound()[k].Lo();
- maxG1[k] = tree->Children()[sorted[0].n]->Bound()[k].Hi();
- minG2[k] =
- tree->Children()[sorted[sorted.size() - 1].n]->Bound()[k].Lo();
- maxG2[k] =
- tree->Children()[sorted[sorted.size() - 1].n]->Bound()[k].Hi();
- for (size_t l = 1; l < tree->NumChildren() - 1; l++)
- {
- if (l < cutOff)
- {
- if (tree->Children()[sorted[l].n]->Bound()[k].Lo() < minG1[k])
- minG1[k] = tree->Children()[sorted[l].n]->Bound()[k].Lo();
- else if (tree->Children()[sorted[l].n]->Bound()[k].Hi() > maxG1[k])
- maxG1[k] = tree->Children()[sorted[l].n]->Bound()[k].Hi();
- }
- else
- {
- if (tree->Children()[sorted[l].n]->Bound()[k].Lo() < minG2[k])
- minG2[k] = tree->Children()[sorted[l].n]->Bound()[k].Lo();
- else if (tree->Children()[sorted[l].n]->Bound()[k].Hi() > maxG2[k])
- maxG2[k] = tree->Children()[sorted[l].n]->Bound()[k].Hi();
- }
- }
- }
- ElemType area1 = 1.0, area2 = 1.0;
- ElemType oArea = 1.0;
- for (size_t k = 0; k < maxG1.size(); k++)
- {
- margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
- area1 *= maxG1[k] - minG1[k];
- area2 *= maxG2[k] - minG2[k];
- oArea *= ((maxG1[k] < minG2[k]) || (maxG2[k] < minG1[k])) ? 0.0 :
- std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]);
- }
+ BoundType bound1(tree->Bound().Dim());
+ BoundType bound2(tree->Bound().Dim());
+
+ for (size_t l = 0; l < cutOff; l++)
+ bound1 |= tree->Child(sorted[l].second).Bound();
+
+ for (size_t l = cutOff; l < tree->NumChildren(); l++)
+ bound2 |= tree->Child(sorted[l].second).Bound();
+
+ ElemType area1 = bound1.Volume();
+ ElemType area2 = bound2.Volume();
+ ElemType oArea = bound1.Overlap(bound2);
+
+ for (size_t k = 0; k < bound1.Dim(); k++)
+ margins[i] += bound1[k].Width() + bound2[k].Width();
+
areas[i] += area1 + area2;
overlapedAreas[i] += oArea;
axisScore += margins[i];
@@ -543,15 +518,19 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
{
ElemType axisScore = 0.0;
- // We'll do Bound().Lo() now and use Bound().Hi() later.
- std::vector<sortStruct<ElemType>> sorted(tree->NumChildren());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->NumChildren());
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Children()[i]->Bound()[j].Hi();
- sorted[i].n = i;
+ sorted[i].first = tree->Children()[i]->Bound()[j].Hi();
+ sorted[i].second = i;
}
- std::sort(sorted.begin(), sorted.end(), structComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
// We'll store each of the three scores for each distribution.
std::vector<ElemType> areas(tree->MaxNumChildren() -
@@ -574,48 +553,23 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
// another. Then we calculate the three scores for that distribution.
size_t cutOff = tree->MinNumChildren() + i;
- // We'll calculate the max and min in each dimension by hand to save time.
- std::vector<ElemType> maxG1(tree->Bound().Dim());
- std::vector<ElemType> minG1(maxG1.size());
- std::vector<ElemType> maxG2(maxG1.size());
- std::vector<ElemType> minG2(maxG1.size());
- for (size_t k = 0; k < tree->Bound().Dim(); k++)
- {
- minG1[k] = tree->Children()[sorted[0].n]->Bound()[k].Lo();
- maxG1[k] = tree->Children()[sorted[0].n]->Bound()[k].Hi();
- minG2[k] =
- tree->Children()[sorted[sorted.size() - 1].n]->Bound()[k].Lo();
- maxG2[k] =
- tree->Children()[sorted[sorted.size() - 1].n]->Bound()[k].Hi();
- for (size_t l = 1; l < tree->NumChildren() - 1; l++)
- {
- if (l < cutOff)
- {
- if (tree->Children()[sorted[l].n]->Bound()[k].Lo() < minG1[k])
- minG1[k] = tree->Children()[sorted[l].n]->Bound()[k].Lo();
- else if (tree->Children()[sorted[l].n]->Bound()[k].Hi() > maxG1[k])
- maxG1[k] = tree->Children()[sorted[l].n]->Bound()[k].Hi();
- }
- else
- {
- if (tree->Children()[sorted[l].n]->Bound()[k].Lo() < minG2[k])
- minG2[k] = tree->Children()[sorted[l].n]->Bound()[k].Lo();
- else if (tree->Children()[sorted[l].n]->Bound()[k].Hi() > maxG2[k])
- maxG2[k] = tree->Children()[sorted[l].n]->Bound()[k].Hi();
- }
- }
- }
- ElemType area1 = 1.0, area2 = 1.0;
- ElemType oArea = 1.0;
- for (size_t k = 0; k < maxG1.size(); k++)
- {
- margins[i] += maxG1[k] - minG1[k] + maxG2[k] - minG2[k];
- area1 *= maxG1[k] - minG1[k];
- area2 *= maxG2[k] - minG2[k];
- oArea *= ((maxG1[k] < minG2[k]) || (maxG2[k] < minG1[k])) ? 0.0 :
- std::min(maxG1[k], maxG2[k]) - std::max(minG1[k], minG2[k]);
- }
+ BoundType bound1(tree->Bound().Dim());
+ BoundType bound2(tree->Bound().Dim());
+
+ for (size_t l = 0; l < cutOff; l++)
+ bound1 |= tree->Child(sorted[l].second).Bound();
+
+ for (size_t l = cutOff; l < tree->NumChildren(); l++)
+ bound2 |= tree->Child(sorted[l].second).Bound();
+
+ ElemType area1 = bound1.Volume();
+ ElemType area2 = bound2.Volume();
+ ElemType oArea = bound1.Overlap(bound2);
+
+ for (size_t k = 0; k < bound1.Dim(); k++)
+ margins[i] += bound1[k].Width() + bound2[k].Width();
+
areas[i] += area1 + area2;
overlapedAreas[i] += oArea;
@@ -672,25 +626,30 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
}
}
- std::vector<sortStruct<ElemType>> sorted(tree->NumChildren());
+ std::vector<std::pair<ElemType, size_t>> sorted(tree->NumChildren());
if (lowIsBest)
{
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Children()[i]->Bound()[bestAxis].Lo();
- sorted[i].n = i;
+ sorted[i].first = tree->Children()[i]->Bound()[bestAxis].Lo();
+ sorted[i].second = i;
}
}
else
{
for (size_t i = 0; i < sorted.size(); i++)
{
- sorted[i].d = tree->Children()[i]->Bound()[bestAxis].Hi();
- sorted[i].n = i;
+ sorted[i].first = tree->Children()[i]->Bound()[bestAxis].Hi();
+ sorted[i].second = i;
}
}
- std::sort(sorted.begin(), sorted.end(), structComp<ElemType>);
+ std::sort(sorted.begin(), sorted.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
TreeType* treeOne = new TreeType(tree->Parent(), tree->MaxNumChildren());
TreeType* treeTwo = new TreeType(tree->Parent(), tree->MaxNumChildren());
@@ -704,9 +663,9 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
for (size_t i = 0; i < tree->NumChildren(); i++)
{
if (i < bestAreaIndexOnBestAxis + tree->MinNumChildren())
- InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].second]);
else
- InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].second]);
}
}
else
@@ -719,9 +678,9 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
for (size_t i = 0; i < tree->NumChildren(); i++)
{
if (i < bestOverlapIndexOnBestAxis + tree->MinNumChildren())
- InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].second]);
else
- InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].second]);
}
}
else
@@ -737,30 +696,36 @@ bool XTreeSplit<TreeType>::SplitNonLeafNode(TreeType* tree,
if ((minOverlapSplitDimension != tree->Bound().Dim()) &&
(bestScoreMinOverlapSplit / areaOfBestMinOverlapSplit < MAX_OVERLAP))
{
- std::vector<sortStruct<ElemType>> sorted2(tree->NumChildren());
+ std::vector<std::pair<ElemType, size_t>> sorted2(tree->NumChildren());
if (minOverlapSplitUsesHi)
{
for (size_t i = 0; i < sorted2.size(); i++)
{
- sorted2[i].d = tree->Children()[i]->Bound()[bestAxis].Hi();
- sorted2[i].n = i;
+ sorted2[i].first = tree->Children()[i]->Bound()[bestAxis].Hi();
+ sorted2[i].second = i;
}
}
else
{
for (size_t i = 0; i < sorted2.size(); i++)
{
- sorted2[i].d = tree->Children()[i]->Bound()[bestAxis].Lo();
- sorted2[i].n = i;
+ sorted2[i].first = tree->Children()[i]->Bound()[bestAxis].Lo();
+ sorted2[i].second = i;
}
}
- std::sort(sorted2.begin(), sorted2.end(), structComp<ElemType>);
+ std::sort(sorted2.begin(), sorted2.end(),
+ [] (const std::pair<ElemType, size_t>& p1,
+ const std::pair<ElemType, size_t>& p2)
+ {
+ return p1.first < p2.first;
+ });
+
for (size_t i = 0; i < tree->NumChildren(); i++)
{
if (i < bestIndexMinOverlapSplit + tree->MinNumChildren())
- InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeOne, tree->Children()[sorted[i].second]);
else
- InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].n]);
+ InsertNodeIntoTree(treeTwo, tree->Children()[sorted[i].second]);
}
}
else
More information about the mlpack-git
mailing list