算法无国界,Bitmap算法用来说明在流方式的数据处理过程之中,特定维度下的UV值的计算。
Bitmap算法思想:
32位机器上,一个整形,比如int a,在内存中占32bit位,可以用对应的32bit位对应十进制的0-31个数,bitmap算法利用这种思想处理大量数据的排序与查询。
Bitmap算法优劣:
- 优点: 1.运算效率高,不许进行比较和移位;2.占用内存少,比如N=10000000;只需占用内存为
N/8=1250000Byte=1.25M
。 - 缺点: 所有的数据不能重复。即不可对重复的数据进行排序和查找。
Bitmap算法举例:
- 第一个4就是
00000000000000000000000000010000 - 输入2的时候
00000000000000000000000000010100 - 输入3的时候
00000000000000000000000000011100 - 输入1的时候
00000000000000000000000000011110
算法理解:思想比较简单,关键是十进制和二进制bit位需要一个map图,把十进制的数映射到bit位。
参考文章: 浅谈bitmap算法 & 流方式计算UV的基数算法
近期评论