Comment approcher le xième percentile pour une grande quantité inconnue de nombre

Question

Vous avez récemment rencontré cette question sur la façon de trouver le xe percentile pour un flux de nombres donné. J'ai une compréhension de base de la façon dont cela pourrait être réalisé si le flux était relativement petit (peut être stocké dans la mémoire, trié et la xième valeur peut être trouvée) mais je me demandais comment le percentile pourrait être approximé si le flux de nombres grand et le nombre de nombres est inconnu.

Answer 1

Je pense que vous pouvez utiliser pour sélectionner Reservoir sampling uniformément k éléments du flux S puis approximativement percentile Xème S avec le percentile xième de ces chiffres k. k dépend de la quantité de mémoire que vous avez et de la précision de l'approximation.

---

EDIT

Voici un exemple de code pour tester la solution:

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

Le résultat est:

percentile approximative: 29

Re al percentile: 29

je me suis assez bonne approximation une pour chaque x i utilisé et actuellement je ne vois pas pourquoi il ne peut pas être adapté à votre cas.