obtendo a média, p95 e p99 de um fluxo de dados - algoritmo, média, precisão, média móvel

Eu tenho dados de entrada e quero calcular omédia, 95º e 99º percentil desses dados - estou mais interessado nos últimos 1000 valores. A qualquer momento, eu "gostaria de consultar esse objeto para obter qualquer um dos três valores (isso pode ocorrer a qualquer momento, não apenas quando os números visto mod 1000 é 0). Existe uma maneira de obter esses três valores sem manter as últimas 1000 amostras?

Isso não precisa ser perfeito, então podemos usar alguns truques para obter uma boa estimativa. Além disso, a velocidade é outra preocupação.

(Eu vou fazer isso em C ++, mas eu não acho que isso importe tanto assim)

Respostas:

No mínimo, você precisará manter uma fila dos 1000 elementos mais recentes.

Para manter uma média de execução, mantenha uma corridatotal dos mais recentes 1000 elementos; quando você adiciona um novo elemento à fila, adiciona seu valor ao total e também subtrai o valor do elemento mais antigo que você acabou de remover da fila. Retorne o total dividido por 1000 e lá vai você.

Para manter um percentual de segundo, mantenha doisacumula e mantém uma contagem dos elementos nos montes; o heap "inferior" tem o menor N% dos valores, e o heap "superior" tem o superior (1-N)% (por exemplo, o heap de 95º percentil inferior terá 950 elementos e o heap de 5º percentil superior tem 50 elementos). A qualquer momento você pode retornar o elemento mais baixo do heap superior, e esse é o seu percentil. Quando você remove um elemento da fila de valores recentes, remova o valor dos heaps também. Se isso deixar os heaps desequilibrados ( Por exemplo, o heap inferior tem 951 elementos e o heap superior tem 49 elementos), em seguida, deslocar elementos para equilibrá-los (por exemplo, remover o elemento superior do heap inferior e adicioná-lo ao heap superior).

Desde que você quer dois percentis, use três pilhas -o heap inferior tem os 950 elementos mais baixos, o meio tem os próximos 40 e o superior o 10 mais alto. Retorna o elemento mais baixo do heap do meio para o 95º percentil e o elemento mais baixo do heap superior para o 99º percentil.

Adicionar e remover elementos de heap é O (lg (n)), entãoesse é o custo de adicionar um novo elemento à fila e três heaps: remova o elemento da fila mais antiga dos heaps (O (lg (n)), inclua o novo elemento queue na pilha apropriada (O (lg (n)) , e equilibre os heaps se necessário (novamente, O (lg (n)). Adicione o novo elemento ao heap mais baixo cujo maior elemento é maior que o heap, ie

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

Certifique-se de que seus heaps permitem elementos duplicados

Primeiro vamos supor que você pode armazenar 1000 números (digamos k vezes 1000, onde k é uma constante).

Mantenha 3 pilhas:

1. Um minheap para armazenar 10 (ou 50) elementos (heapA)
2. Um maxheap para armazenar 990 restantes (ou 950 elementos) (heapB)
3. Um minheap para manter a ordem dos elementos. O elemento mais antigo está sempre no topo deste heap heapC)

Os três heaps são especiais: o heapC também mantém um link para o elemento correspondente em heapA ou heapB. heapA e heapB também controlam o mesmo elemento em heapC.

É assim que funciona:

1. Suponha que você tenha 1000 elementos no sistema. heapA tem 10 elementos, heapB 990 e heapC tem 1000 elementos
2. Exclua o elemento mais antigo do sistema. Exclua-o do heapC e, usando o link, exclua-o do heapA ou do heapB
3. Reequilibrar os três montes.
4. Adicione a ordem do novo elemento ao heapA ou ao heapB, dependendo da parte superior do heapA
5. Adicione a ordem do elemento ao heapC.
6. Ao fazer isso, adicione também links uns aos outros.