Pick tight left-hand-side and right-hand-side bounds and then interpolate a histogram value at percentile p
| 124 | // Pick tight left-hand-side and right-hand-side bounds and then |
| 125 | // interpolate a histogram value at percentile p |
| 126 | double Histogram::Percentile(double p) const { |
| 127 | if (num_ == 0.0) return 0.0; |
| 128 | |
| 129 | double threshold = num_ * (p / 100.0); |
| 130 | double cumsum_prev = 0; |
| 131 | for (size_t i = 0; i < buckets_.size(); i++) { |
| 132 | double cumsum = cumsum_prev + buckets_[i]; |
| 133 | |
| 134 | // Find the first bucket whose cumsum >= threshold |
| 135 | if (cumsum >= threshold) { |
| 136 | // Prevent divide by 0 in remap which happens if cumsum == cumsum_prev |
| 137 | // This should only get hit when p == 0, cumsum == 0, and cumsum_prev == 0 |
| 138 | if (cumsum == cumsum_prev) { |
| 139 | continue; |
| 140 | } |
| 141 | |
| 142 | // Calculate the lower bound of interpolation |
| 143 | double lhs = (i == 0 || cumsum_prev == 0) ? min_ : bucket_limits_[i - 1]; |
| 144 | lhs = std::max(lhs, min_); |
| 145 | |
| 146 | // Calculate the upper bound of interpolation |
| 147 | double rhs = bucket_limits_[i]; |
| 148 | rhs = std::min(rhs, max_); |
| 149 | |
| 150 | double weight = Remap(threshold, cumsum_prev, cumsum, lhs, rhs); |
| 151 | return weight; |
| 152 | } |
| 153 | |
| 154 | cumsum_prev = cumsum; |
| 155 | } |
| 156 | return max_; |
| 157 | } |
| 158 | |
| 159 | double Histogram::Average() const { |
| 160 | if (num_ == 0.0) return 0; |