Рассчитать процентиль из длинного массива?

Question

Учитывая длинный массив задержек, которые находятся в миллисекундах, я хочу рассчитать процентиль от них. Я получил ниже метод, который выполняет эту работу, но я не уверен, как я могу проверить, дает ли это мне точный результат?

public static long[] percentiles(long[] latencies, double... percentiles) { 
    Arrays.sort(latencies, 0, latencies.length); 
    long[] values = new long[percentiles.length]; 
    for (int i = 0; i < percentiles.length; i++) { 
     int index = (int) (percentiles[i] * latencies.length); 
     values[i] = latencies[index]; 
    } 
    return values; 
    } 

Я хотел бы получить 50, 95-е, 99-е и 99.9-й процентили от latencies массива.

long[] percs = percentiles(latencies, 0.5, 0.95, 0.99, 0.999); 

Это правильный способ получить процентиль с учетом большого количества задержек? Я работаю с Java 7.

Answer 1

Согласно Wikipedia, стандартного определения процентили нет; однако они дают несколько возможных определений. Код, который вы опубликовали, ближе всего к методу Nearest Rank, но это не совсем то же самое.

Формулы они дают

n = ceiling((P/100) x N) 

где N длина списка, P является процентилем, и n будет порядковый рангом. Вы уже сделали разделение на 100. Глядя на примеры, которые они дают, ясно, что «порядковый ранг» является индексом в списке, но он 1-относительный. Таким образом, чтобы получить индекс в массиве Java, вы должны вычесть 1. Поэтому правильная формула должна быть

n = ceiling(percentile * N) - 1 

Использование переменных в коде, эквивалент Java будет

(int) Math.ceil(percentiles[i] * latencies.length) - 1 

Это не совсем тот код, который вы написали. Когда вы нанесете double на int, результат округляется до 0, т. Е. Это эквивалент функции «пол». Так что ваш код вычисляет

floor(percentiles[i] * latencies.length) 

Если percentiles[i] * latencies.length не является целым числом, то результат будет таким же в любом случае. Однако, если это целое число, так что «пол» и «потолок» имеют одинаковое значение, тогда результат будет другим.

Пример из Википедии - это вычисление 40-го процентиля, когда список {15, 20, 35, 40, 50}. Их ответ заключается в том, чтобы найти второй элемент в списке, т. Е. 20, потому что 0.40 * 5 = 2.0 и потолок (2.0) = 2.0.

Однако код:

int index = (int) (percentiles[i] * latencies.length); 

приведет к index быть 2, что не то, что вы хотите, потому что это даст вам третий элемент в списке, а не второй.

Так что, чтобы соответствовать определению Википедии, ваш расчет индекса нужно будет немного изменить. (С другой стороны, я не удивлюсь, если кто-то придет и скажет, что ваши вычисления верны, а Википедия ошибается. Посмотрим ...)

Answer 2

Это то, что вы ищете:

class Program 
{ 
    static void Main(string[] args) 
    { 
     List<long> latencies = new List<long>() { 3, 6, 7, 8, 8, 9, 10, 13, 15, 16, 20 }; 

     Console.WriteLine(Percentile(latencies,25)); 
     Console.WriteLine(Percentile(latencies, 50)); 
     Console.WriteLine(Percentile(latencies, 75)); 
     Console.WriteLine(Percentile(latencies, 100)); 

     Console.ReadLine(); 
    } 

    public static long Percentile(List<long> latencies, double Percentile) 
    { 
     latencies.Sort(); 
     int Index = (int)Math.Ceiling(((double)Percentile/(double)100) * (double)latencies.Count); 
     return latencies[Index-1]; 
    } 
}