Estruturas de Dados Probabilísticas

No items found.
20/11/2020
Rodrigo Sene
Rodrigo Sene
Engenheiro de Software Senior

Desenvolvedor entusiasmado, busco sempre aprender mais e compartilhar para tentar tornar todos ao meu redor mais empolgados com tecnologia.

Está sem tempo para ler? Aperte o play para escutar o artigo.

Como os engenheiros de softwares tomam decisões? Com a evolução das tecnologias e principalmente a facilidade do acesso à internet por milhões de pessoas, a quantidade de dados gerados aumenta exponencialmente e rapidamente. Engenheiros de softwares encaram desafios cada vez mais complexos, baseando decisões em bases de dados com centenas de milhões de informações. Para ajudar a manter os softwares performáticos, várias ferramentas e técnicas ganharam força. Entre elas, o uso de estruturas de dados probabilísticas.

O que é uma estrutura de dados?

Antes de entendermos estruturas de dados probabilísticas precisamos entender o que são estruturas de dados e por que as utilizamos.

Ao tomar a decisão de como manusear um dado, o engenheiro de software precisa se basear em algumas características, como a facilidade de acesso ao dado, o custo para manter o dado acessível e a facilidade de manuseio do dado pelo desenvolvedor.

Dados sendo jogados em uma mesa de madeira

Como organizar os dados em memória?

Existem várias formas de armazenar esses dados. Por exemplo, os dados podem ser armazenados em fitas. Elas oferecem muito espaço e são baratas, porém o acesso do desenvolvedor a esses dados não é algo simples. Também podemos utilizar o HDD, que é bem mais fácil para manter o acesso aos dados pelo desenvolvedor, por meio de um banco de dados, por exemplo, e o custo não é tão elevado. No geral, junto ao SSD, essas são as opções utilizadas na maior parte das aplicações. 

No entanto, existem tomadas de decisões que precisam de uma velocidade ainda maior para acessar os dados e, para isso, é utilizada a memória do computador. Contudo, a memória tem um custo muito elevado e, por isso, pouco espaço disponível. Cada um desses tipos de memória precisa ter os dados organizados para serem armazenados. É para isso que existem estrutura de dados. Cada estrutura de dados tem suas características que possibilitam organizar, acessar, incluir e deletar novos dados, e cada estrutura de dados faz isso de maneira própria e com custos distintos. Isso as torna excelentes para determinados tipos de problemas e não tão boas para outros. Você pode entender mais sobre estrutura de dados e suas características aqui:

Em suma, os dados em memória são a forma mais rápida e simples para que o desenvolvedor utilize os dados para tomar decisões. Porém o seu custo é alto, o que torna sua disponibilidade menor. Uma vez que verificamos isso, como podemos utilizar esse espaço limitado da melhor maneira possível?

O que são estruturas de dados probabilísticas?

Como desenvolvedor, você deve estar habituado a estruturas de dados em memória, como: listas, sets, maps, filas, entre outros. Essas estruturas são chamadas de estruturas de dados determinísticas, pois cada operação realizada retorna um resultado determinístico, ou seja, uma resultado preciso. Para obter esse resultado preciso, essas estrutura necessitam de utilizar mais memória para organizar os dados. Estruturas de dados probabilísticas trabalham de uma forma diferente: seu objetivo não é ter um resultado preciso, mas sim um resultado aproximado, isto é, uma estrutura de dados probabilística pode não retornar a resposta definitiva.

O ponto é que, por não ter a necessidade de serem precisas, estruturas de dados probabilísticas utilizam quantidades muito menores de memória para processar grandes bases de dados.

Elas permitem responder perguntas como: 

É possível que esse elemento exista dentro desta coleção de dados?

Qual a frequência aproximada dos elementos dentro da coleção de dados?

Quantos elementos distintos existem aproximadamente nesta coleção de dados?

Estruturas de dados probabilísticas podem responder perguntas desse tipo com custos bem menores que estruturas de dados determinísticas.

Estruturas de dados probabilísticas utilizam funções hash em seu core. Quanto mais apuradas forem essas funções, menor será a probabilidade de erro, porém mais memória será utilizada, o que torna o uso de memória inversamente proporcional à margem de erro.

Outra característica importante é que uma estrutura de dados probabilística tradicional nunca irá retornar um falso negativo, porém falsos positivos são aceitos. Por exemplo, caso você pergunte a uma estrutura probabilística se existe determinado elemento dentro da sua coleção de dados, essa estrutura nunca irá retornar que não existe, caso o elemento esteja presente. No entanto, podem existir casos em que a estrutura retorne que o elemento esteja presente quando não está. Por isso existe a margem de erro.

Estruturas de dados probabilísticas estão ganhando cada vez mais espaço dentro de grandes players do mercado que veem soluções para trazer economia de custos com memória, principalmente no ambiente cloud, além de produzir ganhos significativos em processos de inicialização de aplicações. A quantidade de dados a serem processados está crescendo cada vez mais e é necessário trazer soluções para os desafios.

Assim como estrutura de dados determinísticas, existem vários tipos de estruturas de dados probabilísticas, cada uma com suas características e utilidades em diferentes cenários. Nos próximos posts, apresentarei algumas, explicando seu funcionamento com mais detalhes.

Diagrama comparativo do uso de memória para determinadas ações em uma coleção de dados controlada.
Diagrama comparativo do uso de memória para determinadas ações em uma coleção de dados controlada.

Bibliografia

https://www.geeksforgeeks.org/introduction-to-the-probabilistic-data-structure/

https://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/

https://bravenewgeek.com/stream-processing-and-probabilistic-methods/


O que você achou deste conteúdo?
Quer receber nossos conteúdos?
Seu cadastro foi efetuado com sucesso! Enviaremos as novidades no seu email.
Oops! Something went wrong while submitting the form.