BitMap 博客分类: 寒假小结 BitMap
程序员文章站
2024-03-25 15:08:58
...
问题:
腾讯要统计自己的注册用户总量,考虑到有的用户用一个IP同时注册了扣扣,DNF和LOL,为了不重复统计,要将超内存的整型数据进行排重操作。
初级想法:
为了解决大型数组排重问题,我们先了解一下bitmap这个概念。bit指位,map指映射。bitmap,顾名思义,就是指输入的整型数能用bit数组中的数一一对应表示出来。也就是说,我们可以建立一个很大的“bit数组”,这个数组足以映射到所有的整型,于是乎我们用一个bit(一个位)表示一个int(32位),只用了原数据的三十二分之一的空间就完成了。
遇到的问题:
现在,我们面临的最最重要的问题是:我们的电脑无法直接对位进行操作!!!
解决问题的思路:
问题到这里,似乎成了一个死结,我们只能用一个byte表示一个int了,节省四分之三的空间,但这远远达不到需求。
试想,我们能否通过byte间接操作bit呢?
一个byte占据八位的存储空间,如果我们找到了一种方法使得一个byte表示八个整型数据,就间接找到了我们理想化的方法。
实际解决步骤:
下面开始讨论这个大数组排重问题的具体实现思路。
1)创建一个byte数组,长度为2的29次方,把所有的byte置0。
2)对应输入的int型数据,先对8取整得m,并把byte[m]转化为二进制数表示。
3)对8取余得到n,将byte[m]的第n位置1。(对于这部分代码,可以当做字符串来处理,当然,熟悉位操作的同学可以通过移位实现。)
到这里,腾讯的用户统计问题就解决了。童鞋们,开始写代码喽。
腾讯要统计自己的注册用户总量,考虑到有的用户用一个IP同时注册了扣扣,DNF和LOL,为了不重复统计,要将超内存的整型数据进行排重操作。
初级想法:
为了解决大型数组排重问题,我们先了解一下bitmap这个概念。bit指位,map指映射。bitmap,顾名思义,就是指输入的整型数能用bit数组中的数一一对应表示出来。也就是说,我们可以建立一个很大的“bit数组”,这个数组足以映射到所有的整型,于是乎我们用一个bit(一个位)表示一个int(32位),只用了原数据的三十二分之一的空间就完成了。
遇到的问题:
现在,我们面临的最最重要的问题是:我们的电脑无法直接对位进行操作!!!
解决问题的思路:
问题到这里,似乎成了一个死结,我们只能用一个byte表示一个int了,节省四分之三的空间,但这远远达不到需求。
试想,我们能否通过byte间接操作bit呢?
一个byte占据八位的存储空间,如果我们找到了一种方法使得一个byte表示八个整型数据,就间接找到了我们理想化的方法。
实际解决步骤:
下面开始讨论这个大数组排重问题的具体实现思路。
1)创建一个byte数组,长度为2的29次方,把所有的byte置0。
2)对应输入的int型数据,先对8取整得m,并把byte[m]转化为二进制数表示。
3)对8取余得到n,将byte[m]的第n位置1。(对于这部分代码,可以当做字符串来处理,当然,熟悉位操作的同学可以通过移位实现。)
到这里,腾讯的用户统计问题就解决了。童鞋们,开始写代码喽。
推荐阅读
-
BitMap 博客分类: 寒假小结 BitMap
-
LZW字典压缩 博客分类: 压缩小结 LZW字典压缩java解压
-
工作中遇到的mysql+mybatis的问题小结 博客分类: mysql
-
Spring AOP 学习小结 博客分类: Spring AOPSpring正则表达式JDKXML
-
hbase基础小结 博客分类: 研发前沿精品转载 hbasenosql
-
监督学习算法小结(1):决策树 博客分类: 机器学习
-
监督学习算法小结(1):决策树 博客分类: 机器学习
-
定时自动操作数据库——Oracle JOB 用法小结 博客分类: Oracle OracleSQL工作J#
-
定时自动操作数据库——Oracle JOB 用法小结 博客分类: Oracle OracleSQL工作J#
-
泛型小结 博客分类: Java CC++C#