大量数据处理

bitMap

可以运用在快速查找、去重、排序、压缩数据等。

将整数n放置在第n个bit位，扫描后按左至右或右至左输入即为排好序的。
https://www.cnblogs.com/dyllove98/archive/2013/07/26/3217741.html
https://www.cnblogs.com/senlinyang/p/7885685.html
题目：一个10G的文件，里面全部是自然数，一行一个，乱序排列，对其排序。在32位机器上面完成，内存限制为 2G。

首先来分析一下题目，10G的文件，只有2G内存，显然，不可能一次性把数据放入内存中直接排序。那么，还有什么其他办法呢？遍寻资料，可以发现大致有两种解决方案：

1、把大文件分成多个小文件，分别排序，到最后合并成一个文件（我暂时还没搞懂这个方法，所以不会描述，有兴趣的看官可以自己去查一下）；

2、另外一种方法就是著名的bitmap算法了。
https://www.jianshu.com/p/bf9dbbc147ed

//arr[n]的第m位置1
void setBit(int num,int arr[])
{
    int n = num / 32;
    int m = num % 32;
    arr[n] += (1 << m);
}
//地位至高位打印
void printBitMap(int arr[],int len)
{
    for (int i = 0; i<len; i++)
    {
        int n = 1;
        for (int ii = 0; ii < 32; ++ii)
        {
            if ((arr[i] & n) == n)//这里时==n，不是==1
            {
                cout << i * 32 + ii << endl;
            }
            n <<= 1;
        }
    }
}
void clr(int arr[], int len)
{
    for (int i = 0; i < len; ++i)
        arr[i] = 0;
}
int main()
{
    int arr[100];
    int arr2[10] = { 100,800,22,314,21,44,0,1,3,2 };
    clr(arr,100);
    for(int i = 0; i < 10; ++i)
    {
        setBit(arr2[i], arr);
    }
    printBitMap(arr, 100);
    return 0;
}

0
1
2
3
21
22
44
100
314
800

bitset

https://www.cnblogs.com/RabbitHu/p/bitset.html
http://www.cplusplus.com/reference/bitset/bitset/
C++封装的bitMap，是模板类

#include<bitset>
int main()
{
    bitset<32> bs(3);//相当于...0011
   // bs.set(3);
    cout << bs.count() << endl;//3
    bs.set(4);//第5位置1
    cout << bs.size() << endl;//32
    cout << bs.to_string() << endl;//00000000000000000000000000010011
    cout << bs.to_ullong() << endl;//19
    return 0;
}

#include<bitset>

int main()
{
	bitset<1000> bs;
	vector<int> arr = { 9,2,4,12,100,900,788,20 };
	for (auto a : arr) bs.set(a);
	cout <<"count: " <<bs.count() << endl;
	for (int i = 0; i < bs.size(); i++)
		if (bs[i] == 1)
			cout << i << " ";
}

count: 8
2 4 9 12 20 100 788 900