cheatah
Source BigBrain
Source

stdlib/statistics/statistics.hpp

1// Copyright (c) 2026 BigBrain LLC. MIT-licensed (see LICENSE).
2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.
3#pragma once
5/**
6 * @file statistics.hpp
7 * @brief cheatah `statistics` — descriptive statistics over numeric sequences,
8 * mirroring Python's `statistics` module. `import statistics` to use it.
9 *
10 * Header-only: every function is a template constrained by the `NumericRange`
11 * concept, so it accepts any iterable of arithmetic values (`list[float]`,
12 * `array[int]`, …) and is instantiated at the call site. Unit tests:
13 * `stdlib/tests/statistics_test.cpp`; the suite runs under AddressSanitizer (the
14 * `asan` preset) and Valgrind (`security/run-valgrind.sh`) on every QA-gate run.
15 *
16 * @note `n` below is the element count. Single-pass reductions are O(n) and
17 * allocation-free; `median` is the exception (it materializes and sorts a
18 * copy). Results are scalar `double`/`std::size_t` — no heap on return.
19 */
20#include <algorithm>
21#include <cmath>
22#include <cstddef>
23#include <ranges>
24#include <type_traits>
25#include <vector>
27namespace cheatah::statistics {
29/// NumericRange<R>: an iterable of arithmetic values (list[float], array[int], …).
30template <typename R>
31concept NumericRange =
32 std::ranges::input_range<R> && std::is_arithmetic_v<std::ranges::range_value_t<R>>;
34/**
35 * Sum of the elements.
36 *
37 * Accumulates every element into a `double`, so an empty range sums to 0.0 and
38 * integer inputs are widened before adding (no integer overflow).
39 * @param data the numeric range.
40 * @return Σ@p data as `double`.
41 * @complexity O(n) single pass.
42 * @alloc none.
43 * @test CheatahStatistics.SumCountMean
44 * @crtest StatisticsCompileRun.Sum
45 * @systest StdlibE2E.Statistics
46 */
47template <NumericRange R>
48double sum(const R& data) {
49 double s = 0.0;
50 for (const auto& x : data) s += static_cast<double>(x);
51 return s;
54/**
55 * Element count.
56 * @param data the numeric range.
57 * @return the number of elements.
58 * @complexity O(n) single pass.
59 * @alloc none.
60 * @test CheatahStatistics.SumCountMean
61 * @crtest StatisticsCompileRun.Count
62 * @systest StdlibE2E.Statistics
63 */
64template <NumericRange R>
65std::size_t count(const R& data) {
66 std::size_t n = 0;
67 for (const auto& x : data) {
68 (void)x;
69 ++n;
70 }
71 return n;
74/**
75 * Arithmetic mean.
76 *
77 * Computes sum/count, but guards division by zero: an empty range returns 0.0
78 * rather than NaN.
79 * @param data the numeric range.
80 * @return the mean, or 0.0 if empty.
81 * @complexity O(n) (two passes: count + sum).
82 * @alloc none.
83 * @test CheatahStatistics.SumCountMean
84 * @crtest StatisticsCompileRun.Mean
85 * @systest StdlibE2E.Statistics
86 */
87template <NumericRange R>
88double mean(const R& data) {
89 const std::size_t n = count(data);
90 return n == 0 ? 0.0 : sum(data) / static_cast<double>(n);
93/**
94 * Population variance (divide by N).
95 *
96 * Mean of the squared deviations from the mean, dividing by N (treats @p data as
97 * the entire population). Returns 0.0 for an empty or single-element range.
98 * @param data the numeric range.
99 * @return the variance, or 0.0 if empty.
100 * @complexity O(n).
101 * @alloc none.
102 * @test CheatahStatistics.PopulationVarianceAndStdev
103 * @crtest StatisticsCompileRun.Pvariance
104 * @systest StdlibE2E.Statistics
105 */
106template <NumericRange R>
107double pvariance(const R& data) {
108 const double m = mean(data);
109 double s = 0.0;
110 std::size_t n = 0;
111 for (const auto& x : data) {
112 const double d = static_cast<double>(x) - m;
113 s += d * d;
114 ++n;
115 }
116 return n == 0 ? 0.0 : s / static_cast<double>(n);
118/**
119 * Population standard deviation.
120 *
121 * Square root of @ref pvariance, so it is 0.0 for empty or single-element ranges
122 * and never negative.
123 * @param data the numeric range.
124 * @return √pvariance(@p data).
125 * @complexity O(n).
126 * @alloc none.
127 * @test CheatahStatistics.PopulationVarianceAndStdev
128 * @crtest StatisticsCompileRun.Pstdev
129 * @systest StdlibE2E.Statistics
130 */
131template <NumericRange R>
132double pstdev(const R& data) { return std::sqrt(pvariance(data)); }
134/**
135 * Sample variance (divide by N−1).
136 *
137 * Sum of squared deviations from the mean divided by N−1 (Bessel's correction,
138 * estimating the variance of the wider population from a sample). Requires at
139 * least two elements; an empty or single-element range returns 0.0 rather than
140 * dividing by zero.
141 * @param data the numeric range.
142 * @return the variance, or 0.0 if fewer than 2 elements.
143 * @complexity O(n).
144 * @alloc none.
145 * @test CheatahStatistics.SampleVarianceAndStdev
146 * @crtest StatisticsCompileRun.Variance
147 * @systest StdlibE2E.Statistics
148 */
149template <NumericRange R>
150double variance(const R& data) {
151 const double m = mean(data);
152 double s = 0.0;
153 std::size_t n = 0;
154 for (const auto& x : data) {
155 const double d = static_cast<double>(x) - m;
156 s += d * d;
157 ++n;
158 }
159 return n > 1 ? s / static_cast<double>(n - 1) : 0.0;
161/**
162 * Sample standard deviation.
163 *
164 * Square root of @ref variance, so it is 0.0 when there are fewer than two
165 * elements.
166 * @param data the numeric range.
167 * @return √variance(@p data).
168 * @complexity O(n).
169 * @alloc none.
170 * @test CheatahStatistics.SampleVarianceAndStdev
171 * @crtest StatisticsCompileRun.Stdev
172 * @systest StdlibE2E.Statistics
173 */
174template <NumericRange R>
175double stdev(const R& data) { return std::sqrt(variance(data)); }
177/**
178 * Median (mean of the two middle values when the count is even).
179 *
180 * Copies the elements into a `double` vector, sorts ascending, and returns the
181 * middle value (averaging the two central values when the count is even).
182 * Returns 0.0 for an empty range.
183 * @param data the numeric range.
184 * @return the median, or 0.0 if empty.
185 * @complexity O(n log n) — copies the elements into a vector and sorts.
186 * @alloc allocates a temporary `std::vector<double>`.
187 * @test CheatahStatistics.MedianOddAndEven
188 * @crtest StatisticsCompileRun.Median
189 * @systest StdlibE2E.Statistics
190 */
191template <NumericRange R>
192double median(const R& data) {
193 std::vector<double> v;
194 for (const auto& x : data) v.push_back(static_cast<double>(x));
195 if (v.empty()) return 0.0;
196 std::sort(v.begin(), v.end());
197 const std::size_t n = v.size();
198 return (n % 2 == 1) ? v[n / 2] : (v[n / 2 - 1] + v[n / 2]) / 2.0;
201} // namespace cheatah::statistics