从长阵列计算百分位数？

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

我想从latencies数组获得第50,95,99和99.9百分位数.

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

考虑到一系列延迟,这是获得百分位数的正确方法吗？我正在使用Java 7.

Answer 1

这就是你要找的东西:

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];
    }
}

Answer 2

根据维基百科，百分位数没有标准定义；然而，他们给出了一些可能的定义。您发布的代码似乎最接近最近排名方法，但并不完全相同。

他们给出的公式是

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

这不完全是您编写的代码。当您将 a 转换double为 an时int，结果将向 0 舍入，即它相当于“floor”函数。所以你的代码计算

floor(percentiles[i] * latencies.length)

如果percentiles[i] * latencies.length不是整数，则无论哪种方式结果都相同。然而，如果它是一个整数，那么“floor”和“ceiling”是相同的值，那么结果就会不同。

维基百科的一个示例是当列表为 {15, 20, 35, 40, 50} 时计算第 40 个百分位。他们的答案是找到列表中的第二项，即 20，因为 0.40 * 5 = 2.0，而上限(2.0) = 2.0。

但是，您的代码：

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

将导致index为 2，这不是您想要的，因为这将为您提供列表中的第三项，而不是第二项。

因此，为了匹配维基百科的定义，您对索引的计算需要稍微修改。（另一方面，如果有人说你的计算是正确的而维基百科是错误的，我不会感到惊讶。我们会看到......）