| 1 |
// (C) Copyright Nick Thompson 2018 |
| 2 |
// (C) Copyright Matt Borland 2020 |
| 3 |
// Use, modification and distribution are subject to the |
| 4 |
// Boost Software License, Version 1.0. (See accompanying file |
| 5 |
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| 6 |
|
| 7 |
#ifndef BOOST_MATH_STATISTICS_UNIVARIATE_STATISTICS_DETAIL_SINGLE_PASS_HPP |
| 8 |
#define BOOST_MATH_STATISTICS_UNIVARIATE_STATISTICS_DETAIL_SINGLE_PASS_HPP |
| 9 |
|
| 10 |
#include <boost/math/tools/config.hpp> |
| 11 |
#include <boost/math/tools/assert.hpp> |
| 12 |
#include <tuple> |
| 13 |
#include <iterator> |
| 14 |
#include <type_traits> |
| 15 |
#include <cmath> |
| 16 |
#include <algorithm> |
| 17 |
#include <valarray> |
| 18 |
#include <stdexcept> |
| 19 |
#include <functional> |
| 20 |
#include <vector> |
| 21 |
|
| 22 |
#ifdef BOOST_MATH_HAS_THREADS |
| 23 |
#include <future> |
| 24 |
#include <thread> |
| 25 |
#endif |
| 26 |
|
| 27 |
namespace boost { namespace math { namespace statistics { namespace detail { |
| 28 |
|
| 29 |
template<typename ReturnType, typename ForwardIterator> |
| 30 |
ReturnType mean_sequential_impl(ForwardIterator first, ForwardIterator last) |
| 31 |
{ |
| 32 |
const std::size_t elements {static_cast<std::size_t>(std::distance(first, last))}; |
| 33 |
std::valarray<ReturnType> mu {0, 0, 0, 0}; |
| 34 |
std::valarray<ReturnType> temp {0, 0, 0, 0}; |
| 35 |
ReturnType i {1}; |
| 36 |
const ForwardIterator end {std::next(first, elements - (elements % 4))}; |
| 37 |
ForwardIterator it {first}; |
| 38 |
|
| 39 |
while(it != end) |
| 40 |
{ |
| 41 |
const ReturnType inv {ReturnType(1) / i}; |
| 42 |
temp = {static_cast<ReturnType>(*it++), static_cast<ReturnType>(*it++), static_cast<ReturnType>(*it++), static_cast<ReturnType>(*it++)}; |
| 43 |
temp -= mu; |
| 44 |
mu += (temp *= inv); |
| 45 |
i += 1; |
| 46 |
} |
| 47 |
|
| 48 |
const ReturnType num1 {ReturnType(elements - (elements % 4))/ReturnType(4)}; |
| 49 |
const ReturnType num2 {num1 + ReturnType(elements % 4)}; |
| 50 |
|
| 51 |
while(it != last) |
| 52 |
{ |
| 53 |
mu[3] += (*it-mu[3])/i; |
| 54 |
i += 1; |
| 55 |
++it; |
| 56 |
} |
| 57 |
|
| 58 |
return (num1 * std::valarray<ReturnType>(mu[std::slice(0,3,1)]).sum() + num2 * mu[3]) / ReturnType(elements); |
| 59 |
} |
| 60 |
|
| 61 |
// Higham, Accuracy and Stability, equation 1.6a and 1.6b: |
| 62 |
// Calculates Mean, M2, and variance |
| 63 |
template<typename ReturnType, typename ForwardIterator> |
| 64 |
ReturnType variance_sequential_impl(ForwardIterator first, ForwardIterator last) |
| 65 |
{ |
| 66 |
using Real = typename std::tuple_element<0, ReturnType>::type; |
| 67 |
|
| 68 |
Real M = *first; |
| 69 |
Real Q = 0; |
| 70 |
Real k = 2; |
| 71 |
Real M2 = 0; |
| 72 |
std::size_t n = 1; |
| 73 |
|
| 74 |
for(auto it = std::next(first); it != last; ++it) |
| 75 |
{ |
| 76 |
Real tmp = (*it - M) / k; |
| 77 |
Real delta_1 = *it - M; |
| 78 |
Q += k*(k-1)*tmp*tmp; |
| 79 |
M += tmp; |
| 80 |
k += 1; |
| 81 |
Real delta_2 = *it - M; |
| 82 |
M2 += delta_1 * delta_2; |
| 83 |
++n; |
| 84 |
} |
| 85 |
|
| 86 |
return std::make_tuple(M, M2, Q/(k-1), Real(n)); |
| 87 |
} |
| 88 |
|
| 89 |
// https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Higher-order_statistics |
| 90 |
template<typename ReturnType, typename ForwardIterator> |
| 91 |
ReturnType first_four_moments_sequential_impl(ForwardIterator first, ForwardIterator last) |
| 92 |
{ |
| 93 |
using Real = typename std::tuple_element<0, ReturnType>::type; |
| 94 |
using Size = typename std::tuple_element<4, ReturnType>::type; |
| 95 |
|
| 96 |
Real M1 = *first; |
| 97 |
Real M2 = 0; |
| 98 |
Real M3 = 0; |
| 99 |
Real M4 = 0; |
| 100 |
Size n = 2; |
| 101 |
for (auto it = std::next(first); it != last; ++it) |
| 102 |
{ |
| 103 |
Real delta21 = *it - M1; |
| 104 |
Real tmp = delta21/n; |
| 105 |
M4 = M4 + tmp*(tmp*tmp*delta21*((n-1)*(n*n-3*n+3)) + 6*tmp*M2 - 4*M3); |
| 106 |
M3 = M3 + tmp*((n-1)*(n-2)*delta21*tmp - 3*M2); |
| 107 |
M2 = M2 + tmp*(n-1)*delta21; |
| 108 |
M1 = M1 + tmp; |
| 109 |
n += 1; |
| 110 |
} |
| 111 |
|
| 112 |
return std::make_tuple(M1, M2, M3, M4, n-1); |
| 113 |
} |
| 114 |
|
| 115 |
#ifdef BOOST_MATH_HAS_THREADS |
| 116 |
|
| 117 |
// https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Higher-order_statistics |
| 118 |
// EQN 3.1: https://www.osti.gov/servlets/purl/1426900 |
| 119 |
template<typename ReturnType, typename ForwardIterator> |
| 120 |
ReturnType first_four_moments_parallel_impl(ForwardIterator first, ForwardIterator last) |
| 121 |
{ |
| 122 |
using Real = typename std::tuple_element<0, ReturnType>::type; |
| 123 |
|
| 124 |
const auto elements = std::distance(first, last); |
| 125 |
const unsigned max_concurrency = std::thread::hardware_concurrency() == 0 ? 2u : std::thread::hardware_concurrency(); |
| 126 |
unsigned num_threads = 2u; |
| 127 |
|
| 128 |
// Threading is faster for: 10 + 5.13e-3 N/j <= 5.13e-3N => N >= 10^4j/5.13(j-1). |
| 129 |
const auto parallel_lower_bound = 10e4*max_concurrency/(5.13*(max_concurrency-1)); |
| 130 |
const auto parallel_upper_bound = 10e4*2/5.13; // j = 2 |
| 131 |
|
| 132 |
// https://lemire.me/blog/2020/01/30/cost-of-a-thread-in-c-under-linux/ |
| 133 |
if(elements < parallel_lower_bound) |
| 134 |
{ |
| 135 |
return detail::first_four_moments_sequential_impl<ReturnType>(first, last); |
| 136 |
} |
| 137 |
else if(elements >= parallel_upper_bound) |
| 138 |
{ |
| 139 |
num_threads = max_concurrency; |
| 140 |
} |
| 141 |
else |
| 142 |
{ |
| 143 |
for(unsigned i = 3; i < max_concurrency; ++i) |
| 144 |
{ |
| 145 |
if(parallel_lower_bound < 10e4*i/(5.13*(i-1))) |
| 146 |
{ |
| 147 |
num_threads = i; |
| 148 |
break; |
| 149 |
} |
| 150 |
} |
| 151 |
} |
| 152 |
|
| 153 |
std::vector<std::future<ReturnType>> future_manager; |
| 154 |
const auto elements_per_thread = std::ceil(static_cast<double>(elements) / num_threads); |
| 155 |
|
| 156 |
auto it = first; |
| 157 |
for(std::size_t i {}; i < num_threads - 1; ++i) |
| 158 |
{ |
| 159 |
future_manager.emplace_back(std::async(std::launch::async | std::launch::deferred, [it, elements_per_thread]() -> ReturnType |
| 160 |
{ |
| 161 |
return first_four_moments_sequential_impl<ReturnType>(it, std::next(it, elements_per_thread)); |
| 162 |
})); |
| 163 |
it = std::next(it, elements_per_thread); |
| 164 |
} |
| 165 |
|
| 166 |
future_manager.emplace_back(std::async(std::launch::async | std::launch::deferred, [it, last]() -> ReturnType |
| 167 |
{ |
| 168 |
return first_four_moments_sequential_impl<ReturnType>(it, last); |
| 169 |
})); |
| 170 |
|
| 171 |
auto temp = future_manager[0].get(); |
| 172 |
Real M1_a = std::get<0>(temp); |
| 173 |
Real M2_a = std::get<1>(temp); |
| 174 |
Real M3_a = std::get<2>(temp); |
| 175 |
Real M4_a = std::get<3>(temp); |
| 176 |
Real range_a = std::get<4>(temp); |
| 177 |
|
| 178 |
for(std::size_t i = 1; i < future_manager.size(); ++i) |
| 179 |
{ |
| 180 |
temp = future_manager[i].get(); |
| 181 |
Real M1_b = std::get<0>(temp); |
| 182 |
Real M2_b = std::get<1>(temp); |
| 183 |
Real M3_b = std::get<2>(temp); |
| 184 |
Real M4_b = std::get<3>(temp); |
| 185 |
Real range_b = std::get<4>(temp); |
| 186 |
|
| 187 |
const Real n_ab = range_a + range_b; |
| 188 |
const Real delta = M1_b - M1_a; |
| 189 |
|
| 190 |
M1_a = (range_a * M1_a + range_b * M1_b) / n_ab; |
| 191 |
M2_a = M2_a + M2_b + delta * delta * (range_a * range_b / n_ab); |
| 192 |
M3_a = M3_a + M3_b + (delta * delta * delta) * range_a * range_b * (range_a - range_b) / (n_ab * n_ab) |
| 193 |
+ Real(3) * delta * (range_a * M2_b - range_b * M2_a) / n_ab; |
| 194 |
M4_a = M4_a + M4_b + (delta * delta * delta * delta) * range_a * range_b * (range_a * range_a - range_a * range_b + range_b * range_b) / (n_ab * n_ab * n_ab) |
| 195 |
+ Real(6) * delta * delta * (range_a * range_a * M2_b + range_b * range_b * M2_a) / (n_ab * n_ab) |
| 196 |
+ Real(4) * delta * (range_a * M3_b - range_b * M3_a) / n_ab; |
| 197 |
range_a = n_ab; |
| 198 |
} |
| 199 |
|
| 200 |
return std::make_tuple(M1_a, M2_a, M3_a, M4_a, elements); |
| 201 |
} |
| 202 |
|
| 203 |
#endif // BOOST_MATH_HAS_THREADS |
| 204 |
|
| 205 |
// Follows equation 1.5 of: |
| 206 |
// https://prod.sandia.gov/techlib-noauth/access-control.cgi/2008/086212.pdf |
| 207 |
template<typename ReturnType, typename ForwardIterator> |
| 208 |
ReturnType skewness_sequential_impl(ForwardIterator first, ForwardIterator last) |
| 209 |
{ |
| 210 |
using std::sqrt; |
| 211 |
BOOST_MATH_ASSERT_MSG(first != last, "At least one sample is required to compute skewness."); |
| 212 |
|
| 213 |
ReturnType M1 = *first; |
| 214 |
ReturnType M2 = 0; |
| 215 |
ReturnType M3 = 0; |
| 216 |
ReturnType n = 2; |
| 217 |
|
| 218 |
for (auto it = std::next(first); it != last; ++it) |
| 219 |
{ |
| 220 |
ReturnType delta21 = *it - M1; |
| 221 |
ReturnType tmp = delta21/n; |
| 222 |
M3 += tmp*((n-1)*(n-2)*delta21*tmp - 3*M2); |
| 223 |
M2 += tmp*(n-1)*delta21; |
| 224 |
M1 += tmp; |
| 225 |
n += 1; |
| 226 |
} |
| 227 |
|
| 228 |
ReturnType var = M2/(n-1); |
| 229 |
|
| 230 |
if (var == 0) |
| 231 |
{ |
| 232 |
// The limit is technically undefined, but the interpretation here is clear: |
| 233 |
// A constant dataset has no skewness. |
| 234 |
return ReturnType(0); |
| 235 |
} |
| 236 |
|
| 237 |
ReturnType skew = M3/(M2*sqrt(var)); |
| 238 |
return skew; |
| 239 |
} |
| 240 |
|
| 241 |
template<typename ReturnType, typename ForwardIterator> |
| 242 |
ReturnType gini_coefficient_sequential_impl(ForwardIterator first, ForwardIterator last) |
| 243 |
{ |
| 244 |
ReturnType i = 1; |
| 245 |
ReturnType num = 0; |
| 246 |
ReturnType denom = 0; |
| 247 |
|
| 248 |
for(auto it = first; it != last; ++it) |
| 249 |
{ |
| 250 |
num += *it*i; |
| 251 |
denom += *it; |
| 252 |
++i; |
| 253 |
} |
| 254 |
|
| 255 |
// If the l1 norm is zero, all elements are zero, so every element is the same. |
| 256 |
if(denom == 0) |
| 257 |
{ |
| 258 |
return ReturnType(0); |
| 259 |
} |
| 260 |
else |
| 261 |
{ |
| 262 |
return ((2*num)/denom - i)/(i-1); |
| 263 |
} |
| 264 |
} |
| 265 |
|
| 266 |
template<typename ReturnType, typename ForwardIterator> |
| 267 |
ReturnType gini_range_fraction(ForwardIterator first, ForwardIterator last, std::size_t starting_index) |
| 268 |
{ |
| 269 |
using Real = typename std::tuple_element<0, ReturnType>::type; |
| 270 |
|
| 271 |
std::size_t i = starting_index + 1; |
| 272 |
Real num = 0; |
| 273 |
Real denom = 0; |
| 274 |
|
| 275 |
for(auto it = first; it != last; ++it) |
| 276 |
{ |
| 277 |
num += *it*i; |
| 278 |
denom += *it; |
| 279 |
++i; |
| 280 |
} |
| 281 |
|
| 282 |
return std::make_tuple(num, denom, i); |
| 283 |
} |
| 284 |
|
| 285 |
#ifdef BOOST_MATH_HAS_THREADS |
| 286 |
|
| 287 |
template<typename ReturnType, typename ExecutionPolicy, typename ForwardIterator> |
| 288 |
ReturnType gini_coefficient_parallel_impl(ExecutionPolicy&&, ForwardIterator first, ForwardIterator last) |
| 289 |
{ |
| 290 |
using range_tuple = std::tuple<ReturnType, ReturnType, std::size_t>; |
| 291 |
|
| 292 |
const auto elements = std::distance(first, last); |
| 293 |
const unsigned max_concurrency = std::thread::hardware_concurrency() == 0 ? 2u : std::thread::hardware_concurrency(); |
| 294 |
unsigned num_threads = 2u; |
| 295 |
|
| 296 |
// Threading is faster for: 10 + 10.12e-3 N/j <= 10.12e-3N => N >= 10^4j/10.12(j-1). |
| 297 |
const auto parallel_lower_bound = 10e4*max_concurrency/(10.12*(max_concurrency-1)); |
| 298 |
const auto parallel_upper_bound = 10e4*2/10.12; // j = 2 |
| 299 |
|
| 300 |
// https://lemire.me/blog/2020/01/30/cost-of-a-thread-in-c-under-linux/ |
| 301 |
if(elements < parallel_lower_bound) |
| 302 |
{ |
| 303 |
return gini_coefficient_sequential_impl<ReturnType>(first, last); |
| 304 |
} |
| 305 |
else if(elements >= parallel_upper_bound) |
| 306 |
{ |
| 307 |
num_threads = max_concurrency; |
| 308 |
} |
| 309 |
else |
| 310 |
{ |
| 311 |
for(unsigned i = 3; i < max_concurrency; ++i) |
| 312 |
{ |
| 313 |
if(parallel_lower_bound < 10e4*i/(10.12*(i-1))) |
| 314 |
{ |
| 315 |
num_threads = i; |
| 316 |
break; |
| 317 |
} |
| 318 |
} |
| 319 |
} |
| 320 |
|
| 321 |
std::vector<std::future<range_tuple>> future_manager; |
| 322 |
const auto elements_per_thread = std::ceil(static_cast<double>(elements) / num_threads); |
| 323 |
|
| 324 |
auto it = first; |
| 325 |
for(std::size_t i {}; i < num_threads - 1; ++i) |
| 326 |
{ |
| 327 |
future_manager.emplace_back(std::async(std::launch::async | std::launch::deferred, [it, elements_per_thread, i]() -> range_tuple |
| 328 |
{ |
| 329 |
return gini_range_fraction<range_tuple>(it, std::next(it, elements_per_thread), i*elements_per_thread); |
| 330 |
})); |
| 331 |
it = std::next(it, elements_per_thread); |
| 332 |
} |
| 333 |
|
| 334 |
future_manager.emplace_back(std::async(std::launch::async | std::launch::deferred, [it, last, num_threads, elements_per_thread]() -> range_tuple |
| 335 |
{ |
| 336 |
return gini_range_fraction<range_tuple>(it, last, (num_threads - 1)*elements_per_thread); |
| 337 |
})); |
| 338 |
|
| 339 |
ReturnType num = 0; |
| 340 |
ReturnType denom = 0; |
| 341 |
|
| 342 |
for(std::size_t i = 0; i < future_manager.size(); ++i) |
| 343 |
{ |
| 344 |
auto temp = future_manager[i].get(); |
| 345 |
num += std::get<0>(temp); |
| 346 |
denom += std::get<1>(temp); |
| 347 |
} |
| 348 |
|
| 349 |
// If the l1 norm is zero, all elements are zero, so every element is the same. |
| 350 |
if(denom == 0) |
| 351 |
{ |
| 352 |
return ReturnType(0); |
| 353 |
} |
| 354 |
else |
| 355 |
{ |
| 356 |
return ((2*num)/denom - elements)/(elements-1); |
| 357 |
} |
| 358 |
} |
| 359 |
|
| 360 |
#endif // BOOST_MATH_HAS_THREADS |
| 361 |
|
| 362 |
template<typename ForwardIterator, typename OutputIterator> |
| 363 |
OutputIterator mode_impl(ForwardIterator first, ForwardIterator last, OutputIterator output) |
| 364 |
{ |
| 365 |
using Z = typename std::iterator_traits<ForwardIterator>::value_type; |
| 366 |
using Size = typename std::iterator_traits<ForwardIterator>::difference_type; |
| 367 |
|
| 368 |
std::vector<Z> modes {}; |
| 369 |
modes.reserve(16); |
| 370 |
Size max_counter {0}; |
| 371 |
|
| 372 |
while(first != last) |
| 373 |
{ |
| 374 |
Size current_count {0}; |
| 375 |
ForwardIterator end_it {first}; |
| 376 |
while(end_it != last && *end_it == *first) |
| 377 |
{ |
| 378 |
++current_count; |
| 379 |
++end_it; |
| 380 |
} |
| 381 |
|
| 382 |
if(current_count > max_counter) |
| 383 |
{ |
| 384 |
modes.resize(1); |
| 385 |
modes[0] = *first; |
| 386 |
max_counter = current_count; |
| 387 |
} |
| 388 |
|
| 389 |
else if(current_count == max_counter) |
| 390 |
{ |
| 391 |
modes.emplace_back(*first); |
| 392 |
} |
| 393 |
|
| 394 |
first = end_it; |
| 395 |
} |
| 396 |
|
| 397 |
return std::move(modes.begin(), modes.end(), output); |
| 398 |
} |
| 399 |
}}}} |
| 400 |
|
| 401 |
#endif // BOOST_MATH_STATISTICS_UNIVARIATE_STATISTICS_DETAIL_SINGLE_PASS_HPP |