Reservoir Sampling em C#: implementação e testes

Para selecionar uma amostra aleatória sem carregar todos os registros na memória, é possível manter apenas um reservatório de tamanho limitado enquanto a entrada é percorrida. A implementação abaixo usa IEnumerable<T>, trata entradas menores que a amostra e vem acompanhada de testes executáveis em C#.

Qual problema o reservatório resolve

O Algorithm R mantém até k elementos. Depois dos primeiros k, cada item disputa uma posição sorteada entre todos os itens já vistos, não apenas entre as posições do reservatório. Essa regra mantém uma amostra uniforme das posições da entrada, assumindo sorteios uniformes. A descrição e a análise estão na seção 2 de Random Sampling with a Reservoir, de Jeffrey Scott Vitter.

Isso não garante que toda categoria apareça em uma amostra particular. Se essa for a exigência, a estratégia de seleção precisa considerar os grupos explicitamente.

Implementação para uma entrada enumerável

public static class Reservoir
{
    public static List<T> Sample<T>(IEnumerable<T> source, int size, Random? random = null)
    {
        ArgumentNullException.ThrowIfNull(source);
        ArgumentOutOfRangeException.ThrowIfNegative(size);
        var sample = new List<T>();
        if (size == 0) return sample;

        random ??= Random.Shared;
        long seen = 0;
        foreach (var item in source)
        {
            seen = checked(seen + 1);
            if (sample.Count < size)
            {
                sample.Add(item);
                continue;
            }

            // Algorithm R: select a position among all items seen, not only the reservoir.
            long position = random.NextInt64(seen);
            if (position < size) sample[(int)position] = item;
        }
        return sample;
    }
}

NextInt64(seen) inclui zero e exclui seen, conforme a documentação do .NET. Se a posição sorteada não pertencer ao reservatório, o novo item não entra na amostra.

Comportamento nos limites

• Entrada nula ou tamanho negativo: exceção explícita.
• Tamanho zero: lista vazia, sem consumir a entrada.
• Entrada menor que a amostra: todos os elementos encontrados.
• Valores iguais em posições diferentes: podem aparecer juntos; o algoritmo não elimina valores duplicados.

A função lê a entrada uma vez e só retorna quando a enumeração termina. Para uma sequência infinita, seria necessário outro contrato, como uma operação que exponha a amostra corrente. Este exemplo não implementa esse comportamento nem utiliza aleatoriedade criptográfica.

Como reproduzir os testes

O pacote contém a implementação, o verificador, o projeto e a seleção do SDK. No diretório do projeto, com .NET 10 instalado, execute:

dotnet run --configuration Release

Em 9 de outubro de 2026, uma execução isolada assistida pelo Codex, com SDK 10.0.401 e runtime 10.0.12, passou nas 13 verificações. O teste do caso pequeno percorre os 12 caminhos de sorteio possíveis para quatro entradas distintas e amostra de duas; cada um dos seis subconjuntos aparece duas vezes. Também foram testados tamanho zero, entrada vazia, tamanho maior que a entrada, sorteios de limite e enumeração única.

Esses testes verificam o comportamento descrito, mas não são benchmark nem certificação estatística do gerador pseudoaleatório. Não demonstram ganho de desempenho em um sistema real.

Correção do exemplo anterior

A versão anterior recebia um array já materializado e acessava posições inexistentes quando k excedia seu comprimento. Esse erro foi reproduzido no verificador. O HTML também não escapava os tipos genéricos, prejudicando a leitura e a cópia do código. A atualização preserva a URL e a data original do artigo; não representa um teste pessoal de Anderson Damasio em produção.