海量数据处理之位图法

位图法就是bitmap的缩写。所谓bitmap,就是用每一位(bit单位)来存放某种状态,节省了大量的空间,适用于大规模数据,但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。正因为位图运算在空间方面的优越性,很多语言都有直接对它的支持。如在C++的STL库中就有一个bitset容器。而在Java中,在java.util包下也有一个BitSet类用来实现位图运算。引用bitset介绍:

A bitset is a special container class that is designed to store bits (elements with only two possible values: 0 or 1,true or false, …).The class is very similar to a regular array, but optimizing for space allocation: each element occupies only one bit (which is eight times less than the smallest elemental type in C++: char).Each element (each bit) can be accessed individually: for example, for a given bitset named mybitset, the expression mybitset[3] accesses its fourth bit, just like a regular array accesses its elements.

转载整理至:

  1. 《编程珠玑》第一章
  2. https://blog.csdn.net/yangquanhui1991/article/details/52172340
  3. https://blog.csdn.net/jackywgw/article/details/51507003?utm_source=blogxgwz2

位运算

1 byte (字节)= 8 bit(位);  1 KB = 1024 B(字节);

1 MB = 1024 KB;  1 GB = 1024 MB;  1 TB = 1024 GB; 

与(&)0&0=0 1&0=0 0&1=0 1&1=1
或(|)0|0=0 1|0=1 0|1=1 1|1=1
异或(^)0^0=0 1^0=1 0^1=1 1^1=0

左移运算

左移运算符m<<n表示把m左移n位。

在左移n位的时候,最左边的n位将被丢弃,同时在最右边补上n个0。

00001010<<2=00101000
10001010<<3=01010000

右移运算

右移运算符m>>n表示把m右移n位。

在右移n位的时候,最右边的n位将被丢弃。左边的处理情况分两种:

  1. 如果数字是一个无符号数值,则用0填补最左边的n位。
  2. 如果数字是一个有符号数值,则用数字的符号位填补最左边的n位。也就是说,如果数字原先是一个正数,则右移之后在最左边补n个0,如果数字原先是负数,则右移之后在最左边补n个1
00001010>>2=00000010
10001010>>3=11110001

位运算小题

请实现一个函数,输入一个整数,输出该数二进制表示中1的个数。

int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        ++count;
        n = (n - 1) & n;
    }
    return count;
}

bitmap

腾讯面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

分析

40亿数据 = 4 * 109个数,假设:unsigned int = 32bit = 4byte

4 * 109 * 4byte ~= 14.9G ~= 16G

如果用bitmap来存储:4 * 109 bits ~= 476.84M ~= 512M = 536870912 byte

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TOTAL_DATA_SIZE 300 //4000000000  /*40亿个不重复的unsigned int整数大数据*/
//#define MAX_BUFFER_SIZE 536870912   /*512MB*/
typedef char bitmap_type;
#define BITMAP_BITS (sizeof(bitmap_type)*8)
#define MAX_BUFFER_SIZE ((TOTAL_DATA_SIZE+BITMAP_BITS-1)/BITMAP_BITS)
 
#define bitmap_set(b,v) (b[(v)/BITMAP_BITS] |= (1 << ((v)%BITMAP_BITS)))
#define bitmap_clear(b,v) (b[(v)/BITMAP_BITS] &= ~(1 << ((v)%BITMAP_BITS)))
#define bitmap_isset(b,v) (b[(v)/BITMAP_BITS] & (1 << ((v)%BITMAP_BITS)))
#define bitmap_zero(b) memset(b,0,sizeof(bitmap_type)*MAX_BUFFER_SIZE)
 
#define DATA_FILE_NAME "data.txt"
  
int main(int argc, char*argv[])
{
    bitmap_type *bitmap = NULL;
    FILE *fp;
    unsigned int num;
    bitmap = (bitmap_type*)malloc(sizeof(bitmap_type)*MAX_BUFFER_SIZE);
    if(bitmap == NULL) {
        printf("bitmap malloc error\n");
        return -1;
    }
    bitmap_zero(bitmap);

    fp = fopen(DATA_FILE_NAME,"rb");
    if(fp == NULL) {
        printf("fopen file %s error\n",DATA_FILE_NAME);
        return -1;
    }
    fclose(fp);
    while(fscanf(fp,"%d",&num) != EOF) {
        bitmap_set(bitmap,num);
    }
    if(bitmap_isset(bitmap,1)) {
        printf("2 is set in the bitmap\n");
    }
    if(bitmap_isset(bitmap,672)) {
        printf("222 is set in the bitmap\n");
    }else {
        printf("222 is not in the bitmap\n");
    }
    if(bitmap_isset(bitmap,88888)) {
        printf("333 is set in the bitmap\n");
    }else {
        printf("333 is not in the bitmap\n");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据