Estruturas de dados probabilísticas

Tradicionalmente na programação pensamos nos 0s e 1s como sendo infalíveis; ou é ou não é, e a não ser por possíveis raios cósmicos que afetem a memória RAM (acontece) não há muita margem pra incerteza. É um dos atrativos dos computadores: nossa memória é falível, mas a deles não. Nós podemos errar uma soma, mas eles não.

Mas e se pudéssemos trocar um pouco da infalibilidade por bastante performance? Em alguns casos, podemos! São as chamadas estruturas de dados probabilisticas, e são ferramentas muito úteis em casos específicos. Nesse post vou mostrar duas delas e citar alguns exemplos de aplicações.

Bloom filters

O bloom filter é uma estrutura de dados probabilística que serve pra verificar rapidamente e eficientemente se um elemento pertence a um conjunto ou não.

Manter em memória todos os elementos e percorrer esse vetor procurando um dado elemento pra determinar se ele já foi visto ou não, por exemplo, é bastante ineficiente pra um vetor grande porque

  1. Seria necessária muita memória pra armazenar tudo
  2. Seria necessário percorrer o vetor até encontrar o elemento, ou no caso de ele não estar presente, ir até o final do vetor.

O bloom filter contorna esses problemas e consegue proporcionar uma verificação de se um elemento pertence um conjunto usando uma quantidade fixa de memória e de modo muito mais rápido e eficiente. Em termos de complexidade, transforma uma operação O(n) em O(1). Quer dizer, a velocidade da operação independe do tamanho do conjunto.

A estrutura suporta somente duas operações:

  • Adicionar elemento ao conjunto
  • Verificar se um elemento está contido no conjunto

Ele sempre vai acusar um elemento que não pertence ao conjunto; o ponto negativo, e inerente de ser uma estrutura de dados probabilística, é que ele pode gerar falsos positivos.

Assim, com um bloom filter, podemos dizer que um elemento com certeza não está contido, ou que ele possivelmente está contido em um conjunto.

Também não é possível saber quantos elementos estão no conjunto, e nem remover um elemento depois que ele foi inserido (mas esse último ponto pode ser remediado usando um counting bloom filter, versão um pouco diferente da mesma estrutura).

Mas de quanto é esse ganho de eficiência, e qual é a taxa de possíveis erros? Os parâmetros são customizáveis, e tudo é questão de escolha de prioridades. Um bloom filter otimizado com 0.1% de erro (falsos positivos) requer por volta de 14.4 bits de memória por elemento, independente do tamanho das entradas.

Quer dizer, se previrmos um conjunto de 10k elementos e quisermos essa taxa de erro de 0.1%, temos que separar em memória 18 kB.

Exemplo de aplicação: Os navegadores, como o Chrome, têm uma funcionalidade que alerta os usuários quando estão prestes a acessar um site malicioso (que seja conhecido por conter links para vírus, por exemplo). Não seria prático ter uma lista completa dos sites perigosos, porque ela ocuparia muito espaço, e também não é conveniente ao usuário do navegador que a cada página acessada o navegador pergunte pra algum servidor do Google se o site é perigoso ou não.

Solução: o navegador vem com um filtro de bloom pre-programado. Ao acessar um site, é feita uma verificação de se o endereço é contido no filtro; a resposta é "esse site certamente não está na lista de sites malicioso" (não está contido no filtro) ou "esse site possivelmente está na lista de sites maliciosos" (está contido, mas pode ser um falso-positivo). No primeiro caso, que acontece na maioria das vezes, a navegação continua normalmente; no segundo caso, o endereço é enviado pro Google pra que ele determine se aquele site realmente está ou não na lista de sites perigosos, para então perguntar ao usuário se ele quer continuar mesmo sabendo dos riscos.

HyperLogLog

O HyperLogLog é uma estrutura de dados probabilística que auxilia na contagem de elementos únicos. Assim, tem duas operações possíveis:

  • Adicionar elemento à contagem
  • Obter número aproximado de contagem

Como você já deve imaginar, ele é muito eficiente na contagem de elementos únicos (muito mais do que guardar cada elemento, verificando se ele já existe num conjunto antes de adicionar 1 à contagem), com a ressalva de que a contagem não é exata, principalmente pra números baixos.

Quão mais eficiente é o HyperLogLog do que o jeito menos sofisticado? O algoritmo consegue estimar contagens além de 10^9 (um bilhão de elementos únicos) com 2% de erro usando 1.5 kb de memória.

Como no caso do bloom filter, é possível ajustar o consumo de memória pra ser maior ou menor, aumentando ou diminuindo a precisão conforme suas necessidades.

Não é possível retirar elementos, mas é possível somar duas contagens diferentes.

Exemplo de aplicação: o Reddit é um site com vários "fóruns" dividido em tópicos, e conta quantas visualizações de usuários cada tópico teve. Mas existem muitos tópicos e muitos usuários, e a contagem tem que ser única; quer dizer, um mesmo usuário não deve ser contado duas vezes, o que elimina a possibilidade de um simples count += 1 quando a página é acessada.

Solução: HyperLogLog pra contar aproximadamente quantas visualizações um tópico teve, usando espaço limitado e de modo muito eficiente. A contagem não precisa ser exata, só dar uma boa ideia de quão popular um tópico é.

Como usar

As estruturas descritas são algoritmos; quer dizer, são jeitos de fazer as coisas. Pra cada linguagem, provavelmente existem uma ou mais implementações desses e outros algoritmos distribuidos em bibliotecas diferentes. Por exemplo, pro Python existe uma biblioteca chamada hyperloglog que implementa o algoritmo. As ideias podem ser aplicadas a qualquer tipo de linguagem!

Palavras finais

Como tantas coisas na engenharia de software, as estruturas de dados probabilísticas são uma ferramenta que tem suas vantagens e desvantagens, e é legal saber que existem.

Também recomendo pesquisar sobre os algoritmos pra entender como funcionam; tive que me controlar pra não tentar descrever isso nesse post (ia ficar muito grande), mas são muito interessantes e até simples de entender apesar do poder que têm. São bons exemplos de como pensar fora da caixa pra resolver um problema complexo, e essa qualidade é muito valiosa em um desenvolvedor.

Dois posts excelentes que descrevem o funcionamento desses dois algoritmos usando analogias a situações da vida real:

https://odino.org/my-favorite-data-structure-hyperloglog/

https://odino.org/bloom-filters-when-data-structures-get-smart/

Show Comments

Get the latest posts delivered right to your inbox.