专栏首页五分钟学算法几道和「黑洞照片」那种海量数据有关的算法问题

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

昨晚被一则新闻刷屏:北京时间 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 的存储空间。根据题目的限制,显然不能把所有的数字都装入内存中。

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

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

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

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

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

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

References

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

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你真的会正确地调试TensorFlow代码吗?

    当谈到在 TensorFlow 上写代码时,我们总会将它和 PyTorch 进行对比,然后讨论 TensorFlow 框架是多么的复杂以及 tf.contrib...

    机器之心
  • 『互联网架构』软件架构-zookeeper之源码分析和运维总结(37)

    PS:zookeeper就告一段落了,zookeeper互联网的奠基石,这个一定要理解原理,有基本的使用,架构之路必须要翻越的一面墙

    IT故事会
  • 从零开始再造打爆李世石的AlphaGo:创造能下围棋的机器人

    我们在上节完成了围棋规则和棋盘状态监测功能,本节我们在基于上节的基础上,设计一个能自己下棋的围棋机器人。首先我们设计一个类叫Agent,它的初始化代码如下:

    望月从良
  • 剑指offer java版(二)

    经典的双指针法。定义两个指针,第一个指针从链表的头指针开始遍历向前走k-1步,第二个指针保持不动,从第k步开始,第二个指针也开始从链表的头指针开始遍历,由于两个...

    蜻蜓队长
  • 为什么每个数据科学家都要读一读Judea Pearl的《The Book of Why》

    我热衷于机器学习已经有 4 个年头,对深度学习感兴趣也有一年了。我构建了用于娱乐和工作的预测模型,也了解很多算法,从梯度提升(gradient boosting...

    机器之心
  • 字典书Trie的实现

    用户2436820
  • 为什么现在面试总是面试造火箭?

    很多人总是抱怨面试官问一些平时不常用的知识点,比如算法呀,网络(TCP)等等,也就是大家常说的:面试造火箭,工作拧螺丝。

    桃翁
  • IBM新研究登上Nature封面:两种量子算法解决分类问题

    机器学习和量子计算在技术炒作方面都达到了惊人的程度,除此之外,二者数学基础的某些方面也有着惊人的相似性。今天 Nature 发表了一篇论文《Supervised...

    机器之心
  • 2019BATJ面试题详解:MyBatis+MySQL+Spring+Redis+多线程

    如何通过HibernateDaoSupport将Spring和Hibernate结合起来?

    美的让人心动
  • 香侬科技李纪为:初入NLP领域的一些小建议

    最近在跟同学的邮件、或者知乎留言中的交流中,不少同学尤其是刚入(jin)门(keng)的同学,提到了深度学习背景下做 NLP 科研的很多迷茫。基本可以归纳为如下...

    机器之心

扫码关注云+社区

领取腾讯云代金券