1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
/*
* Copyright (C) 2016 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.mozilla.thirdparty.com.google.android.exoplayer2.util;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
/**
* Calculate any percentile over a sliding window of weighted values. A maximum weight is
* configured. Once the total weight of the values reaches the maximum weight, the oldest value is
* reduced in weight until it reaches zero and is removed. This maintains a constant total weight,
* equal to the maximum allowed, at the steady state.
* <p>
* This class can be used for bandwidth estimation based on a sliding window of past transfer rate
* observations. This is an alternative to sliding mean and exponential averaging which suffer from
* susceptibility to outliers and slow adaptation to step functions.
*
* @see <a href="http://en.wikipedia.org/wiki/Moving_average">Wiki: Moving average</a>
* @see <a href="http://en.wikipedia.org/wiki/Selection_algorithm">Wiki: Selection algorithm</a>
*/
public class SlidingPercentile {
// Orderings.
private static final Comparator<Sample> INDEX_COMPARATOR = (a, b) -> a.index - b.index;
private static final Comparator<Sample> VALUE_COMPARATOR =
(a, b) -> Float.compare(a.value, b.value);
private static final int SORT_ORDER_NONE = -1;
private static final int SORT_ORDER_BY_VALUE = 0;
private static final int SORT_ORDER_BY_INDEX = 1;
private static final int MAX_RECYCLED_SAMPLES = 5;
private final int maxWeight;
private final ArrayList<Sample> samples;
private final Sample[] recycledSamples;
private int currentSortOrder;
private int nextSampleIndex;
private int totalWeight;
private int recycledSampleCount;
/**
* @param maxWeight The maximum weight.
*/
public SlidingPercentile(int maxWeight) {
this.maxWeight = maxWeight;
recycledSamples = new Sample[MAX_RECYCLED_SAMPLES];
samples = new ArrayList<>();
currentSortOrder = SORT_ORDER_NONE;
}
/** Resets the sliding percentile. */
public void reset() {
samples.clear();
currentSortOrder = SORT_ORDER_NONE;
nextSampleIndex = 0;
totalWeight = 0;
}
/**
* Adds a new weighted value.
*
* @param weight The weight of the new observation.
* @param value The value of the new observation.
*/
public void addSample(int weight, float value) {
ensureSortedByIndex();
Sample newSample = recycledSampleCount > 0 ? recycledSamples[--recycledSampleCount]
: new Sample();
newSample.index = nextSampleIndex++;
newSample.weight = weight;
newSample.value = value;
samples.add(newSample);
totalWeight += weight;
while (totalWeight > maxWeight) {
int excessWeight = totalWeight - maxWeight;
Sample oldestSample = samples.get(0);
if (oldestSample.weight <= excessWeight) {
totalWeight -= oldestSample.weight;
samples.remove(0);
if (recycledSampleCount < MAX_RECYCLED_SAMPLES) {
recycledSamples[recycledSampleCount++] = oldestSample;
}
} else {
oldestSample.weight -= excessWeight;
totalWeight -= excessWeight;
}
}
}
/**
* Computes a percentile by integration.
*
* @param percentile The desired percentile, expressed as a fraction in the range (0,1].
* @return The requested percentile value or {@link Float#NaN} if no samples have been added.
*/
public float getPercentile(float percentile) {
ensureSortedByValue();
float desiredWeight = percentile * totalWeight;
int accumulatedWeight = 0;
for (int i = 0; i < samples.size(); i++) {
Sample currentSample = samples.get(i);
accumulatedWeight += currentSample.weight;
if (accumulatedWeight >= desiredWeight) {
return currentSample.value;
}
}
// Clamp to maximum value or NaN if no values.
return samples.isEmpty() ? Float.NaN : samples.get(samples.size() - 1).value;
}
/**
* Sorts the samples by index.
*/
private void ensureSortedByIndex() {
if (currentSortOrder != SORT_ORDER_BY_INDEX) {
Collections.sort(samples, INDEX_COMPARATOR);
currentSortOrder = SORT_ORDER_BY_INDEX;
}
}
/**
* Sorts the samples by value.
*/
private void ensureSortedByValue() {
if (currentSortOrder != SORT_ORDER_BY_VALUE) {
Collections.sort(samples, VALUE_COMPARATOR);
currentSortOrder = SORT_ORDER_BY_VALUE;
}
}
private static class Sample {
public int index;
public int weight;
public float value;
}
}
|
