几道和「黑洞照片」那种海量数据有关的算法问题

待我称王封你为后i 2022-04-24 05:46 112阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

昨晚被一则新闻刷屏：北京时间 4 月 10 日今晚 9 点，人类首张黑洞照片正式发布。

看到这张图片，小吴心里是极为震撼的：爱因斯坦太太太太太牛逼了！！！

同时，看新闻的时候小吴还注意到里面有个细节，给黑洞”拍照“的事件视界望远镜从 2017 年就开始为黑洞拍照了，但直到 2019 年才公布。

心里不禁纳闷：为什么给黑洞拍照需要这么长时间？

于是去更加详细的搜索资料，果然发现了端倪，其中一个点就是 **望远镜观测到的数据量非常庞大** ！

2017 年时 8 个望远镜的数据量达到了 10PB（=10240TB），2018 年又增加了格陵兰岛望远镜，数据量继续增加。庞大的数据量为处理让数据处理的难度不断加大。

数据运输花了很长时间，最后用飞机花了几个月来运输这千万亿大小的字节数据。

平时面试的时候老是说海量数据，海量数据，这次的数据真的是海量数据了。

这次的数据流之大，导致每个射电望远镜产生的数据，都只能用硬盘来储存。

那么现在问题来了，假设你作为给黑洞拍照的研发人员，给你一台内存有限的计算机，你如何找出这些数据的中位数或者判断某个数字是否存在里面。

## 1. 海量数据查找中位数 ##

### 题目描述 ###

海量数据查找中位数\[1\]：

现在有 10 亿个 int 型的数字（ java 中 int 型占 4B），以及一台可用内存为 1GB 的机器，如何找出这 10 亿个数字的中位数？

所谓中位数就是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

### 题目解析 ###

题目中有 10 亿个数字，每个数字在内存中占 4B，那么这 10 亿个数字完全加载到内存中需要：10 \* 10^8 \* 4，大概需要 4GB 的存储空间。根据题目的限制，显然不能把所有的数字都装入内存中。

这里，可以采用基于 **二进制位比较** 和 快速排序算法中的 **分割思想** 来寻找中位数，实际上这也是 **桶排序** 的一种应用。

![640?wx\_fmt=gif][640_wx_fmt_gif]

假设将这 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。

在数组中的每一位都是二进制位。

布隆过滤器除了一个位数组，还有 K 个哈希函数。当一个元素加入布隆过滤器中的时候，会进行如下操作：

•使用 K 个哈希函数对元素值进行 K 次计算，得到 K 个哈希值。•根据得到的哈希值，在位数组中把对应下标的值置为 1。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

举个例子，假设布隆过滤器有 3 个哈希函数：f1, f2, f3 和一个位数组 `arr`。现在要把 `2333` 插入布隆过滤器中：

•对值进行三次哈希计算，得到三个值 n1, n2, n3。•把位数组中三个元素 arr\[n1\], arr\[n2\], arr\[3\] 都置为 1。

当要判断一个值是否在布隆过滤器中，对元素进行三次哈希计算，得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

**小吴在前不久专门分析讲解过此题，[更加详细的讲解请点击这里查看~][Link 1]**

### References ###

`[1]` 海量数据查找中位数: *https://www.cnblogs.com/hapjin/p/5769087.html*

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 2]

[数据结构与算法： 三十张图弄懂「图的两种遍历方式」][Link 3]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 4]

[几道和散列（哈希）表有关的面试题][Link 5]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 6]

[几道和「堆栈、队列」有关的面试算法题][Link 7]

[链表算法面试问题？看我就够了！][Link 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png]

![640][]戳 “阅读原文”前往小吴的个人博客一起充电学习!

[640_wx_fmt_jpeg]: /images/20220218/a9546fa4137446bcb41ee87fba1db63d.png
[640_wx_fmt_gif]: /images/20220218/2c0fc6cf51b246659b66bbc5cda49576.png
[640_wx_fmt_jpeg 1]: /images/20220218/b73b478adeec41d3be758ec61f7900c9.png
[640_wx_fmt_gif 1]: /images/20220218/58da5bcba62747db82eab1771d4667a5.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485051&idx=2&sn=621c39a76cab27e0bacdaa5bdc804b1c&chksm=fa0e69facd79e0ec39807f41046c57ac2cf2fb589aa5a4a59384bd3cd616c7a9d068ff6ea883&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 8]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 2]: /images/20220218/fc719bcaab064e2baabefa48d788fefc.png
[640_wx_fmt_png]: /images/20220218/56c0544707c740c69feb99de80dc511a.png
[640]: /images/20220218/4f9ff43a773041c0ab3ea1f03b1305ea.png