OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #ifndef NET_NQE_OBSERVATION_BUFFER_H_ | 5 #ifndef NET_NQE_OBSERVATION_BUFFER_H_ |
6 #define NET_NQE_OBSERVATION_BUFFER_H_ | 6 #define NET_NQE_OBSERVATION_BUFFER_H_ |
7 | 7 |
8 #include <float.h> | 8 #include <float.h> |
9 | 9 |
10 #include <algorithm> | 10 #include <algorithm> |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
87 int percentile, | 87 int percentile, |
88 const std::vector<NetworkQualityObservationSource>& | 88 const std::vector<NetworkQualityObservationSource>& |
89 disallowed_observation_sources) const { | 89 disallowed_observation_sources) const { |
90 // Stores weighted observations in increasing order by value. | 90 // Stores weighted observations in increasing order by value. |
91 std::vector<WeightedObservation<ValueType>> weighted_observations; | 91 std::vector<WeightedObservation<ValueType>> weighted_observations; |
92 | 92 |
93 // Total weight of all observations in |weighted_observations|. | 93 // Total weight of all observations in |weighted_observations|. |
94 double total_weight = 0.0; | 94 double total_weight = 0.0; |
95 | 95 |
96 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, | 96 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, |
97 weighted_observations, &total_weight, | 97 &weighted_observations, &total_weight, |
98 disallowed_observation_sources); | 98 disallowed_observation_sources); |
99 if (weighted_observations.empty()) | 99 if (weighted_observations.empty()) |
100 return false; | 100 return false; |
101 | 101 |
102 double desired_weight = percentile / 100.0 * total_weight; | 102 double desired_weight = percentile / 100.0 * total_weight; |
103 | 103 |
104 double cumulative_weight_seen_so_far = 0.0; | 104 double cumulative_weight_seen_so_far = 0.0; |
105 for (const auto& weighted_observation : weighted_observations) { | 105 for (const auto& weighted_observation : weighted_observations) { |
106 cumulative_weight_seen_so_far += weighted_observation.weight; | 106 cumulative_weight_seen_so_far += weighted_observation.weight; |
107 | 107 |
(...skipping 24 matching lines...) Expand all Loading... |
132 const std::vector<NetworkQualityObservationSource>& | 132 const std::vector<NetworkQualityObservationSource>& |
133 disallowed_observation_sources, | 133 disallowed_observation_sources, |
134 ValueType* result) const { | 134 ValueType* result) const { |
135 // Stores weighted observations in increasing order by value. | 135 // Stores weighted observations in increasing order by value. |
136 std::vector<WeightedObservation<ValueType>> weighted_observations; | 136 std::vector<WeightedObservation<ValueType>> weighted_observations; |
137 | 137 |
138 // Total weight of all observations in |weighted_observations|. | 138 // Total weight of all observations in |weighted_observations|. |
139 double total_weight = 0.0; | 139 double total_weight = 0.0; |
140 | 140 |
141 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, | 141 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, |
142 weighted_observations, &total_weight, | 142 &weighted_observations, &total_weight, |
143 disallowed_observation_sources); | 143 disallowed_observation_sources); |
144 if (weighted_observations.empty()) | 144 if (weighted_observations.empty()) |
145 return false; | 145 return false; |
146 | 146 |
147 // Weighted average is the sum of observations times their respective | 147 // Weighted average is the sum of observations times their respective |
148 // weights, divided by the sum of the weights of all observations. | 148 // weights, divided by the sum of the weights of all observations. |
149 double total_weight_times_value = 0.0; | 149 double total_weight_times_value = 0.0; |
150 for (const auto& weighted_observation : weighted_observations) { | 150 for (const auto& weighted_observation : weighted_observations) { |
151 total_weight_times_value += | 151 total_weight_times_value += |
152 (weighted_observation.weight * | 152 (weighted_observation.weight * |
(...skipping 16 matching lines...) Expand all Loading... |
169 const std::vector<NetworkQualityObservationSource>& | 169 const std::vector<NetworkQualityObservationSource>& |
170 disallowed_observation_sources, | 170 disallowed_observation_sources, |
171 ValueType* result) const { | 171 ValueType* result) const { |
172 // Stores weighted observations in increasing order by value. | 172 // Stores weighted observations in increasing order by value. |
173 std::vector<WeightedObservation<ValueType>> weighted_observations; | 173 std::vector<WeightedObservation<ValueType>> weighted_observations; |
174 | 174 |
175 // Total weight of all observations in |weighted_observations|. | 175 // Total weight of all observations in |weighted_observations|. |
176 double total_weight = 0.0; | 176 double total_weight = 0.0; |
177 | 177 |
178 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, | 178 ComputeWeightedObservations(begin_timestamp, current_signal_strength_dbm, |
179 weighted_observations, &total_weight, | 179 &weighted_observations, &total_weight, |
180 disallowed_observation_sources); | 180 disallowed_observation_sources); |
181 if (weighted_observations.empty()) | 181 if (weighted_observations.empty()) |
182 return false; | 182 return false; |
183 | 183 |
184 // The unweighted average is the sum of all observations divided by the | 184 // The unweighted average is the sum of all observations divided by the |
185 // number of observations. | 185 // number of observations. |
186 double total_value = 0.0; | 186 double total_value = 0.0; |
187 for (const auto& weighted_observation : weighted_observations) | 187 for (const auto& weighted_observation : weighted_observations) |
188 total_value += ConvertValueTypeToDouble(weighted_observation.value); | 188 total_value += ConvertValueTypeToDouble(weighted_observation.value); |
189 | 189 |
(...skipping 29 matching lines...) Expand all Loading... |
219 // |weighted_observations| sorted by ascending |WeightedObservation.value|. | 219 // |weighted_observations| sorted by ascending |WeightedObservation.value|. |
220 // Only the observations with timestamp later than |begin_timestamp| are | 220 // Only the observations with timestamp later than |begin_timestamp| are |
221 // considered. |current_signal_strength_dbm| is the current signal strength | 221 // considered. |current_signal_strength_dbm| is the current signal strength |
222 // (in dBm) when the observation was taken, and is set to INT32_MIN if the | 222 // (in dBm) when the observation was taken, and is set to INT32_MIN if the |
223 // signal strength is currently unavailable. This method also sets | 223 // signal strength is currently unavailable. This method also sets |
224 // |total_weight| to the total weight of all observations. Should be called | 224 // |total_weight| to the total weight of all observations. Should be called |
225 // only when there is at least one observation in the buffer. | 225 // only when there is at least one observation in the buffer. |
226 void ComputeWeightedObservations( | 226 void ComputeWeightedObservations( |
227 const base::TimeTicks& begin_timestamp, | 227 const base::TimeTicks& begin_timestamp, |
228 int32_t current_signal_strength_dbm, | 228 int32_t current_signal_strength_dbm, |
229 std::vector<WeightedObservation<ValueType>>& weighted_observations, | 229 std::vector<WeightedObservation<ValueType>>* weighted_observations, |
230 double* total_weight, | 230 double* total_weight, |
231 const std::vector<NetworkQualityObservationSource>& | 231 const std::vector<NetworkQualityObservationSource>& |
232 disallowed_observation_sources) const { | 232 disallowed_observation_sources) const { |
233 DCHECK_GE(Capacity(), Size()); | 233 DCHECK_GE(Capacity(), Size()); |
234 | 234 |
235 weighted_observations.clear(); | 235 weighted_observations->clear(); |
236 double total_weight_observations = 0.0; | 236 double total_weight_observations = 0.0; |
237 base::TimeTicks now = tick_clock_->NowTicks(); | 237 base::TimeTicks now = tick_clock_->NowTicks(); |
238 | 238 |
239 for (const auto& observation : observations_) { | 239 for (const auto& observation : observations_) { |
240 if (observation.timestamp < begin_timestamp) | 240 if (observation.timestamp < begin_timestamp) |
241 continue; | 241 continue; |
242 bool disallowed = false; | 242 bool disallowed = false; |
243 for (const auto& disallowed_source : disallowed_observation_sources) { | 243 for (const auto& disallowed_source : disallowed_observation_sources) { |
244 if (disallowed_source == observation.source) | 244 if (disallowed_source == observation.source) |
245 disallowed = true; | 245 disallowed = true; |
(...skipping 12 matching lines...) Expand all Loading... |
258 int32_t signal_strength_weight_diff = std::abs( | 258 int32_t signal_strength_weight_diff = std::abs( |
259 current_signal_strength_dbm - observation.signal_strength_dbm); | 259 current_signal_strength_dbm - observation.signal_strength_dbm); |
260 signal_strength_weight = | 260 signal_strength_weight = |
261 pow(weight_multiplier_per_dbm_, signal_strength_weight_diff); | 261 pow(weight_multiplier_per_dbm_, signal_strength_weight_diff); |
262 } | 262 } |
263 | 263 |
264 double weight = time_weight * signal_strength_weight; | 264 double weight = time_weight * signal_strength_weight; |
265 | 265 |
266 weight = std::max(DBL_MIN, std::min(1.0, weight)); | 266 weight = std::max(DBL_MIN, std::min(1.0, weight)); |
267 | 267 |
268 weighted_observations.push_back( | 268 weighted_observations->push_back( |
269 WeightedObservation<ValueType>(observation.value, weight)); | 269 WeightedObservation<ValueType>(observation.value, weight)); |
270 total_weight_observations += weight; | 270 total_weight_observations += weight; |
271 } | 271 } |
272 | 272 |
273 // Sort the samples by value in ascending order. | 273 // Sort the samples by value in ascending order. |
274 std::sort(weighted_observations.begin(), weighted_observations.end()); | 274 std::sort(weighted_observations->begin(), weighted_observations->end()); |
275 *total_weight = total_weight_observations; | 275 *total_weight = total_weight_observations; |
276 | 276 |
277 DCHECK_LE(0.0, *total_weight); | 277 DCHECK_LE(0.0, *total_weight); |
278 DCHECK(weighted_observations.empty() || 0.0 < *total_weight); | 278 DCHECK(weighted_observations->empty() || 0.0 < *total_weight); |
279 | 279 |
280 // |weighted_observations| may have a smaller size than |observations_| | 280 // |weighted_observations| may have a smaller size than |observations_| |
281 // since the former contains only the observations later than | 281 // since the former contains only the observations later than |
282 // |begin_timestamp|. | 282 // |begin_timestamp|. |
283 DCHECK_GE(observations_.size(), weighted_observations.size()); | 283 DCHECK_GE(observations_.size(), weighted_observations->size()); |
284 } | 284 } |
285 | 285 |
286 // Holds observations sorted by time, with the oldest observation at the | 286 // Holds observations sorted by time, with the oldest observation at the |
287 // front of the queue. | 287 // front of the queue. |
288 std::deque<Observation<ValueType>> observations_; | 288 std::deque<Observation<ValueType>> observations_; |
289 | 289 |
290 // The factor by which the weight of an observation reduces every second. | 290 // The factor by which the weight of an observation reduces every second. |
291 // For example, if an observation is 6 seconds old, its weight would be: | 291 // For example, if an observation is 6 seconds old, its weight would be: |
292 // weight_multiplier_per_second_ ^ 6 | 292 // weight_multiplier_per_second_ ^ 6 |
293 // Calculated from |kHalfLifeSeconds| by solving the following equation: | 293 // Calculated from |kHalfLifeSeconds| by solving the following equation: |
(...skipping 13 matching lines...) Expand all Loading... |
307 DISALLOW_COPY_AND_ASSIGN(ObservationBuffer); | 307 DISALLOW_COPY_AND_ASSIGN(ObservationBuffer); |
308 }; | 308 }; |
309 | 309 |
310 } // namespace internal | 310 } // namespace internal |
311 | 311 |
312 } // namespace nqe | 312 } // namespace nqe |
313 | 313 |
314 } // namespace net | 314 } // namespace net |
315 | 315 |
316 #endif // NET_NQE_OBSERVATION_BUFFER_H_ | 316 #endif // NET_NQE_OBSERVATION_BUFFER_H_ |
OLD | NEW |