Nossa página inicial de vídeos agora mostra um novo conjunto de 24 recomendações a cada atualização, graças à mudança para amostragem de reservatório ponderada (A-Res). A mudança eliminou o problema do "mesmo-grid-para-sempre" que assolava nosso feed anterior ordenado por pontuação.

Por que a abordagem antiga prejudicava a experiência

A cada duas horas, buscamos os vídeos em alta mais recentes de oito regiões e despejamos os resultados em uma tabela SQLite. A solução ingênua era ordenar o conjunto inteiro — por uma pontuação de relevância — e pegar os 24 primeiros. Esse método garante que os itens com as maiores pontuações apareçam, mas também garante que eles permaneçam lá. Um único clipe viral pode dominar a posição 1 por dias, e os usuários veem uma grade idêntica toda vez que recarregam a página.

Além da experiência estagnada, ordenar a tabela inteira para cada requisição força o SQLite a carregar uma grande estrutura temporária na memória, o que é um desperdício.

O que a amostragem de reservatório ponderada nos proporciona

A amostragem de reservatório ponderada resolve dois problemas de uma só vez:

  1. Novidade com viés – a chance de cada vídeo ser selecionado é proporcional ao seu peso (ex: pontuação de relevância). Um vídeo com o dobro do peso tem duas vezes mais chances de aparecer, mas nenhum item tem uma vaga garantida.
  2. Eficiência de memória – o algoritmo mantém apenas um "reservatório" de tamanho fixo de k itens (k = 24 para o nosso feed). Ele processa o fluxo em uma única passagem, portanto, a memória permanece O(k), independentemente de quantos candidatos cheguem.

A ideia central é simples. Conforme percorremos as linhas recebidas, atribuímos a cada item uma chave aleatória que incorpora seu peso e, em seguida, retemos os k itens com as maiores chaves.

O algoritmo na prática

Para cada vídeo, nós:

  1. Sorteamos um número aleatório uniforme u ∈ (0, 1).
  2. Calculamos uma chave k = u^(1/weight).
    (Quanto maior o peso, maior será a chave esperada.)
  3. Inserimos o item em um min-heap que armazena as k maiores chaves atuais.
    Se o heap exceder o tamanho k, descartamos a menor chave.

Quando o fluxo termina, o heap contém os 24 vídeos que exibiremos.

Lidando com limites de ponto flutuante

Quando o peso de um vídeo é muito grande, u^(1/weight) colapsa para um valor indistinguível de 1.0 em aritmética de precisão dupla, fazendo com que muitos itens pesados compartilhem a mesma chave e percam a aleatoriedade. A solução é trabalhar no espaço logarítmico:

  • Calcule log_key = log(u) / weight em vez da expressão de potência.

Como os logaritmos transformam exponenciação em multiplicação, a ordenação das chaves é preservada, evitando o declínio de precisão. O cálculo não custa praticamente nada extra.

Checklist de implementação

  • Estrutura de dados: um min-heap (fila de prioridade) de tamanho k mantém as maiores chaves de forma eficiente (O(log k) por inserção).
  • Tipo numérico: use números de ponto flutuante de 64 bits para u e para as chaves baseadas em log; eles fornecem precisão ampla para faixas de peso típicas.
  • Verificação estatística de sanidade: execute um teste rápido de Monte Carlo em um pequeno conjunto de amostras. Se itens com peso 10 aparecerem aproximadamente dez vezes mais do que itens com peso 1, a implementação está correta.
  • Streaming de passagem única: o algoritmo não precisa saber o número total de candidatos com antecedência, o que se ajusta naturalmente ao nosso cursor SQLite que fornece as linhas uma a uma.

Conclusão

A amostragem de reservatório ponderada permite que um serviço de recomendação de vídeos mantenha sua página inicial atualizada, respeite as