16#ifndef HIGHWAY_HWY_ROBUST_STATISTICS_H_
17#define HIGHWAY_HWY_ROBUST_STATISTICS_H_
27namespace robust_statistics {
34 using Unique = std::pair<T, int>;
35 std::vector<Unique> unique;
36 for (
size_t i = 0; i < num_values; ++i) {
37 const T value = values[i];
39 std::find_if(unique.begin(), unique.end(),
40 [value](
const Unique u) { return u.first == value; });
41 if (pos == unique.end()) {
42 unique.push_back(std::make_pair(value, 1));
49 std::sort(unique.begin(), unique.end());
53 for (
const auto& value_count : unique) {
54 std::fill(p, p + value_count.second, value_count.first);
55 p += value_count.second;
64 const size_t half_count) {
65 T min_range = std::numeric_limits<T>::max();
68 for (
size_t idx = idx_begin; idx < idx_begin + half_count; ++idx) {
69 HWY_ASSERT(sorted[idx] <= sorted[idx + half_count]);
70 const T range = sorted[idx + half_count] - sorted[idx];
71 if (range < min_range) {
89 size_t half_count = num_values / 2;
90 while (half_count > 1) {
91 idx_begin =
MinRange(sorted, idx_begin, half_count);
95 const T x = sorted[idx_begin + 0];
96 if (half_count == 0) {
100 const T average = (x + sorted[idx_begin + 1] + 1) / 2;
106T
Mode(T* values,
const size_t num_values) {
111template <
typename T,
size_t N>
113 return Mode(&values[0], N);
118T
Median(T* values,
const size_t num_values) {
120 std::sort(values, values + num_values);
121 const size_t half = num_values / 2;
123 if (num_values % 2) {
127 return (values[half] + values[half - 1] + 1) / 2;
135 std::vector<T> abs_deviations;
136 abs_deviations.reserve(num_values);
137 for (
size_t i = 0; i < num_values; ++i) {
138 const int64_t abs =
ScalarAbs(
static_cast<int64_t
>(values[i]) -
139 static_cast<int64_t
>(median));
140 abs_deviations.push_back(
static_cast<T
>(abs));
142 return Median(abs_deviations.data(), num_values);
#define HWY_RESTRICT
Definition base.h:95
#define HWY_ASSERT(condition)
Definition base.h:237
T MedianAbsoluteDeviation(const T *values, const size_t num_values, const T median)
Definition robust_statistics.h:132
T Median(T *values, const size_t num_values)
Definition robust_statistics.h:118
void CountingSort(T *values, size_t num_values)
Definition robust_statistics.h:32
T Mode(T *values, const size_t num_values)
Definition robust_statistics.h:106
T ModeOfSorted(const T *const HWY_RESTRICT sorted, const size_t num_values)
Definition robust_statistics.h:87
size_t MinRange(const T *const HWY_RESTRICT sorted, const size_t idx_begin, const size_t half_count)
Definition robust_statistics.h:63
HWY_API HWY_BITCASTSCALAR_CONSTEXPR RemoveCvRef< T > ScalarAbs(T val)
Definition base.h:2815