OR-Tools  8.2
running_stat.h
Go to the documentation of this file.
1// Copyright 2010-2018 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 <deque>
18
20#include "ortools/base/macros.h"
21
22namespace operations_research {
23
24// Simple class to compute the average over a fixed size window of an integer
25// stream.
27 public:
28 // Initialize the class with the maximum window size.
29 // It must be positive (this is CHECKed).
30 explicit RunningAverage(int window_size = 1);
31
32 // Resets the class to the exact same state as if it was just constructed with
33 // the given window size.
34 void Reset(int window_size);
35
36 // Adds the next integer of the stream.
37 void Add(int value);
38
39 // Returns the average of all the values added so far or zero if no values
40 // where added.
41 double GlobalAverage() const;
42
43 // Returns the average of the values in the current window or zero if the
44 // current window is empty.
45 double WindowAverage() const;
46
47 // Returns true iff the current window size is equal to the one specified in
48 // the constructor.
49 bool IsWindowFull() const;
50
51 // Clears the current window.
52 void ClearWindow();
53
54 private:
55 int window_size_;
56 int num_adds_;
57 double global_sum_;
58 double local_sum_;
59 std::deque<int> values_;
60
61 DISALLOW_COPY_AND_ASSIGN(RunningAverage);
62};
63
64// Simple class to compute efficiently the maximum over a fixed size window
65// of a numeric stream. This works in constant average amortized time.
66template <class Number = double>
68 public:
69 // Takes the size of the running window. The size must be positive.
70 explicit RunningMax(int window_size);
71
72 // Processes a new element from the stream.
73 void Add(Number value);
74
75 // Returns the current maximum element in the window.
76 // An element must have been added before calling this function.
77 Number GetCurrentMax();
78
79 private:
80 const int window_size_;
81
82 // Values in the current window.
83 std::vector<Number> values_;
84
85 // Index of the last added element in the window.
86 int last_index_;
87
88 // Index of the current maximum element.
89 int max_index_;
90
91 DISALLOW_COPY_AND_ASSIGN(RunningMax);
92};
93
94// ################## Implementations below #####################
95
96inline RunningAverage::RunningAverage(int window_size)
97 : window_size_(window_size),
98 num_adds_(0),
99 global_sum_(0.0),
100 local_sum_(0.0) {
101 CHECK_GT(window_size_, 0);
102}
103
104inline void RunningAverage::Reset(int window_size) {
105 window_size_ = window_size;
106 num_adds_ = 0;
107 global_sum_ = 0.0;
108 ClearWindow();
109}
110
111inline void RunningAverage::Add(int value) {
112 ++num_adds_;
113 global_sum_ += value;
114 local_sum_ += value;
115 values_.push_back(value);
116 if (values_.size() > window_size_) {
117 local_sum_ -= values_.front();
118 values_.pop_front();
119 }
120}
121
122inline double RunningAverage::GlobalAverage() const {
123 return num_adds_ == 0 ? 0.0 : global_sum_ / static_cast<double>(num_adds_);
124}
125
126inline double RunningAverage::WindowAverage() const {
127 return values_.empty() ? 0.0
128 : local_sum_ / static_cast<double>(values_.size());
129}
130
132 local_sum_ = 0.0;
133 values_.clear();
134}
135
136inline bool RunningAverage::IsWindowFull() const {
137 return values_.size() == window_size_;
138}
139
140template <class Number>
142 : window_size_(window_size), values_(), last_index_(0), max_index_(0) {
143 DCHECK_GT(window_size, 0);
144}
145
146template <class Number>
148 if (values_.size() < window_size_) {
149 // Starting phase until values_ reaches its final size.
150 // Note that last_index_ stays at 0 during this phase.
151 if (values_.empty() || value >= GetCurrentMax()) {
152 max_index_ = values_.size();
153 }
154 values_.push_back(value);
155 return;
156 }
157 // We are in the steady state.
158 DCHECK_EQ(values_.size(), window_size_);
159 // Note the use of >= instead of > to get the O(1) behavior in presence of
160 // many identical values.
161 if (value >= GetCurrentMax()) {
162 max_index_ = last_index_;
163 values_[last_index_] = value;
164 } else {
165 values_[last_index_] = value;
166 if (last_index_ == max_index_) {
167 // We need to recompute the max.
168 // Note that this happens only if value was strictly lower than
169 // GetCurrentMax() in the last window_size_ updates.
170 max_index_ = 0;
171 Number max_value = values_[max_index_];
172 for (int i = 1; i < values_.size(); ++i) {
173 if (values_[i] > max_value) {
174 max_value = values_[i];
175 max_index_ = i;
176 }
177 }
178 }
179 }
180 if (++last_index_ == window_size_) {
181 last_index_ = 0;
182 }
183}
184
185template <class Number>
187 DCHECK(!values_.empty());
188 return values_[max_index_];
189}
190
191} // namespace operations_research
192
193#endif // OR_TOOLS_UTIL_RUNNING_STAT_H_
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
int64 value
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...