Reservoir sampling: uma amostra uniforme de um fluxo de tamanho desconhecido

Objetivo

Selecionar k itens de forma uniformemente aleatória a partir de uma sequência cujo tamanho só se conhece quando ela termina, numa única passagem e com uso de memória independente do tamanho: por exemplo, amostrar linhas de log para inspeção, escolher linhas de uma exportação grande ou obter exemplos para um relatório sem carregar tudo na memória.

Pré-requisitos

Um gerador de números pseudoaleatórios com uma função de inteiros uniformes. O módulo random do Python, que a documentação descreve como baseado no Mersenne Twister, é adequado para amostragem estatística; a mesma documentação avisa que não deve ser usado para fins de segurança, por isso use secrets quando for preciso impedir que um adversário preveja a amostra. O fluxo é lido uma só vez; os k itens cabem na memória.

Passos

1. Guarde os primeiros k itens numa lista, o reservatório.
2. Para cada item seguinte, numerado como i (contando a partir de 1), sorteie um inteiro j uniformemente entre 1 e i. Se j for no máximo k, sobrescreva a posição j do reservatório com o item; caso contrário, descarte o item.
3. Quando o fluxo terminar, o reservatório é a amostra. A ordem das posições não tem significado; embaralhe-o se a ordem importar mais adiante.
4. Verifique que a amostra é uniforme. O item i entra com probabilidade k/i. Um item que já está no reservatório sobrevive à chegada do item t com probabilidade 1 - 1/t = (t-1)/t. O produto das probabilidades de sobrevivência para t de i+1 a n telescopa para i/n, e (k/i) * (i/n) = k/n, o mesmo valor para todos os itens, incluindo os k primeiros, que entram com probabilidade 1 e sobrevivem com probabilidade k/n.
5. Caso especial k = 1: substitua a única posição com probabilidade 1/i.
6. Teste com um fluxo pequeno, por exemplo 10 itens e k = 3, repetindo o procedimento muitas vezes e verificando que a frequência de inclusão de cada item se aproxima de 0,3; teste também que o código nunca pede o tamanho do fluxo.
7. Fixe a semente do gerador nos testes para garantir reprodutibilidade e registre a semente em produção, para que uma amostra reportada possa ser regenerada.

Resultado esperado

Todos os itens estão na amostra com probabilidade exatamente k/n, com um sorteio aleatório por item e memória proporcional a k, sem nunca precisar do tamanho do fluxo.

Limites e base de verificação

A amostra é uniforme sobre os itens, não sobre o tempo nem sobre os bytes; um fluxo com picos de atividade é amostrado por contagem de itens. Vários fluxos paralelos exigem que os seus reservatórios sejam combinados com pesos proporcionais ao número de itens de cada um. Existem variantes ponderadas e variantes que saltam itens para economizar sorteios aleatórios, que não são tratadas aqui. A correção decorre da aritmética do passo 4; não se afirma nenhuma medição.