| 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 |