032014
 

工作中碰到这样一个问题:

有一个文本文件,有上亿行数据,每行数据是 unsigned int。现在需要将其中可能重复的数只保留一个,同时和另外一个或多个这样的文件进行排重(即和它们做差集)。要求尽可能快的筛选出来。

开始实现比较简单粗暴,将数据直接通过 LOAD DATA INFILE 导入 MySQL 表中,然后多表之间做 LEFT JOIN。数据不是特别大,比如几千万,且就要排重的文件不多时,比如一个,速度还可以接受。然而,当数据上亿,且有多个文件需要排重时,性能急剧下降,必须进行优化。而这,正是 Bitmap 的应用场景。

1、Bitmap 概念

Bitmap 是一个十分有用的数据结构。所谓的 Bit-map 就是用一个 bit 位来标记某个元素对应的 Value,而 Key 即是该元素。由于采用了 Bit 为单位来存储数据,因此在内存占用方面,可以大大节省。(《编程珠玑》第一章引入的问题,提到了 Bitmap)

2、Bitmap 的实现原理

以一个简单的数组排序来说明 Bitmap 的实现原理:array[4,6,3,1,7]

Bitmap 采用的是以空间换时间的思想,数组中最大元素值为7,所以在内存中开辟8位的存储空间,存储空间大小的确定方法是(元素最大值进位到8的倍数/8),之所以除以8,是因为开辟空间的时候以byte为单位,1byte=8bit。

开辟8位的空间后,每位初始化为0,如下表:

0号位 1号位 2号位 3号位 4号位 5号位 6号位 7号位
0 0 0 0 0 0 0 0

开始遍历 array 数组,array[0]=4 时,则将 4号位 置1,变为下表:

0号位 1号位 2号位 3号位 4号位 5号位 6号位 7号位
0 0 0 0 1 0 0 0

array[1]=6 时,则将 6号位 置1,变为下表:

0号位 1号位 2号位 3号位 4号位 5号位 6号位 7号位
0 0 0 0 1 0 1 0

直至遍历完 array 数组,空间各位如下表:

0号位 1号位 2号位 3号位 4号位 5号位 6号位 7号位
0 1 0 1 1 0 1 1

最后,从头开始遍历空间中各位,为1的输出其 位号,得:1,3,4,6,7,其效率为O(n)=8

3、Bitmap 编码实现

一般的,静态语言比较容易实现 Bitmap。在下面的实现中,Bitmap 数据结构可以直接定义为 byte 数组,然而,出于使用的方面原因,这里 Bitmap 的实现额外保存了一些其他信息,因此 Go 和 C 中,使用 struct 定义 Bitmap。

从上面的排序例子知道,实现的关键是 置位 和 清位。

3.1 Go 语言实现

Bitmap 数据结构定义如下:

type Bitmap struct {
    // 保存实际的 bit 数据
    data []byte
    // 指示该 Bitmap 的 bit 容量
    bitsize uint64
    // 该 Bitmap 被设置为 1 的最大位置(方便遍历)
    maxpos uint64
}

置位 和 清位 方法:

// SetBit 将 offset 位置的 bit 置为 value (0/1)
func (this *Bitmap) SetBit(offset uint64, value uint8) bool {
     index, pos := offset/8, offset%8

     if this.bitsize < offset {
          return false
     }

     if value == 0 {
          // &^ 清位
          this.data[index] &^= 0x01 << pos
     } else {
          this.data[index] |= 0x01 << pos

          // 记录曾经设置为 1 的最大位置
          if this.maxpos < offset {
               this.maxpos = offset
          }
     }

     return true
}

完整实现代码:Github Bitmap Golang

3.2 C 语言实现

Bitmap 数据结构定义如下:

typedef struct {
     uint64_t bitsize;
     uint64_t maxpos;

     /* 不定长,必须是结构的最后一个成员 */
     uint8_t data[];
} Bitmap;

置位 和 清位 方法:

bool set_bit(Bitmap* bitmap, uint64_t offset, uint8_t value)
{
     uint64_t index, pos;

     index = offset / 8;
     pos = offset % 8;

     if (bitmap->bitsize < offset) {
          return false;
     }

     if (value) {
          bitmap->data[index] |= 1 << pos;

          if (bitmap->maxpos < offset) {
               bitmap->maxpos = offset;
          }
     } else {
          bitmap->data[index] &= BITMAP_MASK ^ (1 << pos);
     }

     return true;
}

相比和 Go 语言版的不同点是,C 没有直接的 清位 操作符

完整实现代码:Github Bitmap C

3.3 Java 语言实现

Bitmap 采用类实现,定义如下成员变量

private byte[] data;

private long bitsize;
private long maxpos;

置位 和 清位 方法:

public boolean setBit(long offset, int value) {
     if (this.bitsize < offset) {
          return false;
     }

     int index = (int) offset / 8;
     int pos = (int) offset % 8;

     if (value == 1) {
          this.data[index] |= 1 << pos;
          if (this.maxpos < offset) {
               this.maxpos = offset;
          }
     } else {
          this.data[index] &= Bitmap.BITMAP_MASK ^ (1 << pos);
     }

     return true;
}

跟 C 语言一样, Java 也没有直接提供 清位 操作符。

完整实现代码:Github Bitmap Java

3.4 三种语言实现的不同点

通过对比三种语言的实现,可以看出一些不同点:

1)数据类型的支持:Go 和 C 可以实现 uint8/uint64,而 Java 不区分是否有符号(Java 8 提供了无符号数);
2)清位操作:Go 提供了清位操作符;而 C 和 Java 需要自己实现,关键点是 0×01 和 MASK 做异或操作;

4、Bitmap 具体实现的关键点

从上面三种语言的具体实现可以看出,Bitmap 实现的关键有如下几点:

1)使用 byte 数组保存数据,这样可以极大的节省内存空间;
2)某个元素(也就是某个位置)要置为0或1,通过对 8 (1byte=8bit) 做除法和取余来实现;
3)具体的置位或清位,使用位操作实现:没有直接提供操作符的,可以通过多种操作符组合实现;

5、Bitmap 更多应用

一般地涉及到无重复、int 类型的问题,可以考虑 Bitmap 是否能够实现。

1)文章开头提到的排重实现(代码见 github 的taskdiff)

2)《编程珠玑》第一章的问题,可以参考《编程珠玑–位图法排序》

3)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数

8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==12.5MBytes,这样,就用了小小的12M左右的内存表示了所有的8位数的 电话)

4)2.5亿个整数中找出不重复的整数的个数(内存空间不足以容纳这2.5亿个整数)

将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上,在遍历这些数的时候,如果对应位置的 值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个 2bit-map,都是一样的道理。

6、题外话

用三种语言实现的Bitmap进行排重处理,C 和 Java 版本速度差不多,1.5 亿数据60秒内处理完;而 Go 版本需要 1分50秒 左右(主要 bufio 包性能不太理想);内存占用方面,C 最少,Go 次之,Java 最多。

  3 条评论 到 “Bitmap 多语言实现及应用”

评论 (3)
  1. 编程珠玑上的C实现感觉更好

  2. 第一次看到,真的很不错

  3. 凡事须适可而止。

 评论

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>