WeightedLowess
A C++ library for LOWESS with various weighting schemes
Loading...
Searching...
No Matches
interpolate.hpp
Go to the documentation of this file.
1#ifndef WEIGHTEDLOWESS_INTERPOLATE_HPP
2#define WEIGHTEDLOWESS_INTERPOLATE_HPP
3
4#include <vector>
5#include <cstddef>
6#include <utility>
7
8#include "sanisizer/sanisizer.hpp"
9
10#include "window.hpp"
11#include "utils.hpp"
12
18namespace WeightedLowess {
19
29 std::vector<std::size_t> boundaries;
33};
34
51template<typename Data_>
53 const Data_* const x_fit,
54 const PrecomputedWindows<Data_>& windows_fit,
55 const std::size_t num_points_out,
56 const Data_* const x_out
57) {
58 const auto& anchors = windows_fit.anchors;
59 const auto num_anchors = anchors.size();
60
61 AssignedSegments output;
62 sanisizer::resize(output.boundaries, num_anchors);
63
64 std::size_t counter = 0;
65 {
66 const auto right = x_fit[anchors[0]];
67 while (counter < num_points_out && x_out[counter] < right) {
68 ++counter;
69 }
70 }
71
72 for (I<decltype(num_anchors)> i = 1; i < num_anchors; ++i) {
73 output.boundaries[i - 1] = counter;
74 if (counter == num_points_out) {
75 continue;
76 }
77 const auto right = x_fit[anchors[i]];
78 while (counter < num_points_out && x_out[counter] < right) {
79 ++counter;
80 }
81 }
82
83 // Anyone equal to the last anchor get assigned to the last segment.
84 {
85 const auto right = x_fit[anchors[num_anchors - 1]];
86 while (counter < num_points_out && x_out[counter] == right) {
87 ++counter;
88 }
89 output.boundaries[num_anchors - 1] = counter;
90 }
91
92 return output;
93}
94
100inline std::pair<std::size_t, std::size_t> get_interpolation_boundaries(const AssignedSegments& assigned_out) {
101 return std::make_pair(assigned_out.boundaries.front(), assigned_out.boundaries.back());
102}
103
126template<typename Data_>
128 const Data_* const x_fit,
129 const PrecomputedWindows<Data_>& windows_fit,
130 const Data_* const fitted_fit,
131 const Data_* const x_out,
132 const AssignedSegments& assigned_out,
133 Data_* const fitted_out,
134 int num_threads
135) {
136 const auto& anchors = windows_fit.anchors;
137 const auto num_anchors = anchors.size();
138 const auto num_anchors_m1 = num_anchors - 1;
139
140 // One would think that we should parallelize across x_out instead of anchors,
141 // as this has better worksharing when x_out is not evenly distributed across anchor segments.
142 // However, if we did so, we'd have to store the slope and intercept for the anchor segments first,
143 // then look up the slope and intercept for each element of x_out.
144 // This involves an extra memory access and is not SIMD-able.
145 parallelize(num_threads, num_anchors_m1, [&](const int, const I<decltype(num_anchors_m1)> start, const I<decltype(num_anchors_m1)> length) {
146 for (I<decltype(start)> s = start, end = start + length; s < end; ++s) {
147 const auto run_start = assigned_out.boundaries[s];
148 const auto run_end = assigned_out.boundaries[s + 1];
149 if (run_start == run_end) {
150 continue;
151 }
152
153 const auto left_anchor = windows_fit.anchors[s];
154 const auto right_anchor = windows_fit.anchors[s + 1];
155 const Data_ xdiff = x_fit[right_anchor] - x_fit[left_anchor];
156 const Data_ ydiff = fitted_fit[right_anchor] - fitted_fit[left_anchor];
157 if (xdiff > 0) {
158 const Data_ slope = ydiff / xdiff;
159 const Data_ intercept = fitted_fit[right_anchor] - slope * x_fit[right_anchor];
160 for (auto outpt = run_start; outpt < run_end; ++outpt) {
161 fitted_out[outpt] = slope * x_out[outpt] + intercept;
162 }
163 } else {
164 // Protect against infinite slopes by just taking the average.
165 const Data_ ave = fitted_fit[left_anchor] + ydiff / 2;
166 std::fill(fitted_out + run_start, fitted_out + run_end, ave);
167 }
168 }
169 });
170}
171
192template<typename Data_>
193std::pair<std::size_t, std::size_t> interpolate(
194 const Data_* const x_fit,
195 const PrecomputedWindows<Data_>& windows_fit,
196 const Data_* const fitted_fit,
197 const std::size_t num_points_out,
198 const Data_* const x_out,
199 Data_* const fitted_out,
200 int num_threads
201) {
202 const auto assigned_out = assign_to_segments(x_fit, windows_fit, num_points_out, x_out);
203 interpolate(x_fit, windows_fit, fitted_fit, x_out, assigned_out, fitted_out, num_threads);
204 return get_interpolation_boundaries(assigned_out);
205}
206
207}
208
209#endif
Namespace for LOWESS functions.
Definition compute.hpp:18
AssignedSegments assign_to_segments(const Data_ *const x_fit, const PrecomputedWindows< Data_ > &windows_fit, const std::size_t num_points_out, const Data_ *const x_out)
Definition interpolate.hpp:52
void interpolate(const Data_ *const x_fit, const PrecomputedWindows< Data_ > &windows_fit, const Data_ *const fitted_fit, const Data_ *const x_out, const AssignedSegments &assigned_out, Data_ *const fitted_out, int num_threads)
Definition interpolate.hpp:127
std::pair< std::size_t, std::size_t > get_interpolation_boundaries(const AssignedSegments &assigned_out)
Definition interpolate.hpp:100
void parallelize(const int num_workers, const Task_ num_tasks, Run_ run_task_range)
Definition parallelize.hpp:28
Assigned segments.
Definition interpolate.hpp:25
Precomputed windows for LOWESS smoothing.
Definition window.hpp:234
Compute the smoothing window for each point.