🍕 资源限制(大数据)
资源限制技巧：
- 哈希函数可以把数据按照种类均匀分流
- 布隆过滤器用于集合的建立与查询，并可以节省大量空间
- 一致性哈希解决数据服务器的负载管理问题
- 利用并查集结构做岛问题的并行计算
- 位图解决某一范围上数字的出现情况，并可以节省大量空间
- 利用分段统计思想、并进一步节省大量空间
- 利用堆、外排序来做多个处理单元的结果合并
【TIP】: 面试中面试官往往不会给你一个清晰的问题。 需要你自己通过问面试官的方式 “澄清问题”。 这也是一种能力。
TOP 词汇
有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL。 【补充】: 某搜索公司一天的用户搜索词汇是海量的(百亿数据量)，请设计一种求出每天热门Top100词汇的可行办法
【方法】: 利用 “二维堆”。
- 首先，将总的文件分批次处理，每一个批次都是一个大根堆 a。
- 然后，将每一个大根堆 a 中的堆顶元素加到大根堆 b 中，组成一个总大跟堆 b。
- 当从大根堆 b 中弹出最大值后，将这个最大值从其所对应的 a 堆删掉，然后继续从对应的 a 堆中添加一个元素到总的大根堆。
- 如此反复，从 b 中弹出 100 个元素，就得到了前 100 个大的数。
- 因为都是使用堆结构，所以代价是 log 级别的
- 总结思路： 总的大根堆始终存储每一个大根堆的最大值。 类似于二维大根堆 —— 在许多个大根堆上再组成一个大根堆。
统计出现两次的数字
32位无符号整数的范围是0~4294967295，现在有40亿个无符号整数，可以使用最多1GB的内存，找出所有出现了两次的数 【补充】: 可以使用最多10KB的内存，怎么找到这40亿个整数的中位数?
原问题同样有两种解法：
- 利用哈希分流。分批次处理，由于哈希的性质，能够保证划分均匀，并且相同的数字出现在同一组。
- 利用位图，只不过这一次是两个位表示一个信息。
补充问题解法：
- 利用范围统计词频来解决。
- 一个数字占 4 字节，10KB 最多能有2500个字节，找最近的 2 的幂次是 2048。于是利用该内存创建一个 2048 字节大小的数组
- 然后将 40 亿个数，按照范围划分成 2048 份，即数组的每个位依次统计
0~2048,2048~2048*2-1,2048*2~048*3-1... 上有多少个数字（词频）。 - 统计完成后，依次累加，比如累加 a[0] 到 a[400] 时，总的词频为 18 亿。 而 a[401] 值为 3 亿
- 则我们能肯定中位数一定出现在 a[401] 范围上。 并且是 a[401] 范围上的第 2 亿个数。
- 于是我们在
2048*401~2048*402-1这个范围上继续划分成 2048 份，然后找到第 2 亿个数。 - 依次类推，不断逼近，最终就能够找到中位数。
排序
现在有 10G 大小的有符号整数，要求只用 5G 内存对其排序。
【方法1】: 计算内存能够将范围划分成几份，然后从最小范围开始，依次进行排序输出。 【方法2】: 利用一个基地加大根堆的方法。
【方法2举例说明】:
- 假设现在有 10 个数字，然后创建一个大根堆，但内存只支持该大根堆中最多有 3 条数据，数据的组织形式是 "值:出现次数"。如何排序
- 因为数字是有符号整数，所以最开始的基底是
，然后利用大根堆找到最小的三个数，具体方法如下： - 遍历 10 个数字
- 当大根堆为空时，直接将遍历到的数字添加进去。
- 不为空时，因为我们要的是最小的数字，所以只有当遍历到的数字比大根堆的最大值 小 时，才会将该数字添加进去，同时弹出大根堆中最大的数字
- 一轮下来，我们就能得到 10 个数字中最小的三个数。 然后对这三个数进行排序，然后存储到硬盘中。
- 一轮过后，基底需要变成大根堆中最大的哪个数，然后开始新的一轮遍历，只不过小于基底的数字忽略
- 重复几轮，就能够实现用小内存对大数据进行排序。
回看题目，告诉你内存 5G，就是用来看看内存能够支持一个大根堆存储多少条数据。 剩下的方法和举例中的一样，只不过是 10 或者 10 亿的区别。