从一个长数组中计算百分位数？

Question

从一个长数组中计算百分位数？

javamathstatisticsapache-commonspercentile

16

给定一个长的毫秒级延迟数组，我想从中计算百分位数。我有下面的方法可以完成这项工作，但我不确定如何验证它是否给我准确的结果？

  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。

- user5447339

1

请注意，你的percentiles方法不仅计算百分位数值（并非总是正确--请参见我的答案），并返回这些值，它还会使latencies数组排序，这是一个可能不希望出现的副作用。在你尝试编写的小程序中，这可能是无害的，但通常情况下，一个方法具有非其目的的副作用是不好的实践。 - ajb

4个回答

4

public static double percentile(double percentile, List<Double> items) {
    Preconditions.checkArgument(percentile >= 0);
    Preconditions.checkArgument(percentile <= 100);
    Preconditions.checkArgument(!items.isEmpty());

    Collections.sort(items);
    return items.get((int) Math.round(percentile / 100.0 * (items.size() - 1)));
}


@Test
public void test1() {
    List<Double> list = Arrays.asList(0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0);
    assertThat(percentile(0, list)).isEqualTo(0.0);
    assertThat(percentile(20, list)).isEqualTo(2.0);
    assertThat(percentile(80, list)).isEqualTo(8.0);
    assertThat(percentile(100, list)).isEqualTo(10.0);
}

@Test
public void test2() {
    List<Double> list = Arrays.asList(0.0, 1.0, 2.0, 3.0);
    assertThat(percentile(51, list)).isEqualTo(2.0);
    assertThat(percentile(49, list)).isEqualTo(1.0);
}

@Test
public void test3() {
    List<Double> list = Arrays.asList(42.0);     
    assertThat(percentile(0, list)).isEqualTo(42.0);
    assertThat(percentile(100, list)).isEqualTo(42.0);
}

- Zsolt Safrany

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

这不是你所写的代码。当你将一个double强制转换成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，且ceiling(2.0) = 2.0。

然而，你的代码：

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

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

因此，为了匹配维基百科的定义，您对索引的计算需要进行一些修改。(另一方面，如果有人说您的计算是正确的，而维基百科是错误的，我也不会感到惊讶。我们拭目以待...)

- ajb

0

如果数组已排序，您应该只返回数组中的相对元素（例如，在1000个元素的数组中，p99是第990个元素）。

如果数组未排序，并且为了更有效地计算百分位数，您应该使用类似Quickselect的东西。

- Moshe Bixenshpaner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user7358693 · Accepted Answer

这就是你要找的内容：

public static void main(String[] args) {
    List<Long> latencies = new List<Long>() { 3, 6, 7, 8, 8, 9, 10, 13, 15, 16, 20 };
    Collections.sort(latencies);

    System.out.println(percentile(latencies, 25));
    System.out.println(percentile(latencies, 50));
    System.out.println(percentile(latencies, 75));
    System.out.println(percentile(latencies, 100));
}

public static long percentile(List<Long> latencies, double percentile) {
    int index = (int) Math.ceil(percentile / 100.0 * latencies.size());
    return latencies.get(index-1);
}