Como profissionais de engenharia 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. Essas pessoas encaram desafios cada vez mais complexos, tomando decisões baseadas em dados. Diante de um cenário de grande volume de dados, softwares precisam ser performáticos. Nesse momento ferramentas e técnicas vêm ganhando força. Dentre estas as 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.
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, em contextos de tomadas de decisões em tempo real, é necessário um poder de processamento mais rápido para que o dado fique disponível para uso. Uma boa alternativa seria tirar proveito da 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 estruturas 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 na seção de referências.
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,
Como dev, 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. Um fenômeno determinístico pode ser explicado como dado a ocorrência de um evento o resultado sempre será o mesmo, ou seja, torna-se um evento previsível.
No entanto, há um custo associado: essas estruturas necessitam 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 como, por exemplo, o bloom filter, é que 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.
Bibliografia
- Introduction to the Probabilistic Data Structure – GeeksforGeeks
- Probabilistic Data Structures for Web Analytics and Data Mining – Highly Scalable Blog
- Stream Processing and Probabilistic Methods: Data at Scale – Brave New Geek
