ottenere la media, p95 e p99 di un flusso di dati

Question

Ho dati in entrata e voglio calcolare la media, il 95 ° e il 99 ° percentile di tali dati - Sono più interessato agli ultimi 1000 valori. In qualsiasi momento, vorrei interrogare questo oggetto per ottenere uno dei tre valori (questo può verificarsi in qualsiasi momento, non solo quando i numeri visti mod 1000 è 0). C'è un modo per ottenere questi tre valori senza tenere gli ultimi 1000 campioni?

Questo non deve essere perfetto, quindi possiamo usare alcuni trucchi per ottenere una buona stima. Inoltre, la velocità è un'altra preoccupazione. Grazie

(che cercherò di fare questo in C++, ma non credo che le cose più di tanto)

Answer 1

Come minimo, avrete bisogno di mantenere una coda delle più recenti 1000 elementi.

Per mantenere una media corrente, mantenere un totale parziale degli ultimi 1000 elementi; quando aggiungi un nuovo elemento alla coda, aggiungi il suo valore al totale e sottrai anche il valore dell'elemento più vecchio che hai appena rimosso dalla coda. Restituisci il totale diviso per 1000 e lì vai.

Per mantenere un N ° percentile in esecuzione, mantenere due heap e mantenere un conteggio degli elementi negli heap; l'heap "inferiore" ha il N% inferiore dei valori e l'heap "superiore" ha il valore superiore (1-N)% (ad esempio, l'heap del 95 ° percentile inferiore avrà 950 elementi e l'heap del 5 ° percentile superiore sarà avere 50 elementi). In qualsiasi momento puoi restituire l'elemento più basso dall'heap superiore, e questo è il tuo percentile. Quando rimuovi un elemento dalla coda dei valori recenti, rimuovi anche il valore dagli heap. Se questo lascia gli heap non bilanciati (ad esempio l'heap inferiore ha 951 elementi e l'heap superiore ha 49 elementi), quindi sposta gli elementi per bilanciarli (ad esempio rimuovi l'elemento superiore dall'heap inferiore e lo aggiunge all'heap superiore).

Poiché si desiderano due percentili, utilizzare tre heap: l'heap inferiore ha i 950 elementi inferiori, il centro ha i successivi 40 e quello superiore ha i 10 più alti. Restituisce l'elemento più basso dell'heap centrale per il 95 ° percentile e l'elemento più basso dell'heap superiore per il 99 ° percentile.

L'aggiunta e la rimozione di elementi heap è O (lg (n)), quindi è il costo dell'aggiunta di un nuovo elemento alla coda e tre heap: rimuovere l'elemento di coda più vecchio dagli heap (O (lg (n)), aggiungi il nuovo elemento di coda all'heap appropriato (O (lg (n)) e bilancia gli heap se necessario (di nuovo, O (lg (n)). Aggiungi il nuovo elemento all'heap più basso il cui elemento più alto è maggiore l'elemento mucchio, vale a dire

if (newElement < lowestHeap.maxElement) { 
    lowestHeap.add(newElement) 
} else if (newElement < middleHeap.maxElement) { 
    middleHeap.add(newElement) 
} else { 
    highestHeap.add(newElement) 
} 

assicurarsi che le cumuli consentono elementi duplicati

Answer 2

Prima supponiamo che può permettersi di memorizzare 1000 numeri (diciamo k volte 1000, dove k è una costante)

Tenere 3 cumuli:

1. Un minheap per memorizzare 10 (o 50) elementi (heapA)
2. Un maxheap per memorizzare rimanenti 990 (o 950 elementi) (heapB)
3. A minheap a mantenere l'ordine degli elementi. L'elemento più vecchio è sempre in cima a questo heap di heap C)

I tre heap sono speciali: heapC mantiene anche un collegamento all'elemento corrispondente in heapA o heapB. heapA e heapB tengono traccia dello stesso elemento in heapC.

Questo è il modo in cui funziona:

1. Si supponga di avere 1000 elementi del sistema. heapA ha 10 elementi, heapB 990 e heapC ha 1000 elementi
2. Elimina l'elemento più vecchio dal sistema. Eliminalo da heapC e utilizzando il link cancellalo da heapA o heapB
3. Riequilibrare i tre heap.
4. Aggiungere l'ordine del nuovo elemento in heapA o heapB in base alla parte superiore dell'heapA
5. Aggiungere l'ordine dell'elemento all'heapC.
6. Mentre si esegue questa operazione, aggiungere anche collegamenti tra loro.