前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >关于HyperLogLog去重优化

关于HyperLogLog去重优化

作者头像
Flink实战剖析
发布2022-04-18 13:14:53
2880
发布2022-04-18 13:14:53
举报
文章被收录于专栏:Flink实战剖析Flink实战剖析

1Flink去重第一弹: MapState去重

2Flink去重第二弹:SQL方式

3Flink去重第三弹:HyperLogLog去重

在HyperLogLog去重实现中,如果要求误差在0.001以内,那么就需要1048576个int, 也就是会消耗4M的存储空间,但是在实际使用中有很多的维度的统计是达不到这个数据量,那么可以在这里做一个优化,优化方式是:初始HyperLogLog内部使用存储是一个set集合,当set大小达到了指定大小(1048576)就转换为HyperLogLog存储方式。这种方式可以有效减小内存消耗。

实现代码:

代码语言:javascript
复制
public class OptimizationHyperLogLog {
    //hyperloglog结构
    private HyperLogLog hyperLogLog;
    //初始的一个set
    private Set<Integer> set;
     
    private double rsd;
    
    //hyperloglog的桶个数,主要内存占用
    private int bucket;

    public OptimizationHyperLogLog(double rsd){
        this.rsd=rsd;
        this.bucket=1 << HyperLogLog.log2m(rsd);
        set=new HashSet<>();      
       }

   //插入一条数据
    public void offer(Object object){
        final int x = MurmurHash.hash(object);
        int currSize=set.size();
        if(hyperLogLog==null && currSize+1>bucket){ 
           //升级为hyperloglog
           hyperLogLog=new HyperLogLog(rsd);
           for(int d: set){
               hyperLogLog.offerHashed(d);
           }
           set.clear();
        }

        if(hyperLogLog!=null){
            hyperLogLog.offerHashed(x);
        }else {
            set.add(x);
        }
    }

    //获取大小
    public long cardinality() {
      if(hyperLogLog!=null) return hyperLogLog.cardinality();
      return set.size();
    }
}

初始化:入参同样是一个允许的误差范围值rsd,计算出hyperloglog需要桶的个数bucket,也就需要是int数组大小,并且初始化一个set集合hashset;

数据插入:使用与hyperloglog同样的方式将插入数据转hash, 判断当前集合的大小+1是否达到了bucket,不满足则直接添加到set中,满足则将set里面数据转移到hyperloglog对象中并且清空set, 后续数据将会被添加到hyperloglog中;

这种写法没有考虑并发情况,在实际使用情况中也不会存在并发问题。

—END—

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-01-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Flink实战剖析 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
对象存储
对象存储(Cloud Object Storage,COS)是由腾讯云推出的无目录层次结构、无数据格式限制,可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限,无需分区管理,适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档