Skip to content

Latest commit

 

History

History
262 lines (176 loc) · 6.39 KB

基础提升06.md

File metadata and controls

262 lines (176 loc) · 6.39 KB
Raw

6. 大数据题目、位运算

资源限制类题目

MyBit.cpp

6.1 大数据题目的解题技巧

之前的课已经介绍过前4个内容，本节内容为介绍解决大数据题目的后3个技巧

  1. 哈希函数可以把数据按照种类均匀分流

  2. 布隆过滤器用于集合的建立与查询，并可以节省大量空间

  3. 一致性哈希解决数据服务器的负载管理问题

  4. 利用并查集结构做岛问题的并行计算

  5. 位图解决某一范围上数字的出现情况，并可以节省大量空间

  6. 利用分段统计思想、并进一步节省大量空间

  7. 利用堆、外排序来做多个处理单元的结果合并

6.2 分段统计思想

32位无符号整数的范围是0~4,294,967,295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数？

原问题：

要描述所有的数需要的内存：

  • 准备一个长度为2^32的bit类型的数组

  • 2^32/8Byte = 2^29 = 536870912 = 536MB

[进阶]

  • 内存限制为10MB，但是只用找到一个没出现过的数即可

  • 内存限制为3KB

分析：

  • 一个无符号整数占4Byte，3KB/4 = 750 约等于 2^9 = 512

  • 将整个范围分成512份，进行词频统计，一定有一份的数量是少的

  • 把定位到的范围继续分为512份，进行词频统计，一定会有一份的数量是少的，反复进行

[进进阶]

只能申请有限个变量，如何统计

  • 二分寻找不满的部分，最多过32次大文件

6.3 堆

有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL

分析：

  • 布隆过滤器（边添加边查询，有失误率）

  • 哈希函数分流（将大文件分成小文件）

[补充]

某搜索公司一天的用户搜索词汇是海量的（百亿数据量），请设计一种求出每天热门Top100词汇的可行办法

  1. 通过哈希分流将大文件分成小文件，通过词频统计确定每个小文件的Top100，大根堆的形式

  2. 把每个大根堆的堆顶拿出来，单独组成一个大根堆(总堆)

  3. 从总堆中弹出一个元素，查看它属于哪个小文件，将该文件的堆顶弹出，让新的堆顶进入总堆

6.4 位图

32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数。

方法一：

  • 哈希函数分流

方法二：

  • 位图
一个位只能表示出现过和没出现过，所以使用两个位信息表示数字出现的状态

00：0次

01：1次

10：2次

11：2次以上

2^32 * 2 bit / 8 = 636MB

[补充]

可以使用最多10MB的内存，怎么找到这40亿个整数的中位数？

  • 分段统计思想

  • 10KB能申请多大的无符号整型数组：10KB / 4B = 2500 -> 2048 = 2^11

  • 将整个范围分成2048份，遍历40亿个数，进行词频统计，寻找第20亿个数

6.5 腾讯原题

10G文件中为无序的有符号整数，只给5G内存，如何输出新的文件10G，保证是有序的

方法一：小根堆

  • 小根堆进行词频统计，一条记录 8Byte + 额外空间消耗 -> 16Byte

  • 5G/16Byte = 5*2^26 -> 2^27条记录

  • 用小根堆先统计最低范围上的数字出现的状况，依次移动范围

方法二：大根堆

  • 大文件中10个数，做一个只放3条记录的大根堆，依次过大文件，找到所有数字中最小的3个数，按照值进行排序，输出到新的大文件中

  • 更改门槛值Y，重复进行

6.6 位运算

1. 不用比较判断

给定两个有符号32位整数a和b，返回a和b中较大的。

[要求]

不用做任何比较判断。

返回 a:

  1. a 和 b 的符号相同 && a - b >= 0
  2. a 和 b 的符号不相同 && a > 0
// 请保证参数 n 不是 1 就是 0
// 1 -> 0
// 0 -> 1 
int flip(int n){
    return n ^ 1;
}
// n 是非负数，返回 1
// n 是负数， 返回 0
int sign(int n){
    return flip( (n >> 31) & 1 );
}
// bug: a - b 可能溢出
int getMax1(int a, int b){
    int c = a - b;
    int scA = sign(c);      // a - b 为非负，scA为 1；a - b 为负，scA为 0
    int scB = flip(scA);    // scA为0，scB为1；scA为1，scB为0
    return a * scA + b * scB;
}
int getMax2(int a, int b){
    int c = a - b;
    int sa = sign(a);
    int sb = sign(b);
    int sc = sign(c);
    int difSab = sa ^ sb;       // a 和 b 的符号不一样为1，一样为0
    int sameSab = flip(difSab); // a 和 b 的符号不一样为0，一样为1
    int returnA = difSab * sa + sameSab * sc;
    int returnB = flip(returnA);
    return a * returnA + b * returnB;
}

2. 判断一个32位正数是不是2的幂、4的幂

2的幂：

  • 二进制中只有一个1

方法一：取出最右侧的 1 与原数比较

方法二：

  • X 只有一个1
  • X-1 会将原来唯一的1打散
  • X & (X-1) == 0

4的幂：

  • 先判断是否是2的幂
  • X & 0101...01 ≠ 0
bool is2Power(int n){
    return (n & (n - 1)) == 0;
}
bool is4Power(int n){
    return (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}

3. 加减乘除

给定两个有符号32位整数a和b，不能使用算术运算符，分别实现a和b的加、减、乘、除运算

[要求]

如果给定a、b执行加减乘除的运算结果就会导致数据的溢出，那么你实现的函数不必对此负责，除此之外请保证计算过程不发生溢出

// 加法
int myAdd(int a, int b){
    int sum = a;
    while (b != 0){
        sum = a ^ b;        // 无进位相加
        b = (a & b) << 1;   // 进位信息
        a = sum;
    }
    return sum;
}

// 减法
int MyMinus(int a, int b){
    return myAdd(a, negNum(b));
}
// 相反数
int negNum(int n){  
    return myAdd(~n, 1);
}

// 乘法
int MyMulti(int a, int b){
    int res = 0;
    while(b != 0){
        if((b & 1) != 0){
            res = myAdd(res, a);
        }
        a <<= 1;
        b >>= 1;    // 需要无符号右移
    }
    return res;
}

// 除法
int myDiv(int a, int b){
    int x = isNeg(a) ? negNum(a) : a;
    int y = isNeg(b) ? negNum(b) : b;
    int res = 0;
    for(int i = 31; i > -1; i = MyMinus(i, 1)){
        if((x >> i) >= y){  // 右移更安全，y左移可能溢出
            res |= (1 << i);
            x = MyMinus(x, y << i);
        }
    }
    return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}
bool isNeg(int n){
    return n < 0;
}