mlpack 3.4.2
perform_split.hpp
Go to the documentation of this file.
1
16#ifndef MLPACK_CORE_TREE_PERFORM_SPLIT_HPP
17#define MLPACK_CORE_TREE_PERFORM_SPLIT_HPP
18
19namespace mlpack {
20namespace tree {
21namespace split {
22
35template<typename MatType, typename SplitType>
36size_t PerformSplit(MatType& data,
37 const size_t begin,
38 const size_t count,
39 const typename SplitType::SplitInfo& splitInfo)
40{
41 // This method modifies the input dataset. We loop both from the left and
42 // right sides of the points contained in this node.
43 size_t left = begin;
44 size_t right = begin + count - 1;
45
46 // First half-iteration of the loop is out here because the termination
47 // condition is in the middle.
48 while ((left <= right) &&
49 (SplitType::AssignToLeftNode(data.col(left), splitInfo)))
50 left++;
51 while ((!SplitType::AssignToLeftNode(data.col(right), splitInfo)) &&
52 (left <= right) && (right > 0))
53 right--;
54
55 // Shortcut for when all points are on the right.
56 if (left == right && right == 0)
57 return left;
58
59 while (left <= right)
60 {
61 // Swap columns.
62 data.swap_cols(left, right);
63
64 // See how many points on the left are correct. When they are correct,
65 // increase the left counter accordingly. When we encounter one that isn't
66 // correct, stop. We will switch it later.
67 while (SplitType::AssignToLeftNode(data.col(left), splitInfo) &&
68 (left <= right))
69 left++;
70
71 // Now see how many points on the right are correct. When they are correct,
72 // decrease the right counter accordingly. When we encounter one that isn't
73 // correct, stop. We will switch it with the wrong point we found in the
74 // previous loop.
75 while ((!SplitType::AssignToLeftNode(data.col(right), splitInfo)) &&
76 (left <= right))
77 right--;
78 }
79
80 Log::Assert(left == right + 1);
81
82 return left;
83}
84
100template<typename MatType, typename SplitType>
101size_t PerformSplit(MatType& data,
102 const size_t begin,
103 const size_t count,
104 const typename SplitType::SplitInfo& splitInfo,
105 std::vector<size_t>& oldFromNew)
106{
107 // This method modifies the input dataset. We loop both from the left and
108 // right sides of the points contained in this node.
109 size_t left = begin;
110 size_t right = begin + count - 1;
111
112 // First half-iteration of the loop is out here because the termination
113 // condition is in the middle.
114 while ((left <= right) &&
115 (SplitType::AssignToLeftNode(data.col(left), splitInfo)))
116 left++;
117 while ((!SplitType::AssignToLeftNode(data.col(right), splitInfo)) &&
118 (left <= right) && (right > 0))
119 right--;
120
121 // Shortcut for when all points are on the right.
122 if (left == right && right == 0)
123 return left;
124
125 while (left <= right)
126 {
127 // Swap columns.
128 data.swap_cols(left, right);
129
130 // Update the indices for what we changed.
131 size_t t = oldFromNew[left];
132 oldFromNew[left] = oldFromNew[right];
133 oldFromNew[right] = t;
134
135 // See how many points on the left are correct. When they are correct,
136 // increase the left counter accordingly. When we encounter one that isn't
137 // correct, stop. We will switch it later.
138 while (SplitType::AssignToLeftNode(data.col(left), splitInfo) &&
139 (left <= right))
140 left++;
141
142 // Now see how many points on the right are correct. When they are correct,
143 // decrease the right counter accordingly. When we encounter one that isn't
144 // correct, stop. We will switch it with the wrong point we found in the
145 // previous loop.
146 while ((!SplitType::AssignToLeftNode(data.col(right), splitInfo)) &&
147 (left <= right))
148 right--;
149 }
150
151 Log::Assert(left == right + 1);
152 return left;
153}
154
155} // namespace split
156} // namespace tree
157} // namespace mlpack
158
159
160#endif // MLPACK_CORE_TREE_BINARY_SPACE_TREE_PERFORM_SPLIT_HPP
static void Assert(bool condition, const std::string &message="Assert Failed.")
Checks if the specified condition is true.
size_t PerformSplit(MatType &data, const size_t begin, const size_t count, const typename SplitType::SplitInfo &splitInfo)
This function implements the default split behavior i.e.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: cv.hpp:1