扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 场景题 > 系统设计高频面试题 > 7. 基数估计

如何计算数据流中不同元素的个数?例如,独立访客(Unique Visitor,简称UV)统计。这个问题称为基数估计(Cardinality Estimation),也是一个很经典的题目。

方案1: HashSet

首先最容易想到的办法是用HashSet,每来一个元素,就往里面塞,HashSet的大小就所求答案。但是在大数据的场景下,HashSet在单机内存中存不下。

方案2: bitmap

HashSet耗内存主要是由于存储了元素的真实值,可不可以不存储元素本身呢?bitmap就是这样一个方案,假设已经知道不同元素的个数的上限,即基数的最大值,设为N,则开一个长度为N的bit数组,地位跟HashSet一样。每个元素与bit数组的某一位一一对应,该位为1,表示此元素在集合中,为0表示不在集合中。那么bitmap中1的个数就是所求答案。

这个方案的缺点是,bitmap的长度与实际的基数无关,而是与基数的上限有关。假如要计算上限为1亿的基数,则需要12.5MB的bitmap,十个网站就需要125M。关键在于,这个内存使用与集合元素数量无关,即使一个网站仅仅有一个1UV,也要为其分配12.5MB内存。

实际上目前还没有发现在大数据场景中准确计算基数的高效算法,因此在不追求绝对准确的情况下,使用近似算法算是一个不错的解决方案。

方案3: Linear Counting

方案4: LogLog Counting

方案5: HyperLogLog Counting


点击面试手册,获取本站面试手册PDF完整版