目录

大数据与空间限制

背景知识

布隆过滤器

布隆过滤器,就是将一个对象给N个互相独立的hash函数去hash一波得到的N个值 再去对要存放的数组进行求余, 那个数组是一个BitMap,(要么为0要么为1) 将得到的余数去对应的数组涂黑

检查某个数是否在数组中:

将该对象去给N个hash函数hash再求余,去bitMap中一个个找,如果全是黑的,那么说明在 不全是黑说明不在

如何生成布隆过滤器:

  • 对于输入的数据量n和失误率p，布隆过滤器的大小m：m = - (n*lnp)/(ln2*ln2)，计算结果向上取整
  • 需要的哈希函数的个数k：k = ln2 * m/n = 0.7 * m/n
  • 由于前两步都进行了向上取整，那么由前两步确定的布隆过滤器的真正失误率p：p = (1 - e^(-nk/m))^k

题目

40亿个无符号数 找出不存在的数

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

10亿字节算1G 使用位图去计算 0->42亿的bit数组去表示每一个数是否出现过 出现了就描黑 42亿/8 < 10亿字节

如何做出1万亿的bit?

如果拿一维数组下标来看的话 是无法达到的 这时候可以用二维数组来 每一行人为规定是1千万个bit

使用long类型的2维数组 第x位bit如何确定位置 让第x位除以1千万 定位是哪一行 再用x-第几个千万 再除64 定位到哪一个数

进阶

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

分组思想: 将某一范围的数进行分组 再去对应的组中进行遍历查找 找到不满足条件的 再去不满足条件的组中 进行进一步的查找

举例:

某一类 范围为0 ~ 1200 但只有1000个实例 如何找到没出现的数

将0 ~ 1200 进行分组

0 ~ 99 100 ~ 199 …. 1100 ~ 1199 1200

再遍历1000个实例 若 遍历为 120 则将 100 ~ 199 区间的词频 + 1 最终找到区间少于100的 再遍历对应的组 缩小范围

解答:

10MB->Byte => 80M bit

42亿/8千万 =  60

int[] 长度 60 

int[0] : 第一个8千万

int[1] : 第二个8千万

遍历寻找小于8千万的 再次进行分组

再度进阶

内存限制为10kb 只用找到一个没出现过的数

10kb=> 1000/4 = 250 int[] 长度:250

42亿分250份 统计 找出不满足个数的区间例:[ a - b ] 
再对[a,b]进行划分 250 分 再找不满足条件的 释放内存 进行划分

再再进阶

给你几个变量 求42亿中的中位数

0--------|------42亿
        mid
        找到(2^32 - 1 ) / 2 中位数
0----|----2^32 - 1 / 2
     mid
        直到为1

将10亿无序文件排好序 都在磁盘 内存给定为10MB

内存中创建个 大根堆 放入最小的1万数 算出1万个数后
放入0号文件 拿到0号文件的最大值 假定为5000
以后遍历的时候碰见小于5000的不理会 再次放到1号文件 又一个1万
依次这样

找出重复的URL

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

对于要求时间: 
1. 将100亿的URL进行hash
2. 然后分散到机器上 
3. 搞成文件
4. 分别进行统计
要求空间: 则使用布隆过滤器 判断 存在在过滤器的就进行记录 最后一起返回 表示有重复的
可以减少内存

进阶

某搜索公司一天的用户搜索词汇量是海量的 设计一种求Top100的词

用户进行正常的请求的话 正常返回给它就是
但服务器此时要异步的记录url 将string发给机器
然后分散给不同的文件 从各文件求出Top100

如何排序

拿外排的话  3 个文件 先各自大->小 排好来 进行对比 0
1 2 选 17 9 100对比 选走K  然后移到 Z 再比较 
拿走 A移到B 再比较拿到E 如此 复杂度O(N)

二维堆排序
0 1 2组成一个堆 A   A D K 比较的话 这三入堆 B
选出最大的K 弹出 然后 Z 入堆 然后再弹出最大的
复杂度O(NlogN)

去内存限制为1GB 找到一个出现过2次的数

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

选择两个bit 作为位图的位

  • 00 0 次
  • 01 1 次
  • 10 2 次
  • 11 大于 2次

进阶

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

分段统计

第一段出现 a 个 第二段 b 个 第三段 c 个 ..依次累加 达到20亿个或者刚超过20亿个 到刚好超过的那个区间 去划分

总结

大数据题目的解题技巧

  • 哈希函数可以把数据按照种类均匀分流
  • 布隆过滤器用于集合的建立与查询，并可以节省大量空间
  • 一致性哈希解决数据服务器的负载管理问题
  • 利用并查集结构做岛问题的并行计算
  • 位图解决某一范围上数字的出现情况，并可以节省大量空间
  • 利用分段统计思想、并进一步节省大量空间
  • 利用堆、外排序来做多个处理单元的结果合并