如何估算大量未知数的第 x 个百分位数

Question

最近遇到了关于如何找到给定数字流的第 x 个百分位数的问题。如果流相对较小（可以存储到内存中，排序并可以找到第 x 个值），我对如何实现这一点有一个基本的了解，但我想知道如果数字流相当大，如何近似百分位数大，数量未知。

Answer 1

我认为你可以统一使用 Reservoir sampling 到 select k 流 S 中的元素，然后用 xth 近似 S 的第 xth 个百分位数这些 k 个数字的百分位数。 k 取决于您有多少内存以及近似值的精确度。

编辑

下面是一个代码示例来测试解决方案：

// create random stream of numbers
Random random = new Random(0);
List<Integer> stream = new ArrayList<Integer>();
for (int i = 0; i < 100000; ++i) {
    stream.add((int) (random.nextGaussian() * 100 + 30));
}
// get approximate percentile
int k = 1000; // sample size
int x = 50; // percentile
// init priority queue for sampling
TreeMap<Double, Integer> queue = new TreeMap<Double, Integer>();
// sample k elements from stream
for (int val : stream) {
    queue.put(random.nextDouble(), val);
    if (queue.size() > k) {
        queue.pollFirstEntry();
    }
}
// get xth percentile from k samples
List<Integer> sample = new ArrayList<Integer>(queue.values());
Collections.sort(sample);
int approxPercent = sample.get(sample.size() * x / 100);
System.out.println("Approximate percentile: " + approxPercent);
// get real value of the xth percentile
Collections.sort(stream);
int percent = stream.get(stream.size() * x / 100);
System.out.println("Real percentile: " + percent);

结果是：

Approximate percentile: 29

Real percentile: 29

我对我使用的每个 x 都有一个很好的近似值，目前我不明白为什么它不适合你的情况。

如何估算大量未知数的第 x 个百分位数

How to approximate the xth percentile for a large unknown quantity of number

algorithm

approximation

sampling

percentile