apache-spark - 如何在 Apache Spark 中计算百分位数

Question

我有一个整数rdd(即RDD[Int])，我想做的是计算以下十个百分位数:[0th, 10th, 20th, .. ., 第90, 第100]。最有效的方法是什么？

Answer 1

你可以:

1. 通过 rdd.sortBy() 对数据集进行排序
2. 通过 rdd.count() 计算数据集的大小
3. 带有索引的压缩以方便百分位检索
4. 通过 rdd.lookup() 检索所需的百分位数，例如对于第 10 个百分位数 rdd.lookup(0.1 * size)

计算中位数和第 99 个百分位数:getPercentiles(rdd, new double[]{0.5, 0.99}, size, numPartitions);

在 Java 8 中:

public static double[] getPercentiles(JavaRDD<Double> rdd, double[] percentiles, long rddSize, int numPartitions) {
    double[] values = new double[percentiles.length];

    JavaRDD<Double> sorted = rdd.sortBy((Double d) -> d, true, numPartitions);
    JavaPairRDD<Long, Double> indexed = sorted.zipWithIndex().mapToPair((Tuple2<Double, Long> t) -> t.swap());

    for (int i = 0; i < percentiles.length; i++) {
        double percentile = percentiles[i];
        long id = (long) (rddSize * percentile);
        values[i] = indexed.lookup(id).get(0);
    }

    return values;
}

请注意，这需要对数据集进行排序，O(n.log(n))，并且对于大型数据集可能会很昂贵。

另一个答案建议简单地计算直方图无法正确计算百分位数:这是一个反例:一个由 100 个数字组成的数据集，其中 99 个数字为 0，其中一个数字为 1。最终得到所有 99 个 0在第一个垃圾箱中，1 在最后一个垃圾箱中，中间有 8 个空垃圾箱。