首页天道酬勤大数据的应用场景及具体实例(保险大数据应用场景)

大数据的应用场景及具体实例(保险大数据应用场景)

admin 12-04 08:51 272次浏览

10亿数字去重的问题

这是一个常见的问题,网上有很多关于这个问题的解决方案的搜索。

主流的解决方案是用位图来处理。

虽然用位图解决这个问题的方法很巧妙,但受访者不会告诉你位图会有什么局限性。

本文从位图的局限性入手,探讨解决这类问题的其他方法。

当然,在讨论这种解决方案的同时,我会扩大这个问题的范围。

重复数据删除

扩大数值范围

原问题中的数字范围只有0-10亿,这是一个非常有利的限制,也正是因为这个限制,位图才能够完美的解决这个问题。

一个10亿长度的位图消耗多少内存空间?

100000000/8/1024/1024=119.20928955078米

也就是不到120M。

java中无符号int类型的最大值是4294967295。也就是说,如果是解决一个整数可重复性问题,消耗的内存只有512M。现在大多数电脑都买得起。

但如果放宽这个限制,取值范围是0-1万亿?当内存再也装不下这么长的位图?

00-1010如果把数值的范围放宽到0-1万亿,这时可以把10-100亿的数据分成一个区,100-200亿的数据分成第二个区,以此类推。然后在每个分区做位图的去重操作。

虽然这种方法可以解决范围放宽后的去重问题。但这也带来了另一个问题。

这是什么问题?

虽然我们放宽了数值的范围,但原始数据的总数仍然只有10亿!也就是说浪费严重。为了识别每个值的存在,我们需要浪费999个资源来识别不存在的资源。

这说明位图不适合那些稀疏的数据集,会有大量的数据浪费。

00-1010之前,我们谈论的都是数字去重的问题。如果要复制的数据集不是数字数据而是字符串,位图就不能很好地工作。当然,我们可以对字符串进行二值化,并使用位图以二进制方式删除重复项。但是这种方式是不可行的。毕竟,一个4字节的字符串已经需要消耗512M的内存。而且要复制的字符串肯定不止四个,那么这个时候我们该怎么办呢?

00-1010我们可以通过散列余数来划分字符串。因为此分区方法可以确保相同的字符串将位于相同的分区中。然后,复制每个分区中的文件。使用set移除副本就足够了。只需确保分区后,分区数据的大小小于内存的大小。

00-1010算法:

1.首先,需要k个散列函数,每个函数可以将密钥散列成一个整数。

2.在初始化过程中,需要一个N位数组,每个位都初始化为0。

3.当一个密钥被添加到集合中时,k个散列值由k个散列函数计算,并且数组中相应的位位置被设置为1。

4.判断一个密钥是否在集合中时,使用k个哈希函数计算k个哈希值,查询数组中对应的位。如果所有位都是1,则认为它在集合中。

布隆过滤器在空间和时间上有很大的优势。布隆过滤器的存储空间和插入/查询时间是恒定的。

同时缺点也很明显,那就是误判率。随着沉积元素数量的增加,误判率增加。

实际上,目前在大数据场景中还没有更好的高效算法来精确计算基数,所以使用概率算法而不追求绝对精度是一个很好的解决方案。该算法不直接存储数据集本身,而是通过一定的概率统计方法估计基值,可以大大节省内存,保证误差控制在一定范围内。

分区

Hyperloglog Counting(HLL):Hyperloglog Counting是基于LLC的优化和改进。在相同的空间复杂度下,基数估计误差可以小于有限责任公司。并且空间复杂度仅为O(log_2(log_2(N_{max}))。

上面我们已经计算过,用位图存储1亿个统计数据大约需要1200万内存。在HLL,只需要不到1K的内存就可以做到。

目前,HyperLogLog算法已经在redis中实现,只需要12K内存,可以统计2.64个数据,标准误差为0.81%。

这说明这个算法有多强大。至于这个算法的具体细节,可以自己谷歌一下。

同样的缺点是误判率。

如果业务不需要完全准确的数据,可以选择这个算法。例如,HyperLogLog算法可以用来统计每天访问的网站的IP数量。

字符串去重

.这些是基于数据进一步发展的知识点。希望这些内容对你有用。

大眼之膨胀算法
() 重复数据的处理方式(数据库删除重复数据)
相关内容