昨晚被一则新闻刷屏: 北京时间 4 月 10 日今晚 9 点, 人类首张黑洞照片正式发布.
看到这张图片, 小吴心里是极为震撼的: 爱因斯坦太太太太太牛逼了!!!
同时, 看新闻的时候小吴还注意到里面有个细节, 给黑洞 "拍照" 的事件视界望远镜从 2017 年就开始为黑洞拍照了, 但直到 2019 年才公布.
心里不禁纳闷: 为什么给黑洞拍照需要这么长时间?
于是去更加详细的搜索资料, 果然发现了端倪, 其中一个点就是 望远镜观测到的数据量非常庞大 !
2017 年时 8 个望远镜的数据量达到了 10PB(=10240TB),2018 年又增加了格陵兰岛望远镜, 数据量继续增加. 庞大的数据量为处理让数据处理的难度不断加大.
平时面试的时候老是说海量数据, 海量数据, 这次的数据真的是海量数据了.
这次的数据流之大, 导致每个射电望远镜产生的数据, 都只能用硬盘来储存.
那么现在问题来了, 假设你作为给黑洞拍照的研发人员, 给你一台内存有限的计算机, 你如何找出这些数据的中位数或者判断某个数字是否存在里面.
1. 海量数据查找中位数
题目描述
现在有 10 亿个 int 型的数字( java 中 int 型占 4B), 以及一台可用内存为 1GB 的机器, 如何找出这 10 亿个数字的中位数?
所谓中位数就是有序列表中间的数. 如果列表长度是偶数, 中位数则是中间两个数的平均值.
题目解析
题目中有 10 亿个数字, 每个数字在内存中占 4B, 那么这 10 亿个数字完全加载到内存中需要: 10 * 10^8 * 4, 大概需要 4GB 的存储空间. 根据题目的限制, 显然不能把所有的数字都装入内存中.
这里, 可以采用基于 二进制位比较 和 快速排序算法中的 分割思想 来寻找中位数, 实际上这也是 桶排序 的一种应用.
桶排序
假设将这 10 亿个数字保存在一个大文件中, 依次读一部分文件到内存(不超过内存的限制: 1GB ), 将每个数字用二进制表示, 比较二进制的最高位(第 32 位), 如果数字的最高位为 0, 则将这个数字写入 file_0 文件中; 如果最高位为 1, 则将该数字写入 file_1 文件中.
注意: 最高位为符号位, 也就是说 file_1 中的数都是负数, 而 file_0 中的数都是正数.
通过这样的操作, 这 10 亿个数字分成了两个文件, 假设 file_0 文件中有 6 亿个数字, 而 file_1 文件中有 4 亿个数字.
这样划分后, 思考一下: 所求的中位数在哪个文件中?
10 亿个数字的中位数是 10 亿个数排序之后的第 5 亿个数, 现在 file_0 有 6 亿个正数, file_1 有 4 亿个负数, file_0 中的数都比 file_1 中的数要大, 排序之后的第 5 亿个数一定是正数, 那么排序之后的第 5 亿个数一定位于 file_0 中.
也就是说: 中位数就在 file_0 文件中, 并且是 file_0 文件中所有数字排序之后的第 1 亿个数字.
现在, 我们只需要处理 file_0 文件了(不需要再考虑 file_1 文件).
而对于 file_0 文件, 可以同样的采取上面的措施处理: 将 file_0 文件依次读一部分到内存(不超内存限制: 1GB ), 将每个数字用二进制表示, 比较二进制的 次高位(第 31 位), 如果数字的次高位为 0, 写入 file_0_0 文件中; 如果次高位为 1 , 写入 file_0_1 文件中.
现假设 file_0_0 文件中有 3 亿个数字, file_0_1 中也有 3 亿个数字, 则中位数就是: file_0_0 文件中的数字从小到大排序之后的第 1 亿个数字.
抛弃 file_0_1 文件, 继续对 file_0_0 文件 根据次次高位(第 30 位) 划分, 假设此次划分的两个文件为: file_0_0_0 中有 0.5 亿个数字, file_0_0_1 中有 2.5 亿个数字, 那么中位数就是 file_0_0_1 文件中的所有数字排序之后的第 0.5 亿个数.
2. 海量数据中判断数字是否存在
题目描述
现在有 10 亿个 int 型的数字( java 中 int 型占 4B), 以及一台可用内存为 1GB 的机器, 给出一个整数, 问如果快速地判断这个整数是否在这 10 亿数字中?
题目分析
这里可以使用 布隆过滤器 进行处理.
布隆过滤器 (英语: Bloom Filter) 是 1970 年由 Burton Bloom 提出的.
它实际上是一个很长的二进制矢量和一系列随机映射函数.
它可以用来判断一个元素是否在一个集合中. 它的优势是只需要占用很小的内存空间以及有着高效的查询效率.
对于布隆过滤器而言, 它的本质是一个位数组: 位数组就是数组的每个元素都只占用 1 bit , 并且每个元素只能是 0 或者 1.
一开始, 布隆过滤器的位数组所有位都初始化为 0. 比如, 数组长度为 m , 那么将长度为 m 个位数组的所有的位都初始化为 0.
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
---|---|---|---|---|---|---|---|---|---|
0 | 0 | 1 | 。 | 。 | 。 | 。 | 。 | m-2 | m-1 |
在数组中的每一位都是二进制位.
布隆过滤器除了一个位数组, 还有 K 个哈希函数. 当一个元素加入布隆过滤器中的时候, 会进行如下操作:
使用 K 个哈希函数对元素值进行 K 次计算, 得到 K 个哈希值.
根据得到的哈希值, 在位数组中把对应下标的值置为 1.
图 1
举个例子, 假设布隆过滤器有 3 个哈希函数: f1, f2, f3 和一个位数组 arr. 现在要把 2333 插入布隆过滤器中:
对值进行三次哈希计算, 得到三个值 n1, n2, n3.
把位数组中三个元素 arr[n1], arr[n2], arr[3] 都置为 1.
当要判断一个值是否在布隆过滤器中, 对元素进行三次哈希计算, 得到值之后判断位数组中的每个元素是否都为 1, 如果值都为 1, 那么说明这个值在布隆过滤器中, 如果存在一个值不为 1, 说明该元素不在布隆过滤器中.
布隆
小吴在前不久专门分析讲解过此题, 更加详细的讲解请点击这里查看~
参考资料
海量数据查找中位数: https://www.cnblogs.com/hapjin/p/5769087.html
个人网站: https://www.cxyxiaowu.com
公众号: 五分钟学算法
来源: https://www.cnblogs.com/fivestudy/p/10689490.html