Desenvolvimento de um novo algoritmo de contagem eficiente
Introdução
- Imagine que você está monitorando animais selvagens em uma floresta primária.
- Você tira fotos dos animais com uma câmera digital e quer saber quantos animais não repetidos existem.
- Os métodos existentes exigem lembrar e comparar todos os animais, mas isso é ineficiente.
Situação do problema
- Em plataformas de grande escala como o Facebook, é difícil contar o número de usuários únicos que fazem login todos os dias.
- Recentemente, cientistas da computação propuseram um novo método para estimar o número de itens distintos em listas longas.
- Esse algoritmo precisa lembrar apenas de um pequeno número de itens.
Algoritmo CVM
- O algoritmo CVM é um passo importante para resolver o problema dos elementos distintos, estudado há mais de 40 anos.
- Esse algoritmo consegue estimar com eficiência o número de elementos distintos em um fluxo de dados.
- "O novo algoritmo é surpreendentemente simples e fácil de implementar" - Andrew McGregor
Exemplo: audiolivro de Hamlet
- Hamlet tem 30.557 palavras. Para descobrir quantas delas são únicas, seria preciso lembrar de todas as palavras.
- O algoritmo CVM usa randomização para reduzir o uso de memória.
Como o algoritmo CVM funciona
- Primeira rodada: registra 100 palavras e, para palavras duplicadas, remove algumas com cara ou coroa.
- Segunda rodada: para tornar mais difícil manter palavras duplicadas, são necessários dois lançamentos de moeda.
- Terceira rodada: são necessários três lançamentos de moeda.
- O processo se repete até a k-ésima rodada para estimar o número de palavras únicas.
Verificação da precisão
- A precisão varia de acordo com o tamanho da memória.
- O número de palavras únicas em Hamlet é 3.967; com memória de 100 itens, a estimativa média é 3.955, e com memória de 1.000 itens, a estimativa média é 3.964.
Conclusão
- "Mesmo para problemas fundamentais e bem estudados, existem soluções simples, mas contraintuitivas" - William Kuszmaul
Opinião do GN⁺
- Útil em cenários de streaming de dados: o algoritmo CVM consegue estimar com eficiência itens distintos em grandes fluxos de dados, sendo útil para análises em tempo real.
- Eficiência de memória: ele pode manter alta precisão minimizando o uso de memória, o que é especialmente vantajoso em ambientes com restrições de memória.
- Importância da randomização: o fato de a randomização permitir resolver um problema complexo de forma simples sugere grande potencial de aplicação em outras áreas.
- Pontos a considerar na adoção da tecnologia: ao adotar esse algoritmo, é preciso considerar o equilíbrio entre tamanho de memória e precisão. Se a memória não for suficiente, a precisão pode cair.
- Tecnologias relacionadas: vale a pena compará-lo com outros algoritmos de estimativa de elementos distintos, como o HyperLogLog. É importante entender os prós e contras de cada algoritmo para escolher a melhor solução para cada situação.
1 comentários
Comentários do Hacker News
Resumo dos comentários do Hacker News
Algoritmo semelhante ao HyperLogLog
Explica um algoritmo semelhante ao HyperLogLog usando sequências de lançamentos de moeda. Ele funciona de forma especialmente eficiente em dados de streaming e usa pouca memória.
Apontamento de erro na explicação do algoritmo
Aponta que a explicação do algoritmo está errada e apresenta o método correto por meio de um exemplo de código. A abordagem de armazenar a palavra primeiro e depois removê-la produz resultados mais precisos.
Recomendação do artigo
Menciona que o artigo é tão fácil de ler quanto o post do blog e oferece mais informações. Ele explica um algoritmo simples para estimar a cardinalidade de conjuntos em dados de streaming.
Exemplo de implementação em Python
Fornece um exemplo de implementação em Python de um algoritmo de streaming. Com código simples, é possível entender e praticar o algoritmo.
Útil para refatoração de sistemas
Menciona que está refatorando um sistema que conta visitas inserindo contagens em uma tabela, e que esse método parece uma alternativa interessante à abordagem com HyperLogLog.
Método eficiente em memória
Afirma que cientistas da computação inventaram uma forma eficiente em memória de estimar o tamanho de subconjuntos.
Discussão sobre o Chernoff Bound
Discute uma variação do Chernoff Bound usada no artigo. Diz que não tem certeza se essa variação compromete a correção da prova.
Diferença entre estimar elementos únicos e contar
Observa que estimar o número de elementos únicos e realmente contar são coisas bem diferentes, e aponta que o título é inadequado.
Introdução a algoritmos de stream eficientes
Apresenta um algoritmo eficiente e fácil de implementar para encontrar os top k itens em um stream. Recomenda o artigo de Karp, Shenker & Papadimitriou.
Importância do pensamento criativo
Diz que gosta de exemplos de "pensar fora da caixa" e enfatiza que é importante encontrar a pergunta certa para resolver um problema. Espera conseguir internalizar e aplicar esse tipo de pensamento criativo por meio de vários exemplos.