如何近似未知数量的第x百分位数

最近遇到了关于如何找到给定数字流的第x百分位数的问题。如果数据流相对较小（可以存储到内存中，排序并且可以找到第x个值），我对此有基本的了解，但是我想知道如果数字流相当公平，百分比是如何近似的数量众多，数量未知。如何近似未知数量的第x百分位数

来源

2017-08-30 Bruce

我不认为你可以做这个没有存储数字（不一定在内存中）。 – Henry

你知道这些值的粗略分布吗？还是硬性限制？ –

不，没有明确的数字分布范围之外的值的分布。这些值基本上是服务器的响应时间，因此已经声明某些响应时间可能会出现轻微乱序（但可能会丢弃太乱的响应）。 – Bruce

我认为你可以使用Reservoir sampling选择从流S均匀k的元素，然后近似的S第x百分位与这些k号码的第x个百分点。 k取决于您有多少内存以及近似值应该如何精确。

EDIT

下面是一个代码示例来测试溶液：

// 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);

结果是：

近似百分位数：29

再人位数：29

我得到了一个很好的近似每x我所用，目前我不明白为什么它不适合你的情况。

来源

2017-08-30 15:41:46

因此，我目前正在尝试使用存储到数组列表中的选定元素进行油藏采样。但是，似乎这个近似值与期望的第x百分位差距仍然很远。所以，我想知道数据结构的变化是否可能会进一步优化呢？此外，流元素是响应时间等，尽管某些响应时间可能不符合顺序;他们通常是有点排序的顺序，并且可能会丢弃太乱的响应。知道这一点，是否有一个不同的采样算法，这样会更好？ – Bruce

@布鲁斯，我已经添加了一个代码示例的答案。目前我看不出为什么这个近似不适合你。也许你可以提供一个流的例子？ –

如何近似未知数量的第x百分位数

回答

相关问题