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

Question

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

Answer 1

我想你可以使用 Reservoir sampling从流 S 中均匀地选择 k 元素，然后用这些 k 的第 x 个百分位数近似 S 的第 x 个百分位数> 数字。 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 都有一个很好的近似值，目前我不明白为什么它不适合你的情况。