Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
running_stat.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_UTIL_RUNNING_STAT_H_
15#define OR_TOOLS_UTIL_RUNNING_STAT_H_
16
17#include <cstddef>
18#include <deque>
19#include <vector>
20
22
23namespace operations_research {
24
25// Simple class to compute the average over a fixed size window of an integer
26// stream.
28 public:
29 // Initialize the class with the maximum window size.
30 // It must be positive (this is CHECKed).
31 explicit RunningAverage(int window_size = 1);
32
33 // This type is neither copyable nor movable.
36
37 // Resets the class to the exact same state as if it was just constructed with
38 // the given window size.
39 void Reset(int window_size);
40
41 // Adds the next integer of the stream.
42 void Add(int value);
43
44 // Returns the average of all the values added so far or zero if no values
45 // where added.
46 double GlobalAverage() const;
47
48 // Returns the average of the values in the current window or zero if the
49 // current window is empty.
50 double WindowAverage() const;
51
52 // Returns true iff the current window size is equal to the one specified in
53 // the constructor.
54 bool IsWindowFull() const;
55
56 // Clears the current window.
57 void ClearWindow();
58
59 private:
60 int window_size_;
61 int num_adds_;
62 double global_sum_;
63 double local_sum_;
64 std::deque<int> values_;
65};
66
67// Simple class to efficiently compute the maximum over a fixed size window
68// of a numeric stream. This works in constant average amortized time.
69template <class Number = double>
71 public:
72 // Takes the size of the running window. The size must be positive.
73 explicit RunningMax(int window_size);
74
75 // This type is neither copyable nor movable.
76 RunningMax(const RunningMax&) = delete;
77 RunningMax& operator=(const RunningMax&) = delete;
78
79 // Processes a new element from the stream.
80 void Add(Number value);
81
82 // Returns the current maximum element in the window.
83 // An element must have been added before calling this function.
84 Number GetCurrentMax();
85
86 void Reset();
87
88 private:
89 const int window_size_;
90
91 // Values in the current window.
92 std::vector<Number> values_;
93
94 // Index of the last added element in the window.
95 int last_index_;
96
97 // Index of the current maximum element.
98 int max_index_;
99};
100
101// ################## Implementations below #####################
102
103inline RunningAverage::RunningAverage(int window_size)
104 : window_size_(window_size),
105 num_adds_(0),
106 global_sum_(0.0),
107 local_sum_(0.0) {
108 CHECK_GT(window_size_, 0);
109}
110
111inline void RunningAverage::Reset(int window_size) {
112 window_size_ = window_size;
113 num_adds_ = 0;
114 global_sum_ = 0.0;
115 ClearWindow();
116}
117
118inline void RunningAverage::Add(int value) {
119 ++num_adds_;
120 global_sum_ += value;
121 local_sum_ += value;
122 values_.push_back(value);
123 if (static_cast<int>(values_.size()) > window_size_) {
124 local_sum_ -= values_.front();
125 values_.pop_front();
126 }
127}
128
129inline double RunningAverage::GlobalAverage() const {
130 return num_adds_ == 0 ? 0.0 : global_sum_ / static_cast<double>(num_adds_);
131}
132
133inline double RunningAverage::WindowAverage() const {
134 return values_.empty() ? 0.0
135 : local_sum_ / static_cast<double>(values_.size());
136}
137
139 local_sum_ = 0.0;
140 values_.clear();
141}
142
143inline bool RunningAverage::IsWindowFull() const {
144 return static_cast<int>(values_.size()) == window_size_;
145}
146
147template <class Number>
149 : window_size_(window_size), values_(), last_index_(0), max_index_(0) {
150 DCHECK_GT(window_size, 0);
151}
152
153template <class Number>
154void RunningMax<Number>::Add(Number value) {
155 if (static_cast<size_t>(values_.size()) < window_size_) {
156 // Starting phase until values_ reaches its final size.
157 // Note that last_index_ stays at 0 during this phase.
158 if (values_.empty() || value >= GetCurrentMax()) {
159 max_index_ = values_.size();
160 }
161 values_.push_back(value);
162 return;
163 }
164 // We are in the steady state.
165 DCHECK_EQ(values_.size(), window_size_);
166 // Note the use of >= instead of > to get the O(1) behavior in presence of
167 // many identical values.
168 if (value >= GetCurrentMax()) {
169 max_index_ = last_index_;
170 values_[last_index_] = value;
171 } else {
172 values_[last_index_] = value;
173 if (last_index_ == max_index_) {
174 // We need to recompute the max.
175 // Note that this happens only if value was strictly lower than
176 // GetCurrentMax() in the last window_size_ updates.
177 max_index_ = 0;
178 Number max_value = values_[max_index_];
179 for (int i = 1; i < static_cast<int>(values_.size()); ++i) {
180 if (values_[i] > max_value) {
181 max_value = values_[i];
182 max_index_ = i;
183 }
184 }
185 }
186 }
187 if (++last_index_ == window_size_) {
188 last_index_ = 0;
189 }
190}
191
192template <class Number>
194 values_.clear();
195 last_index_ = 0;
196 max_index_ = 0;
197}
198
199template <class Number>
201 DCHECK(!values_.empty());
202 return values_[max_index_];
203}
204
205} // namespace operations_research
206
207#endif // OR_TOOLS_UTIL_RUNNING_STAT_H_
RunningAverage & operator=(const RunningAverage &)=delete
void ClearWindow()
Clears the current window.
RunningAverage(const RunningAverage &)=delete
This type is neither copyable nor movable.
void Add(int value)
Adds the next integer of the stream.
RunningAverage(int window_size=1)
################## Implementations below #####################
RunningMax(int window_size)
Takes the size of the running window. The size must be positive.
void Add(Number value)
Processes a new element from the stream.
RunningMax & operator=(const RunningMax &)=delete
RunningMax(const RunningMax &)=delete
This type is neither copyable nor movable.
In SWIG mode, we don't want anything besides these top-level includes.