模拟大数据处理之——bitset

模拟类似的题目：在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。

解决方法：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

注：下面的代码中使用两个bitset代表相邻的两个bit。第一个bitset中对应bit位为1表示这个位置对应的数存在，第二个bitset中对应的位为1表示这个位置对应的数重复出现。

c++代码如下：

#include<iostream>
#include<bitset>

void create_original_data()   //产生原始大数据文件
{
    int rand_number;
    unsigned int number=20;
    srand(0);
    FILE* original_file_pointer=fopen("./original_data","w");
    for(int i=0;i<2e4;i++)   //此处声称20000个数而不是2.5亿个数，因为只是模拟
    {
        number=(unsigned int)rand()+(unsigned int)rand();
        fprintf(original_file_pointer,"%un",number);
    }
    fclose(original_file_pointer);
}
int main()
{
    create_original_data();
    std::bitset<0xffffffff>* bits_1=new std::bitset<0xffffffff>;
    std::bitset<0xffffffff>* bits_2=new std::bitset<0xffffffff>;

    unsigned int bit_index;

    (*bits_1).reset();
    (*bits_2).reset();
    FILE* original_file_pointer=fopen("./original_data","r");
    FILE* output_file_pointer=fopen("./output_data","w");
    for(int i=0;i<2e4;i++)
    {
        fscanf(original_file_pointer,"%u",&bit_index);
        if(!(*bits_1).test(bit_index))       
            (*bits_1).set(bit_index);
        else
            (*bits_2).set(bit_index);
    }

    fseek(original_file_pointer,0L,SEEK_SET);   
    for(unsigned int i=0;i<2e4;i++)
    {
        fscanf(original_file_pointer,&bit_index);
        if((*bits_1).test(bit_index))
        {
            if(!(*bits_2).test(bit_index))
                fprintf(output_file_pointer,bit_index);
        }
    }

    delete bits_1;
    delete bits_2;
    fclose(original_file_pointer);
    fclose(output_file_pointer);
    return 0;
}