如何近似未知數量的第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百分位數

回答

相關問題