BitMap 和 HyperLogLog

2024-03-18 01:36
文章标签 bitmap hyperloglog

本文主要是介绍BitMap 和 HyperLogLog,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

BitMap

常用命令

应用场景

日活统计

用户签到

HyperLogLog

什么是基数?

常用命令

应用场景


BitMap

问: "有10亿个不重复的无序的正数,如果快速排序?"

这看上去很简单,就是一个排序而已,但是大部分排序算法都需要把数据放到内存里面操作,这10亿个数字得占用多少内存?

在大部分编程语言里面,int类型一般的都是占4个byte,也是32位,不管这个数字是1 或者是 21亿都得占32位,所以如果现在有10亿数字需要存放在内存里面,需要多少内存呢?

以Java为例,1000000000 * 4 / 1024 / 1024 = 3814.69MB,大概需要3814.69MB内存!

假如有 1,3,7,2,5 这5个数字需要存放,正常情况下你需要5*4=20byte,但bitmap只需要1byte,即桶排的思想。

setbit的大小在0到2的32次方(最大使用512M内存)之间,即0~4294967296(42亿)之间。

常用命令

bitmap主要就三个操作命令:

  • setbit(设置标记)
  • getbit(即 getbit key index ,如果返回1,表示存在否则不存在)
  • bitcount(即 bitcount key ,统计和)

应用场景

日活统计

统计应用或网站的日活,这个属于比较常见的case了,如果是用redis来做这个事情,首先我们最容易想到的是Hash结构,存储如下:

  • 日期(key,如“2024-03-17”)userId(field,如“134”)true(value)
  • 判断日活则是统计map的元素个数

以上设计其实没什么问题,但如果日活量很高的话,会造成大Key问题(这里Value会很大),我们看一下bitmap可以怎么做

  • setbit 日期 uesrId 1
  • bitcount 日期

简单对比一下上面两种方案

当数据量小时,且userid分布不均匀,小的为个位数,大的几千万,上亿这种,使用bitmap就有点亏了,因为userId作为index,那么bitmap的长度就需要能容纳最大的userId,但是实际日活又很小,说明bitmap中间有大量的空白数据。

反之当数据量很大时,比如百万/千万,userId是连续递增的场景下,bitmap的优势有两点:

  1. 存储开销小
  2. 统计总数快

用户签到

  • setbit 用户id+年月 dayofmonth 1
  • bitcount 用户id+年月

HyperLogLog

  • HyperLogLog是用来做基数统计的算法,不是集合,不会保存元数据,只记录数量而不是数值。
  • HyperLogLog的优点是,在输入元素的数量或者体积非常非常大时,计算基数所需的空间总是固定的、并且是很小的。
  • 在 Redis 里面,每个 HyperLogLog 键只需要花费 12 KB 内存,就可以计算接近 2^64 个不同元素的基数。这和计算基数时,元素越多耗费内存就越多的集合形成鲜明对比。
  • 基数估计的结果是一个带有 0.81% 标准错误(standard error)的近似值。是可接受的范围。

什么是基数?

比如数据集(1,3,5,7,5,7,8}, 那么这个数据集的基数集为{1,3,5 ,7,8},基数(不重复元素)为5。基数估计就是在误差可接受的范围内,快速计算基数。

常用命令

  • PFADD key element [element ...]:添加指定元素到 HyperLogLog 中
  • PFCOUNT key [key ...]:返回给定 HyperLogLog 的基数估算值
  • PFMERGE destkey sourcekey [sourcekey ...〕:将多个 HyperLogLog 合并为一个 HyperLogLog

应用场景

说明:有局限性,就是只能统计基数数量,而没办法去知道具体的内容是什么

一般使用:

  • 统计注册 IP 数
  • 统计每日访问 IP 数
  • 统计页面实时 UV 数
  • 统计在线用户数
  • 统计用户每天搜索不同词条的个数

这篇关于BitMap 和 HyperLogLog的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/820790

相关文章

数据流与Bitmap之间相互转换

把获得的数据流转换成一副图片(Bitmap) 其原理就是把获得倒的数据流序列化到内存中,然后经过加工,在把数据从内存中反序列化出来就行了。 难点就是在如何实现加工。因为Bitmap有一个专有的格式,我们常称这个格式为数据头。加工的过程就是要把这个数据头与我们之前获得的数据流合并起来。(也就是要把这个头加入到我们之前获得的数据流的前面)      那么这个头是

黑马点评11——UV统计-HyperLogLog

文章目录 HyperLogLog的用法测试百万数据的统计 HyperLogLog的用法 简直就是天生用于UV统计的,太爽了! 测试百万数据的统计 /*** info memory* 2107168* 插入1000000条数据后,内存的变化* 2121552*/@Testvoid testHyperLogLog(){String[] values = new Stri

黑马点评10——用户签到-BitMap数据结构

文章目录 BitMap用法签到功能签到统计 BitMap用法 其实数据库完全可以实现签到功能 但签到数据比较大,借鉴签到卡的思想 布隆过滤器也是使用BitMap实现的. 签到功能 因为是当前用户的当天,所以保存需要的年月日不需要参数,可以直接获取。 @Overridepublic Result sign() {// 1. 获取当前登录用户Long userId

将DIB/bitmap读入内存并转为 halcon hobject

问题由来:在mfc halcon混合编程中,发现halcon::readimage() 函数读取图片(8位8M/bmp)至少200ms,当然24位 32位bmp 倍数所消耗的时间倍数上涨。那么有没有什么方法加快读取速度?目前发现一个亲测可行的方式:  1、通过 DIBAPI 读取图片,下载可转到点击打开链接,赚点积分 2、获取所读读片的图像数据的首地址,注意非结构头地址 3、通过halcon

C#Bitmap和Image之间的关系

Image 类 Image 是一个抽象基类,它定义了所有图像类型的共同属性和方法。它提供了图像处理的通用接口,比如获取图像的尺寸、像素格式、帧数等。Image 类本身不能被实例化,它只是提供了一个通用的框架,具体的图像类型(如位图、图标、元文件等)需要通过继承 Image 类来实现。Image 类提供了一些通用的方法,如 Save(保存图像到文件)、GetThumbnailImage(获取图像的

Android Drawable与Bitmap

一、相关概念 1、Drawable就是一个可画的对象,其可能是一张位图(BitmapDrawable),也可能是一个图形(ShapeDrawable),还有可能是一个图层(LayerDrawable),我们根据画图的需求,创建相应的可画对象 2、Canvas画布,绘图的目的区域,用于绘图 3、Bitmap位图,用于图的处理 4、Matrix矩阵 二、Bitmap 1、从资源中获取

Android调整Bitmap图片大小

#Android调整Bitmap图片大小 /*** 调整图片大小* * @param bitmap* 源* @param dst_w* 输出宽度* @param dst_h* 输出高度* @return*/public static Bitmap imageScale(Bitmap bitmap, int dst_w, int d

145. 利用 Redis Bitmap实践: 用户签到统计

文章目录 一、Redis Bitmap简介二、Bitmap 的主要应用三、Go使用Redis实现签到统计用户签到查询用户签到状态统计今年累计签到天数统计当月的签到情况 总结 在现代应用程序中,用户签到是一个常见的功能。我们通常使用 MySQL 数据库来存储用户的签到记录。然而,随着用户数量的增加,数据库中的记录将会随时间和用户量线性增长,这不仅增加了存储的负担,而且可能影响查询效率

bitmap(位图)的使用

零存零取,整存零取,整存整取, 零存整取 bitmap介绍 位图不是真正的数据类型,它是定义在字符串类型中,一个字符串类型的值最多能存储512M字节的内容,    位上限:2^(9(512)+10(1024)+10(1024)+3(8b=1B))=2^32b 语句操作: setbit 语法:SETBIT key offset value (offset位偏移量,从0开始), setbi

Android 画布canvas drawBitmap(Bitmap bitmap, Rect src, Rect dst, Paint paint)

void    drawBitmap(Bitmap bitmap, Rect src, Rect dst, Paint paint) Draw the specified bitmap, scaling/translating automatically to fill the destination rectangle. 绘制指定的位图,自动缩放/平移以填充目标矩形。没有返回值。该方法有三个参