代码练习----位图排序----与大数据处理

傷城~ 2022-04-12 14:24 128阅读 0赞

一道位图排序解决的题目如下：

输入：一个文本文件最多包含n个正整数的字符串，每个数都小于n，逗号间隔，其中n=10000000, 没有重复的整数。  
输出： 按升序排列这些数，并打印输出到另外一个文本文件中。格式也是逗号间隔、允许末尾有逗号。  
约束：算法复杂度为O(N), 接口函数运行时申请内存或栈不超过2M。

对外提供的接口为：   
    int stat(const char \*InFileName, const char \*OutFileName);  
该接口放在BitMapSort.h的头文件中。

BitMapSort.h

#ifndef _EXPR_LOG_H_
    #define _EXPR_LOG_H_
    
    int stat(const char *InFileName, const char *OutFileName);
    
    #endif

BitMapSort.c

#include "BitMapSort.h"
    #include <stdio.h>
    #include <string.h>
    #include <fcntl.h>
    #define BITSPERCHAR 8  
    #define N 10000000
    #define BUFSIZE 1024
    void BitMapSort(const char *InFileName, const char *OutFileName)
    {
        int in  = open(InFileName, O_RDONLY);
        int out = open(OutFileName,O_WRONLY|O_CREAT);
        char datas[N/BITSPERCHAR] = {0};
        char tmp[16] = {0};
        char buffer[BUFSIZE];
        int data = 0;
        int i = 0;
    
        if ((-1 == in) || (-1 == out))
        {
            return; 
        }
        memset(datas,0,sizeof(datas));
    
        while (read(in, buffer, BUFSIZE ) > 0)  
        {     
            for(i=0;i<strlen(buffer);i++)
            {
                if((',' == buffer[i]))
                {
                    datas[data/8] |= (1 << (data%8));
                    /*printf("get:%d,%x\n",data,datas[data/8]);*/
                    data = 0;
                    continue;
                }
                data = data * 10 + (buffer[i] - '0');
            }
        }     
        datas[data/8] |= (1 << (data%8));
        /*printf("get:%d,%x\n",data,datas[data/8]);*/
    
        for(i=0;i< N;i++)
        {
            if(0 != (datas[i/8] & (1 << (i%8))) )
            { 
                /*printf("%d,",i);*/
                sprintf(tmp,"%d,",i);
                write(out, tmp, strlen(tmp));
            }
        }
        close(in);
        close(out);
    }
    void main(void)
    {
        int fd = open("Data.txt",O_WRONLY|O_CREAT);
        char *data = "1,2,3,4,34,42,64,5,67,8,96,342,123,34352,879";
        write(fd, data, strlen(data));
        close(fd);
        BitMapSort("Data.txt","OutData.txt");
    }

MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。概念"Map（映射）"和"Reduce（归约）"

## Bit-map空间压缩和快速排序去重 ##

**1. Bit-map的基本思想**  
　　32位机器上，对于一个整型数，比如int a=1 在内存中占32bit位，这是为了方便计算机的运算。但是对于某些应用场景而言，这属于一种巨大的浪费，因为我们可以用对应的32bit位对应存储十进制的0-31个数，而这就是Bit-map的基本思想。Bit-map算法利用这种思想处理大量数据的排序、查询以及去重。  
　　Bitmap在用户群做交集和并集运算的时候也有极大的便利。

**2. Bit-map应用之快速排序**  
        假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）,我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，如下图：![1344854370_5847.jpg][]

然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0x01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一（如下图）：   
 ![1344854388_8094.jpg][]

然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：   
:![1344854408_4675.jpg][]  
　　遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的，时间复杂度O(n)。  
**优点：**  
　　运算效率高，不需要进行比较和移位；  
　　占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。   
**缺点：**  
　　所有的数据不能重复。即不可对重复的数据进行排序和查找。  
       当数据类似（1，1000，10万）只有3个数据的时候，用bitmap时间复杂度和空间复杂度相当大，只有**当数据比较密集时才有优势**。

**3. Bit-map应用之快速去重**  
　　2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。   
　　首先，根据“内存空间不足以容纳这2.5亿个整数”我们可以快速的联想到Bit-map。下边关键的问题就是怎么设计我们的Bit-map来表示这2.5亿个数字的状态了。其实这个问题很简单，一个数字的状态只有三种，分别为不存在，只有一个，有重复。因此，我们只需要2bits就可以对一个数字的状态进行存储了，假设我们设定一个数字不存在为00，存在一次01，存在两次及其以上为11。那我们大概需要存储空间几十兆左右。  
　　接下来的任务就是遍历一次这2.5亿个数字，如果对应的状态位为00，则将其变为01；如果对应的状态位为01，则将其变为11；如果为11，,对应的转态位保持不变。  
　　最后，我们将状态位为01的进行统计，就得到了不重复的数字个数，时间复杂度为O(n)。

**4. Bit-map应用之快速查询**  
　　同样，我们利用Bit-map也可以进行快速查询，这种情况下对于一个数字只需要一个bit位就可以了，0表示不存在，1表示存在。假设上述的题目改为，如何快速判断一个数字是够存在于上述的2.5亿个数字集合中。  
　　同之前一样，首先我们先对所有的数字进行一次遍历，然后将相应的转态位改为1。遍历完以后就是查询，由于我们的Bit-map采取的是连续存储（整型数组形式，一个数组元素对应32bits），我们实际上是采用了一种分桶的思想。一个数组元素可以存储32个状态位，那将待查询的数字除以32，定位到对应的数组元素（桶），然后再求余（%32），就可以定位到相应的状态位。如果为1，则代表改数字存在；否则，该数字不存在。

**5. Bit-map扩展——Bloom Filter(布隆过滤器)**

Bloom Filter：一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。当一个元素被加入集合中时,通过k各散列函数将这个元素映射成一个位数组中的k个点,并将这k个点全部置为1。

Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive），因此Bloom Filter不适合那些“零错误”的应用场合，而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

eg. 集合表示和元素查询

Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到\{1,…,m\}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0。  
![o_bf1.jpg][]

为了表达S=\{x1, x2,…,xn\}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到\{1,…,m\}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注：如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个“1“处）。     
![o_bf2.jpg][]

在判断y是否属于这个集合时，对y应用k次哈希函数，若所有hi(y)的位置都是1（1≤i≤k），就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有一处指向了“0”位）；y2或者属于这个集合，或者刚好是一个false positive。  
![o_bf3.jpg][]

**6. 总结**  
　　使用Bit-map的思想，我们可以将存储空间进行压缩，而且可以对数字进行快速排序、去重和查询的操作。Bloom Fliter是Bit-map思想的一种扩展，它可以在允许低错误率的场景下，大大地进行空间压缩，是一种拿错误率换取空间的数据结构。

**7. 应用**  
　　适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下  
　　基本原理及要点：使用bit数组来表示某些元素是否存在，比如8位电话号码  
　　扩展：bloom filter可以看做是对bit-map的扩展

问题实例：

*  1. 使用位图法判断整形数组是否存在重复，或不同数字的个数

判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。  
位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到 5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

*  2. 在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数

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

或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map，都是一样的道理。

解法二：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

解法三：（lz）类似解法2，只是划分时按照快排partition一样划分，直到划分到每个块都可以放入内存中。

*  2.1 一个序列里除了一个元素，其他元素都会重复出现3次，设计一个时间复杂度与空间复杂度最低的算法，找出这个不重复的元素。
 *  3.  已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。

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

lz觉得这个是应该用计数排序类似的算法吧，而不是bitmap?

*  4. 给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

解析:bitmap算法就好办多了。申请512M的内存，一个bit位代表一个unsigned int值，读入40亿个数，设置相应的bit位；读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。  
Note: unsigned int最大数为2^32 - 1，所以需要2^32 - 1个位，也就是(2^32 - 1) / 8 /10 ^ 9G = 0.5G内存。

逆向思维优化：usinged int只有接近43亿（unsigned int最大值为232-1=4294967295,最大不超过43亿），所以可以用某种方式存没有出现过的3亿个数（使用数组\{大小为3亿中最大的数/8 bytes\}存储），如果出现在3亿个数里面，说明不在40亿里面。3亿个数存储空间一般小于40亿个。（xx存储4294967296需要512MB， 存储294967296只需要35.16MBxx）

*  5. 给定一个数组a，求所有和为SUM的两个数。

如果数组都是整数（负数也可以，将所有数据加上最小的负数x，SUM += 2x就可以了）。如a = \[1,2,3,4,7,8\]，先求a的补数组\[8,7,6,5,2,1\]，开辟两个数组b1,b2（最大数组长度为SUM/8/2\{因为两数满足和为SUM，一个数<SUM/2，另一个数也就知道了\}，这样每个b数组最大内存为SUM/(8\*2\*1024\*1024) = 128M）,使用bitmap算法和数组a分别设置b1, b2对应的位为1，b1, b2相与就可以得到和为SUM的两个数其中一个数了。

[1344854370_5847.jpg]: https://img-my.csdn.net/uploads/201208/13/1344854370_5847.jpg
[1344854388_8094.jpg]: https://img-my.csdn.net/uploads/201208/13/1344854388_8094.jpg
[1344854408_4675.jpg]: https://img-my.csdn.net/uploads/201208/13/1344854408_4675.jpg
[o_bf1.jpg]: /images/20220412/0b907a3cd6f6404bb17bf1a02e18667d.png
[o_bf2.jpg]: /images/20220412/4e6f3ba608754c638eb5d34cec81f46d.png
[o_bf3.jpg]: /images/20220412/0f0ee4c4be1344fa8231b4e422f5b10b.png