{"id":5738,"date":"2023-06-15T09:51:12","date_gmt":"2023-06-15T12:51:12","guid":{"rendered":"https:\/\/elemarjr.com\/clube-de-estudos\/?p=5738"},"modified":"2023-10-21T21:35:36","modified_gmt":"2023-10-22T00:35:36","slug":"hyperloglog-uma-solucao-eficiente-para-determinar-a-cardinalidade-de-conjuntos","status":"publish","type":"artigos","link":"https:\/\/elemarjr.com\/clube-de-estudos\/artigos\/hyperloglog-uma-solucao-eficiente-para-determinar-a-cardinalidade-de-conjuntos\/","title":{"rendered":"HyperLogLog: Uma solu\u00e7\u00e3o eficiente para determinar a cardinalidade de conjuntos"},"content":{"rendered":"\n

HyperLogLog<\/em> \u00e9 um algoritmo not\u00e1vel por sua habilidade de estimar a cardinalidade de conjuntos com alta precis\u00e3o e efici\u00eancia. Quando se fala de cardinalidade, estamos nos referindo ao n\u00famero de elementos \u00fanicos em um conjunto de dados. Em outras palavras, se estivermos analisando um conjunto de dados de visitantes de um site, a cardinalidade seria o n\u00famero de visitantes \u00fanicos que visitaram o site.<\/p>\n\n\n\n

A Cardinalidade de Conjuntos<\/h2>\n\n\n\n

A cardinalidade \u00e9 uma m\u00e9trica extremamente \u00fatil e muitas vezes crucial em diversas \u00e1reas, especialmente na an\u00e1lise de dados. No entanto, determinar a cardinalidade pode se tornar um desafio em conjuntos de dados muito grandes, onde \u00e9 impratic\u00e1vel ou mesmo imposs\u00edvel contar cada elemento \u00fanico individualmente.<\/p>\n\n\n\n

A Necessidade de uma Solu\u00e7\u00e3o Eficiente<\/h2>\n\n\n\n

\u00c0 medida que o volume de dados que lidamos continua a crescer exponencialmente, precisamos de solu\u00e7\u00f5es que possam lidar eficientemente com essa escala. A capacidade de estimar a cardinalidade de conjuntos de dados grandes de maneira eficiente e precisa \u00e9, portanto, mais importante do que nunca. E \u00e9 aqui que o HyperLogLog<\/em> entra em cena.<\/p>\n\n\n\n

O Algoritmo HyperLogLog<\/h2>\n\n\n\n

O HyperLogLog<\/em>, criado por Flajolet, Fusy, Gandouet e Meunier<\/em> em 2007, \u00e9 um algoritmo projetado especificamente para essa tarefa. Ele fornece uma maneira eficiente de estimar a cardinalidade de conjuntos de dados grandes, com um alto grau de precis\u00e3o e um uso de mem\u00f3ria consideravelmente baixo.<\/p>\n\n\n\n

Funcionamento e Componentes-chave do HyperLogLog<\/h3>\n\n\n\n

O HyperLogLog<\/em> usa um m\u00e9todo probabil\u00edstico para estimar a cardinalidade. Ele opera criando uma s\u00e9rie de “buckets”<\/em> de mem\u00f3ria, cada um dos quais armazena o maior “rank”<\/em> de um hash<\/em> observado. A cardinalidade \u00e9 ent\u00e3o estimada com base na m\u00e9dia desses ranks<\/em>.<\/p>\n\n\n\n

Exemplo de implementa\u00e7\u00e3o em C#<\/h3>\n\n\n\n
C#<\/span><\/path><\/path><\/svg><\/span>
using<\/span> System<\/span>;<\/span><\/span>\nusing<\/span> System.Collections.Generic<\/span>;<\/span><\/span>\nusing<\/span> System.Security.Cryptography<\/span>;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>HyperLogLog<\/span><\/span>\n{<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[]<\/span> buckets<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>HyperLogLog<\/span>(<\/span>int<\/span> numBuckets<\/span>)<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>buckets<\/span> <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[<\/span>numBuckets<\/span>]<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>AddElement<\/span>(<\/span>string<\/span> element<\/span>)<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>using<\/span> <\/span>(<\/span>var<\/span> md5 <\/span>=<\/span> <\/span>MD5<\/span>.<\/span>Create<\/span>())<\/span><\/span>\n        <\/span>{<\/span><\/span>\n            <\/span>byte<\/span>[]<\/span> hash <\/span>=<\/span> <\/span>md5<\/span>.<\/span>ComputeHash<\/span>(<\/span>System<\/span>.<\/span>Text<\/span>.<\/span>Encoding<\/span>.<\/span>UTF8<\/span>.<\/span>GetBytes<\/span>(<\/span>element<\/span>))<\/span>;<\/span><\/span>\n            <\/span>int<\/span> bucketIndex <\/span>=<\/span> <\/span>hash<\/span>[<\/span>0<\/span>]<\/span> <\/span>%<\/span> <\/span>buckets<\/span>.<\/span>Length<\/span>;<\/span><\/span>\n            <\/span>int<\/span> rank <\/span>=<\/span> <\/span>CalculateRank<\/span>(<\/span>hash<\/span>)<\/span>;<\/span><\/span>\n            <\/span>buckets<\/span>[<\/span>bucketIndex<\/span>]<\/span> <\/span>=<\/span> <\/span>Math<\/span>.<\/span>Max<\/span>(<\/span>buckets<\/span>[<\/span>bucketIndex<\/span>],<\/span> <\/span>rank<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>int<\/span> <\/span>EstimateCardinality<\/span>()<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>double<\/span> alpha<\/span>;<\/span><\/span>\n        <\/span>int<\/span> m <\/span>=<\/span> <\/span>buckets<\/span>.<\/span>Length<\/span>;<\/span><\/span>\n        <\/span>switch<\/span> <\/span>(<\/span>m<\/span>)<\/span><\/span>\n        <\/span>{<\/span><\/span>\n            <\/span>case<\/span> <\/span>16<\/span>:<\/span><\/span>\n                <\/span>alpha<\/span> <\/span>=<\/span> <\/span>0.673<\/span>;<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n            <\/span>case<\/span> <\/span>32<\/span>:<\/span><\/span>\n                <\/span>alpha<\/span> <\/span>=<\/span> <\/span>0.697<\/span>;<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n            <\/span>case<\/span> <\/span>64<\/span>:<\/span><\/span>\n                <\/span>alpha<\/span> <\/span>=<\/span> <\/span>0.709<\/span>;<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n            <\/span>default<\/span>:<\/span><\/span>\n                <\/span>alpha<\/span> <\/span>=<\/span> <\/span>0.7213<\/span> <\/span>\/<\/span> <\/span>(<\/span>1<\/span> <\/span>+<\/span> <\/span>1.079<\/span> <\/span>\/<\/span> <\/span>m<\/span>)<\/span>;<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>double<\/span> sum <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>foreach<\/span> <\/span>(<\/span>int<\/span> bucket <\/span>in<\/span> <\/span>buckets<\/span>)<\/span><\/span>\n        <\/span>{<\/span><\/span>\n            <\/span>sum<\/span> <\/span>+=<\/span> <\/span>1.0<\/span> <\/span>\/<\/span> <\/span>(<\/span>1<\/span> <\/span><<<\/span> <\/span>bucket<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>double<\/span> estimate <\/span>=<\/span> <\/span>alpha<\/span> <\/span>*<\/span> <\/span>m<\/span> <\/span>*<\/span> <\/span>m<\/span> <\/span>\/<\/span> <\/span>sum<\/span>;<\/span><\/span>\n        <\/span>return<\/span> <\/span>(<\/span>int<\/span>)<\/span>estimate<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>int<\/span> <\/span>CalculateRank<\/span>(<\/span>byte<\/span>[]<\/span> hash<\/span>)<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>int<\/span> rank <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>foreach<\/span> <\/span>(<\/span>byte<\/span> b <\/span>in<\/span> <\/span>hash<\/span>)<\/span><\/span>\n        <\/span>{<\/span><\/span>\n            <\/span>if<\/span> <\/span>((<\/span>b<\/span> <\/span>&<\/span> <\/span>0x01<\/span>)<\/span> <\/span>==<\/span> <\/span>0<\/span> <\/span>||<\/span> <\/span>(<\/span>b<\/span> <\/span>&<\/span> <\/span>0x02<\/span>)<\/span> <\/span>==<\/span> <\/span>0<\/span>)<\/span><\/span>\n            <\/span>{<\/span><\/span>\n                <\/span>rank<\/span>++;<\/span><\/span>\n            <\/span>}<\/span><\/span>\n            <\/span>else<\/span><\/span>\n            <\/span>{<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n            <\/span>}<\/span><\/span>\n        <\/span>}<\/span><\/span>\n        <\/span>return<\/span> <\/span>rank<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>Program<\/span><\/span>\n{<\/span><\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>Main<\/span>()<\/span><\/span>\n    <\/span>{<\/span><\/span>\n        <\/span>\/\/ Criando um objeto HyperLogLog com 64 buckets<\/span><\/span>\n        HyperLogLog hyperLogLog <\/span>=<\/span> <\/span>new<\/span> HyperLogLog<\/span>(<\/span>64<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Adicionando elementos de exemplo<\/span><\/span>\n        <\/span>hyperLogLog<\/span>.<\/span>AddElement<\/span>(<\/span>"<\/span>element1<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>hyperLogLog<\/span>.<\/span>AddElement<\/span>(<\/span>"<\/span>element2<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>hyperLogLog<\/span>.<\/span>AddElement<\/span>(<\/span>"<\/span>element3<\/span>"<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Estimando a cardinalidade<\/span><\/span>\n        <\/span>int<\/span> cardinality <\/span>=<\/span> <\/span>hyperLogLog<\/span>.<\/span>EstimateCardinality<\/span>()<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>Console<\/span>.<\/span>WriteLine<\/span>(<\/span>"<\/span>Estimativa da Cardinalidade: <\/span>"<\/span> <\/span>+<\/span> <\/span>cardinality<\/span>)<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Neste exemplo, temos a classe HyperLogLog<\/code> que representa a estrutura do HyperLogLog. Ela possui um array de buckets<\/code> para armazenar os ranks dos hashes observados. O m\u00e9todo AddElement<\/code> \u00e9 usado para adicionar um novo elemento ao HyperLogLog, calculando o \u00edndice do bucket e atualizando o rank, se necess\u00e1rio. O m\u00e9todo EstimateCardinality<\/code> estima a cardinalidade com base nos ranks armazenados nos buckets.<\/p>\n\n\n\n
No exemplo Main<\/code>, criamos um objeto HyperLogLog<\/code> com 64 buckets, adicionamos alguns elementos de exemplo e estimamos a cardinalidade. O resultado \u00e9 exibido no console.<\/p>\n\n\n\n
Exemplo de implementa\u00e7\u00e3o em Java<\/h3>\n\n\n\n
Java<\/span><\/path><\/path><\/svg><\/span>
import<\/span> <\/span>java<\/span>.<\/span>nio<\/span>.<\/span>charset<\/span>.<\/span>StandardCharsets<\/span>;<\/span><\/span>\nimport<\/span> <\/span>java<\/span>.<\/span>security<\/span>.<\/span>MessageDigest<\/span>;<\/span><\/span>\nimport<\/span> <\/span>java<\/span>.<\/span>security<\/span>.<\/span>NoSuchAlgorithmException<\/span>;<\/span><\/span>\n<\/span>\npublic<\/span> <\/span>class<\/span> <\/span>HyperLogLog<\/span> <\/span>{<\/span><\/span>\n    <\/span>private<\/span> <\/span>int<\/span>[]<\/span> <\/span>buckets<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>HyperLogLog<\/span>(<\/span>int<\/span> <\/span>numBuckets<\/span>)<\/span> <\/span>{<\/span><\/span>\n        buckets <\/span>=<\/span> <\/span>new<\/span> <\/span>int<\/span>[<\/span>numBuckets<\/span>]<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>void<\/span> <\/span>addElement<\/span>(<\/span>String<\/span> <\/span>element<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>try<\/span> <\/span>{<\/span><\/span>\n            <\/span>MessageDigest<\/span> <\/span>md5<\/span> <\/span>=<\/span> <\/span>MessageDigest<\/span>.<\/span>getInstance<\/span>(<\/span>"<\/span>MD5<\/span>"<\/span>)<\/span>;<\/span><\/span>\n            <\/span>byte<\/span>[]<\/span> <\/span>hash<\/span> <\/span>=<\/span> <\/span>md5<\/span>.<\/span>digest<\/span>(<\/span>element<\/span>.<\/span>getBytes<\/span>(<\/span>StandardCharsets<\/span>.<\/span>UTF_8<\/span>))<\/span>;<\/span><\/span>\n            <\/span>int<\/span> <\/span>bucketIndex<\/span> <\/span>=<\/span> hash<\/span>[<\/span>0<\/span>]<\/span> <\/span>%<\/span> <\/span>buckets<\/span>.<\/span>length<\/span>;<\/span><\/span>\n            <\/span>int<\/span> <\/span>rank<\/span> <\/span>=<\/span> <\/span>calculateRank<\/span>(<\/span>hash<\/span>)<\/span>;<\/span><\/span>\n            buckets<\/span>[<\/span>bucketIndex<\/span>]<\/span> <\/span>=<\/span> <\/span>Math<\/span>.<\/span>max<\/span>(<\/span>buckets<\/span>[<\/span>bucketIndex<\/span>],<\/span> rank<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span> <\/span>catch<\/span> <\/span>(<\/span>NoSuchAlgorithmException<\/span> <\/span>e<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>e<\/span>.<\/span>printStackTrace<\/span>()<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>int<\/span> <\/span>estimateCardinality<\/span>()<\/span> <\/span>{<\/span><\/span>\n        <\/span>double<\/span> <\/span>alpha<\/span>;<\/span><\/span>\n        <\/span>int<\/span> <\/span>m<\/span> <\/span>=<\/span> <\/span>buckets<\/span>.<\/span>length<\/span>;<\/span><\/span>\n        <\/span>switch<\/span> <\/span>(<\/span>m<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>case<\/span> <\/span>16<\/span>:<\/span><\/span>\n                alpha <\/span>=<\/span> <\/span>0.673<\/span>;<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n            <\/span>case<\/span> <\/span>32<\/span>:<\/span><\/span>\n                alpha <\/span>=<\/span> <\/span>0.697<\/span>;<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n            <\/span>case<\/span> <\/span>64<\/span>:<\/span><\/span>\n                alpha <\/span>=<\/span> <\/span>0.709<\/span>;<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n            <\/span>default:<\/span><\/span>\n                alpha <\/span>=<\/span> <\/span>0.7213<\/span> <\/span>\/<\/span> <\/span>(<\/span>1<\/span> <\/span>+<\/span> <\/span>1.079<\/span> <\/span>\/<\/span> m<\/span>)<\/span>;<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>double<\/span> <\/span>sum<\/span> <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>for<\/span> <\/span>(<\/span>int<\/span> <\/span>bucket<\/span> <\/span>:<\/span> buckets<\/span>)<\/span> <\/span>{<\/span><\/span>\n            sum <\/span>+=<\/span> <\/span>1.0<\/span> <\/span>\/<\/span> <\/span>(<\/span>1<\/span> <\/span><<<\/span> bucket<\/span>)<\/span>;<\/span><\/span>\n        <\/span>}<\/span><\/span>\n<\/span>\n        <\/span>double<\/span> <\/span>estimate<\/span> <\/span>=<\/span> alpha <\/span>*<\/span> m <\/span>*<\/span> m <\/span>\/<\/span> sum<\/span>;<\/span><\/span>\n        <\/span>return<\/span> <\/span>(<\/span>int<\/span>)<\/span> estimate<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>private<\/span> <\/span>int<\/span> <\/span>calculateRank<\/span>(<\/span>byte<\/span>[]<\/span> <\/span>hash<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>int<\/span> <\/span>rank<\/span> <\/span>=<\/span> <\/span>0<\/span>;<\/span><\/span>\n        <\/span>for<\/span> <\/span>(<\/span>byte<\/span> <\/span>b<\/span> <\/span>:<\/span> hash<\/span>)<\/span> <\/span>{<\/span><\/span>\n            <\/span>if<\/span> <\/span>((<\/span>b <\/span>&<\/span> <\/span>0x01<\/span>)<\/span> <\/span>==<\/span> <\/span>0<\/span> <\/span>||<\/span> <\/span>(<\/span>b <\/span>&<\/span> <\/span>0x02<\/span>)<\/span> <\/span>==<\/span> <\/span>0<\/span>)<\/span> <\/span>{<\/span><\/span>\n                rank<\/span>++;<\/span><\/span>\n            <\/span>}<\/span> <\/span>else<\/span> <\/span>{<\/span><\/span>\n                <\/span>break;<\/span><\/span>\n            <\/span>}<\/span><\/span>\n        <\/span>}<\/span><\/span>\n        <\/span>return<\/span> rank<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n<\/span>\n    <\/span>public<\/span> <\/span>static<\/span> <\/span>void<\/span> <\/span>main<\/span>(<\/span>String<\/span>[]<\/span> <\/span>args<\/span>)<\/span> <\/span>{<\/span><\/span>\n        <\/span>\/\/ Criando um objeto HyperLogLog com 64 buckets<\/span><\/span>\n        <\/span>HyperLogLog<\/span> <\/span>hyperLogLog<\/span> <\/span>=<\/span> <\/span>new<\/span> <\/span>HyperLogLog<\/span>(<\/span>64<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Adicionando elementos de exemplo<\/span><\/span>\n        <\/span>hyperLogLog<\/span>.<\/span>addElement<\/span>(<\/span>"<\/span>element1<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>hyperLogLog<\/span>.<\/span>addElement<\/span>(<\/span>"<\/span>element2<\/span>"<\/span>)<\/span>;<\/span><\/span>\n        <\/span>hyperLogLog<\/span>.<\/span>addElement<\/span>(<\/span>"<\/span>element3<\/span>"<\/span>)<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>\/\/ Estimando a cardinalidade<\/span><\/span>\n        <\/span>int<\/span> <\/span>cardinality<\/span> <\/span>=<\/span> <\/span>hyperLogLog<\/span>.<\/span>estimateCardinality<\/span>()<\/span>;<\/span><\/span>\n<\/span>\n        <\/span>System<\/span>.<\/span>out<\/span>.<\/span>println<\/span>(<\/span>"<\/span>Estimativa da Cardinalidade: <\/span>"<\/span> <\/span>+<\/span> cardinality<\/span>)<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\n\/\/ Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Neste exemplo, temos a classe HyperLogLog<\/code> que representa a estrutura do HyperLogLog. Ela possui um array de buckets<\/code> para armazenar os ranks dos hashes observados. O m\u00e9todo addElement<\/code> \u00e9 usado para adicionar um novo elemento ao HyperLogLog, calculando o \u00edndice do bucket e atualizando o rank, se necess\u00e1rio. O m\u00e9todo estimateCardinality<\/code> estima a cardinalidade com base nos ranks armazenados nos buckets.<\/p>\n\n\n\n
No m\u00e9todo main<\/code>, criamos um objeto HyperLogLog<\/code> com 64 buckets, adicionamos alguns elementos de exemplo e estimamos a cardinalidade. O resultado \u00e9 exibido no console.<\/p>\n\n\n\n
Exemplo de implementa\u00e7\u00e3o em Python<\/h3>\n\n\n\n
Python<\/span><\/path><\/path><\/svg><\/span>
import<\/span> mmh3<\/span><\/span>\nimport<\/span> math<\/span><\/span>\n<\/span>\nclass<\/span> <\/span>HyperLogLog<\/span>:<\/span><\/span>\n    <\/span>def<\/span> <\/span>__init__<\/span>(<\/span>self<\/span>,<\/span> <\/span>num_buckets<\/span>):<\/span><\/span>\n        <\/span>self<\/span>.<\/span>num_buckets <\/span>=<\/span> num_buckets<\/span><\/span>\n        <\/span>self<\/span>.<\/span>buckets <\/span>=<\/span> <\/span>[<\/span>0<\/span>]<\/span> <\/span>*<\/span> num_buckets<\/span><\/span>\n<\/span>\n    <\/span>def<\/span> <\/span>add_element<\/span>(<\/span>self<\/span>,<\/span> <\/span>element<\/span>):<\/span><\/span>\n        hash_value <\/span>=<\/span> mmh3<\/span>.<\/span>hash<\/span>(<\/span>element<\/span>)<\/span> <\/span># Usando o algoritmo MurmurHash para gerar o hash<\/span><\/span>\n        bucket_index <\/span>=<\/span> hash_value <\/span>&<\/span> <\/span>(<\/span>self<\/span>.<\/span>num_buckets <\/span>-<\/span> <\/span>1<\/span>)<\/span> <\/span># Obtendo o \u00edndice do bucket usando a opera\u00e7\u00e3o bitwise AND<\/span><\/span>\n        rank <\/span>=<\/span> <\/span>self<\/span>.<\/span>calculate_rank<\/span>(<\/span>hash_value<\/span>)<\/span> <\/span># Calculando o rank baseado no hash<\/span><\/span>\n        <\/span>self<\/span>.<\/span>buckets<\/span>[<\/span>bucket_index<\/span>]<\/span> <\/span>=<\/span> <\/span>max<\/span>(<\/span>self<\/span>.<\/span>buckets<\/span>[<\/span>bucket_index<\/span>],<\/span> rank<\/span>)<\/span> <\/span># Atualizando o rank m\u00e1ximo do bucket<\/span><\/span>\n<\/span>\n    <\/span>def<\/span> <\/span>estimate_cardinality<\/span>(<\/span>self<\/span>):<\/span><\/span>\n        alpha <\/span>=<\/span> <\/span>0.7213<\/span> <\/span>\/<\/span> <\/span>(<\/span>1<\/span> <\/span>+<\/span> <\/span>1.079<\/span> <\/span>\/<\/span> <\/span>self<\/span>.<\/span>num_buckets<\/span>)<\/span><\/span>\n        sum_of_inverses <\/span>=<\/span> <\/span>sum<\/span>([<\/span>1<\/span> <\/span>\/<\/span> <\/span>(<\/span>2<\/span> <\/span>**<\/span> rank<\/span>)<\/span> <\/span>for<\/span> rank <\/span>in<\/span> <\/span>self<\/span>.<\/span>buckets<\/span>])<\/span><\/span>\n        estimate <\/span>=<\/span> alpha <\/span>*<\/span> <\/span>(<\/span>self<\/span>.<\/span>num_buckets <\/span>**<\/span> <\/span>2<\/span>)<\/span> <\/span>\/<\/span> sum_of_inverses<\/span><\/span>\n<\/span>\n        <\/span>if<\/span> estimate <\/span><=<\/span> <\/span>2.5<\/span> <\/span>*<\/span> <\/span>self<\/span>.<\/span>num_buckets<\/span>:<\/span>  <\/span># Small range correction<\/span><\/span>\n            zeros <\/span>=<\/span> <\/span>self<\/span>.<\/span>buckets<\/span>.<\/span>count<\/span>(<\/span>0<\/span>)<\/span><\/span>\n            <\/span>if<\/span> zeros <\/span>!=<\/span> <\/span>0<\/span>:<\/span><\/span>\n                estimate <\/span>=<\/span> <\/span>self<\/span>.<\/span>num_buckets <\/span>*<\/span> math<\/span>.<\/span>log<\/span>(<\/span>self<\/span>.<\/span>num_buckets <\/span>\/<\/span> zeros<\/span>)<\/span><\/span>\n<\/span>\n        <\/span>return<\/span> <\/span>int<\/span>(<\/span>estimate<\/span>)<\/span><\/span>\n<\/span>\n    <\/span>def<\/span> <\/span>calculate_rank<\/span>(<\/span>self<\/span>,<\/span> <\/span>hash_value<\/span>):<\/span><\/span>\n        rank <\/span>=<\/span> <\/span>1<\/span><\/span>\n        <\/span>while<\/span> <\/span>(<\/span>hash_value <\/span>&<\/span> <\/span>1<\/span>)<\/span> <\/span>==<\/span> <\/span>0<\/span>:<\/span>  <\/span># Contando os bits zero consecutivos<\/span><\/span>\n            rank <\/span>+=<\/span> <\/span>1<\/span><\/span>\n            hash_value <\/span>>>=<\/span> <\/span>1<\/span><\/span>\n        <\/span>return<\/span> rank<\/span><\/span>\n<\/span>\n# Exemplo de uso<\/span><\/span>\nhyperloglog <\/span>=<\/span> <\/span>HyperLogLog<\/span>(<\/span>64<\/span>)<\/span>  <\/span># Criando um objeto HyperLogLog com 64 buckets<\/span><\/span>\n<\/span>\n# Adicionando elementos de exemplo<\/span><\/span>\nhyperloglog<\/span>.<\/span>add_element<\/span>(<\/span>"<\/span>element1<\/span>"<\/span>)<\/span><\/span>\nhyperloglog<\/span>.<\/span>add_element<\/span>(<\/span>"<\/span>element2<\/span>"<\/span>)<\/span><\/span>\nhyperloglog<\/span>.<\/span>add_element<\/span>(<\/span>"<\/span>element3<\/span>"<\/span>)<\/span><\/span>\n<\/span>\n# Estimando a cardinalidade<\/span><\/span>\ncardinality <\/span>=<\/span> hyperloglog<\/span>.<\/span>estimate_cardinality<\/span>()<\/span><\/span>\n<\/span>\nprint<\/span>(<\/span>"<\/span>Estimativa da Cardinalidade:<\/span>"<\/span>,<\/span> cardinality<\/span>)<\/span><\/span>\n<\/span>\n# Fonte: ChatGPT<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Neste exemplo, a classe HyperLogLog<\/code> representa a estrutura do HyperLogLog. Ela possui um array buckets<\/code> para armazenar os ranks m\u00e1ximos dos hashes observados. O m\u00e9todo add_element<\/code> \u00e9 usado para adicionar um novo elemento ao HyperLogLog, calcular o \u00edndice do bucket e atualizar o rank m\u00e1ximo, se necess\u00e1rio. O m\u00e9todo estimate_cardinality<\/code> estima a cardinalidade com base nos ranks armazenados nos buckets.<\/p>\n\n\n\n
No exemplo de uso, criamos um objeto HyperLogLog<\/code> com 64 buckets, adicionamos alguns elementos de exemplo e estimamos a cardinalidade. O resultado \u00e9 exibido no console.<\/p>\n\n\n\n
A Efici\u00eancia do HyperLogLog<\/h3>\n\n\n\n
A verdadeira beleza do HyperLogLog<\/em> reside em sua efici\u00eancia. Ele consome uma quantidade constante de mem\u00f3ria, independentemente do tamanho do conjunto de dados que est\u00e1 analisando. Isso o torna extremamente \u00fatil em cen\u00e1rios onde o espa\u00e7o de armazenamento \u00e9 limitado.<\/p>\n\n\n\n
Aplica\u00e7\u00f5es Pr\u00e1ticas do HyperLogLog<\/h2>\n\n\n\n
O HyperLogLog<\/em> tem uma ampla gama de aplica\u00e7\u00f5es pr\u00e1ticas, especialmente em grandes conjuntos de dados.<\/p>\n\n\n\n
Uso do HyperLogLog em Analytics<\/h3>\n\n\n\n
Uma das aplica\u00e7\u00f5es mais comuns \u00e9 na an\u00e1lise de tr\u00e1fego de websites<\/em>, onde \u00e9 usado para estimar o n\u00famero de visitantes \u00fanicos de um site.<\/p>\n\n\n\n
HyperLogLog na Transforma\u00e7\u00e3o Digital<\/h3>\n\n\n\n
O HyperLogLog<\/em> tamb\u00e9m \u00e9 crucial no processo de transforma\u00e7\u00e3o digital das empresas, permitindo a an\u00e1lise de grandes volumes de dados de maneira eficiente, o que pode levar a insights<\/em> valiosos e melhorar a tomada de decis\u00f5es.<\/p>\n\n\n\n
Conclus\u00e3o<\/h2>\n\n\n\n
O HyperLogLog representa uma solu\u00e7\u00e3o eficiente e precisa para determinar a cardinalidade de conjuntos, especialmente em grandes volumes de dados. Sua habilidade de proporcionar estimativas precisas com um uso m\u00ednimo de mem\u00f3ria o torna uma ferramenta valiosa na era digital de hoje.<\/p>\n\n\n\n
Esse conte\u00fado \u00e9 parte do material disponibilizado para os participantes do meu grupo de estudos de\u00a0Algoritmos e Estruturas de Dados<\/strong>. Voc\u00ea quer participar desse grupo?\u00a0Clique aqui e veja como funciona<\/a><\/strong>.<\/p>\n\n\n\n
D\u00favidas Frequentes<\/h2>\n\n\n\n
O que \u00e9 HyperLogLog<\/em>?<\/strong>
HyperLogLog <\/em>\u00e9 um algoritmo para estimar a cardinalidade de conjuntos de dados grandes.<\/p>\n\n\n\n
Por que o HyperLogLog<\/em> \u00e9 \u00fatil?<\/strong>
HyperLogLog<\/em> \u00e9 \u00fatil por sua habilidade de fornecer estimativas precisas da cardinalidade com um uso m\u00ednimo de mem\u00f3ria.<\/p>\n\n\n\n
Onde o HyperLogLog<\/em> \u00e9 usado?<\/strong>
O HyperLogLog<\/em> \u00e9 usado em v\u00e1rias aplica\u00e7\u00f5es, incluindo a an\u00e1lise de tr\u00e1fego de websites<\/em> e a an\u00e1lise de grandes volumes de dados na transforma\u00e7\u00e3o digital.<\/p>\n\n\n\n
O HyperLogLog \u00e9 sempre preciso?<\/strong>
HyperLogLog<\/em> \u00e9 uma estimativa, ent\u00e3o haver\u00e1 alguma varia\u00e7\u00e3o, mas geralmente \u00e9 muito preciso.<\/p>\n\n\n\n
Como o HyperLogLog economiza mem\u00f3ria?<\/strong>
O HyperLogLog<\/em> usa um m\u00e9todo probabil\u00edstico para estimar a cardinalidade, o que consome uma quantidade constante de mem\u00f3ria, independentemente do tamanho do conjunto de dados.<\/p>\n","protected":false},"featured_media":5894,"parent":0,"template":"","cursos":[5],"class_list":["post-5738","artigos","type-artigos","status-publish","has-post-thumbnail","hentry","cursos-algortimos"],"acf":[],"_links":{"self":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/artigos\/5738","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/artigos"}],"about":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/types\/artigos"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/media\/5894"}],"wp:attachment":[{"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/media?parent=5738"}],"wp:term":[{"taxonomy":"cursos","embeddable":true,"href":"https:\/\/elemarjr.com\/clube-de-estudos\/wp-json\/wp\/v2\/cursos?post=5738"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}