算法无国界,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的基数算法