diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 19:33:14 +0000 |
commit | 36d22d82aa202bb199967e9512281e9a53db42c9 (patch) | |
tree | 105e8c98ddea1c1e4784a60a5a6410fa416be2de /third_party/libwebrtc/rtc_base/numerics/running_statistics.h | |
parent | Initial commit. (diff) | |
download | firefox-esr-upstream.tar.xz firefox-esr-upstream.zip |
Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/libwebrtc/rtc_base/numerics/running_statistics.h')
-rw-r--r-- | third_party/libwebrtc/rtc_base/numerics/running_statistics.h | 161 |
1 files changed, 161 insertions, 0 deletions
diff --git a/third_party/libwebrtc/rtc_base/numerics/running_statistics.h b/third_party/libwebrtc/rtc_base/numerics/running_statistics.h new file mode 100644 index 0000000000..bbcc7e2a73 --- /dev/null +++ b/third_party/libwebrtc/rtc_base/numerics/running_statistics.h @@ -0,0 +1,161 @@ +/* + * Copyright (c) 2019 The WebRTC project authors. All Rights Reserved. + * + * Use of this source code is governed by a BSD-style license + * that can be found in the LICENSE file in the root of the source + * tree. An additional intellectual property rights grant can be found + * in the file PATENTS. All contributing project authors may + * be found in the AUTHORS file in the root of the source tree. + */ + +#ifndef API_NUMERICS_RUNNING_STATISTICS_H_ +#define API_NUMERICS_RUNNING_STATISTICS_H_ + +#include <algorithm> +#include <cmath> +#include <limits> + +#include "absl/types/optional.h" +#include "rtc_base/checks.h" +#include "rtc_base/numerics/math_utils.h" + +namespace webrtc { +namespace webrtc_impl { + +// tl;dr: Robust and efficient online computation of statistics, +// using Welford's method for variance. [1] +// +// This should be your go-to class if you ever need to compute +// min, max, mean, variance and standard deviation. +// If you need to get percentiles, please use webrtc::SamplesStatsCounter. +// +// Please note RemoveSample() won't affect min and max. +// If you want a full-fledged moving window over N last samples, +// please use webrtc::RollingAccumulator. +// +// The measures return absl::nullopt if no samples were fed (Size() == 0), +// otherwise the returned optional is guaranteed to contain a value. +// +// [1] +// https://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Welford's_online_algorithm + +// The type T is a scalar which must be convertible to double. +// Rationale: we often need greater precision for measures +// than for the samples themselves. +template <typename T> +class RunningStatistics { + public: + // Update stats //////////////////////////////////////////// + + // Add a value participating in the statistics in O(1) time. + void AddSample(T sample) { + max_ = std::max(max_, sample); + min_ = std::min(min_, sample); + ++size_; + // Welford's incremental update. + const double delta = sample - mean_; + mean_ += delta / size_; + const double delta2 = sample - mean_; + cumul_ += delta * delta2; + } + + // Remove a previously added value in O(1) time. + // Nb: This doesn't affect min or max. + // Calling RemoveSample when Size()==0 is incorrect. + void RemoveSample(T sample) { + RTC_DCHECK_GT(Size(), 0); + // In production, just saturate at 0. + if (Size() == 0) { + return; + } + // Since samples order doesn't matter, this is the + // exact reciprocal of Welford's incremental update. + --size_; + const double delta = sample - mean_; + mean_ -= delta / size_; + const double delta2 = sample - mean_; + cumul_ -= delta * delta2; + } + + // Merge other stats, as if samples were added one by one, but in O(1). + void MergeStatistics(const RunningStatistics<T>& other) { + if (other.size_ == 0) { + return; + } + max_ = std::max(max_, other.max_); + min_ = std::min(min_, other.min_); + const int64_t new_size = size_ + other.size_; + const double new_mean = + (mean_ * size_ + other.mean_ * other.size_) / new_size; + // Each cumulant must be corrected. + // * from: sum((x_i - mean_)²) + // * to: sum((x_i - new_mean)²) + auto delta = [new_mean](const RunningStatistics<T>& stats) { + return stats.size_ * (new_mean * (new_mean - 2 * stats.mean_) + + stats.mean_ * stats.mean_); + }; + cumul_ = cumul_ + delta(*this) + other.cumul_ + delta(other); + mean_ = new_mean; + size_ = new_size; + } + + // Get Measures //////////////////////////////////////////// + + // Returns number of samples involved via AddSample() or MergeStatistics(), + // minus number of times RemoveSample() was called. + int64_t Size() const { return size_; } + + // Returns minimum among all seen samples, in O(1) time. + // This isn't affected by RemoveSample(). + absl::optional<T> GetMin() const { + if (size_ == 0) { + return absl::nullopt; + } + return min_; + } + + // Returns maximum among all seen samples, in O(1) time. + // This isn't affected by RemoveSample(). + absl::optional<T> GetMax() const { + if (size_ == 0) { + return absl::nullopt; + } + return max_; + } + + // Returns mean in O(1) time. + absl::optional<double> GetMean() const { + if (size_ == 0) { + return absl::nullopt; + } + return mean_; + } + + // Returns unbiased sample variance in O(1) time. + absl::optional<double> GetVariance() const { + if (size_ == 0) { + return absl::nullopt; + } + return cumul_ / size_; + } + + // Returns unbiased standard deviation in O(1) time. + absl::optional<double> GetStandardDeviation() const { + if (size_ == 0) { + return absl::nullopt; + } + return std::sqrt(*GetVariance()); + } + + private: + int64_t size_ = 0; // Samples seen. + T min_ = infinity_or_max<T>(); + T max_ = minus_infinity_or_min<T>(); + double mean_ = 0; + double cumul_ = 0; // Variance * size_, sometimes noted m2. +}; + +} // namespace webrtc_impl +} // namespace webrtc + +#endif // API_NUMERICS_RUNNING_STATISTICS_H_ |