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

昨晚被一则新闻刷屏:北京时间 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,说明该元素不在布隆过滤器中。

布隆

总结

以上所述是小编给大家介绍的几道和「黑洞照片」那种海量数据有关的算法问题,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对我们网站的支持!
如果你觉得本文对你有帮助,欢迎转载,烦请注明出处,谢谢!

(0)

相关推荐

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • JS实现的数组去除重复数据算法小结

    本文实例讲述了JS实现的数组去除重复数据算法.分享给大家供大家参考,具体如下: 在JS中经常会遇到去除数组中重复数据的需求,在此介绍四种算法以实现JS数组去重的功能. 1. 速度最快算法:对象键值对法 实现思路:新建一js对象以及新数组,遍历传入数组时,判断值是否为js对象的键,不是的话给对象新增该键并放入新数组. //注意点: 判断 是否为js对象键时,会自动对传入的键执行"toString()",不同的键可能会被误认为一样:例如: a[1].a["1"] .解决

  • C++数据结构与算法之双缓存队列实现方法详解

    本文实例讲述了C++数据结构与算法之双缓存队列实现方法.分享给大家供大家参考,具体如下: "双缓存队列"是我在一次开发任务中针对特殊场景设计出来的结构.使用场景为:发送端持续向接收端发送数据包--并且不理会接收端是否完成业务逻辑.由于接收端在任何情况下停止响应即可能产生数据丢失,因此无法简单的设计一条线程安全队列来对数据写入或读取(读取数据时将队列上锁视为对写入的停止响应). 鉴于此,我的设计思路如下: 接收端首先向A队列中写入数据,然后当数据处理请求到来的时候切换到B队列继续写入,之

  • Python数据结构与算法之图结构(Graph)实例分析

    本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

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

    昨晚被一则新闻刷屏:北京时间 4 月 10 日今晚 9 点,人类首张黑洞照片正式发布. 看到这张图片,小吴心里是极为震撼的:爱因斯坦太太太太太牛逼了!!! 同时,看新闻的时候小吴还注意到里面有个细节,给黑洞"拍照"的事件视界望远镜从 2017 年就开始为黑洞拍照了,但直到 2019 年才公布. 心里不禁纳闷:为什么给黑洞拍照需要这么长时间? 于是去更加详细的搜索资料,果然发现了端倪,其中一个点就是 望远镜观测到的数据量非常庞大 ! 2017 年时 8 个望远镜的数据量达到了 10PB(

  • 分享几道和「滑动窗口」有关的算法面试题

    前言科普:什么是滑动窗口算法 滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合. 假设有数组 [a b c d e f g h ],一个大小为 3 的 滑动窗口 在其上滑动,则有: [a b c] [b c d] [c d e] [d e f] [e f g] [f g h] 一般情况下就是使用这个窗口在数组的 合法区间 内进行滑动,同时 动态地 记录一些有用的数据,很多情况下,能够极大地提高算法地效率. 1. 滑动窗口最大值 题目来源于 LeetCode

  • 与情人「分手告白」的十句话 学口语者必读

    1. I just don't love you anymore. 我不再爱你了. 2. It's really not working. 我们的感情真的行不通. 3. I've met someone else. 我已另结新欢了. 4. We've grown apart. 我们都各自成长了. 5. The magic's gone from our relationship. 我们之间的爱情魔力已经不见了. 6. I think we should be just friends. 我想我们

  • Matlab实现黑洞优化算法的示例代码

    目录 前言 1.概述 1.1黑洞算法 1.2黑洞搜索优化算法 1.3黑洞搜索算法的实现过程 2.Matlab代码实现 2.1主函数 2.2目标函数 2.3黑洞优化算法 3.结果展现 前言 应用的领域很多. 1.概述 1.1黑洞算法 根据黑洞现象原理首次提出BH 算法,它在传统PSO基础上引入了新的机制,有效地提高了收敛速度并防止了陷入局部极值的情况发生;但是该方法却没有提及如何确定黑洞边界和如何处理吸收星体的问题. Hatamlou BH算法进行了完善,让其更加接近于黑洞的自然现状,使其具有黑洞

  • Android WebP 图片压缩与传输

    1. 简介 直到4g时代,流量依然是宝贵的东西.而移动网络传输中,最占流量的一种载体:图片,成为了我们移动开发者不得不关注的一个问题. 我们关注的问题,无非是图片体积和质量如何达到一个比较和谐的平衡,希望得到质量不错的图片同时体积还不能太大. 走在时代前列的谷歌给出了一个不错的答案--WebP. WebP是一种图片文件格式,在相同的压缩指标下,webp的有损压缩能比jpg小 25-34%.而在我自己的测试里,有时候能小50%. 2. 大企业背书 WebP在2010年发布第一个版本,到现在已经6年

  • 中国各个省份简称

    北京市(京)天津市(津)上海市(沪)重庆市(渝)河北省(冀)河南省(豫)云南省(云)辽宁省(辽)黑龙江省(黑)湖南省(湘)安徽省(皖)山东省(鲁)新疆维吾尔(新)江苏省(苏)浙江省(浙)江西省(赣)湖北省(鄂)广西壮族(桂)甘肃省(甘)山西省(晋)内蒙古(蒙)陕西省(陕)吉林省(吉)福建省(闽)贵州省(贵)广东省(粤)  青海省(青)西藏(藏)四川省(川)宁夏回族(宁)海南省(琼) 每个省级行政区的名称和简称,各有由来: 1.京:战国时期称蓟,是「战国七雄」之一燕国的京城.辽国称燕京.金国改称京

  • 从美的原则谈 WWW 网页上的艺术表现

    一:美的原则 什么是美呢? 美的事物应该具备什么条件呢? 我们根据人类美感的共通性可以定出十个美的原则:连续.渐变.对称.对比.比例.平衡.调和.律动.统一.完整. 在讨论美的原则之前,必须先了解「单位形」的意义.单位形是在相同或相似的形象组合中最基本的单位元素.单位形可以单独重复排列,或组成「单位形组合」,再以「单位形组合」为基础,作有规律的反复排列.下列图例说明以一个「单位形」配置构成八种「单位形组合」. 以一个「单位形」配置构成八种「单位形组合」图例 每一个「单位形组合」又可以重复以线状﹝

  • perl常问题集合之一

    Perl是什么? Perl是一个高阶程式语言,由 Larry Wall和其他许多人所写,融合了许多语言的特性.它主要是由无所不在的 C语言,其次由 sed.awk,UNIX shell 和至少十数种其他的工具和语言所演化而来.Perl对 process.档案,和文字有很强的处理.变换能力,因此举凡有关快速原型设计.系统工具.软体工具.系统管理.资料库连结.图像程式设计.网路连结,和 WWW程式设计等之类的任务,都特别 适合用 Perl来做.这些特长不但使 Perl成为系统维护管理者和 CGI作者

  • 学习C++编程的必备软件

    1. 前言 这一课我们来做一些 C++ 开发前的准备工作. 2. 编程的必要工具 依你看,对编程来说,什么软件是必要的呢? 如果你认真学了上一课,那你至少可以说出一种吧. 对了,就是编译器.这个重要的程序可以把你的源代码(用高级语言如 C 语言写的指令)转换成电脑可以理解的二进制码(只包含 0 和 1 的,类似 01100110001111011101010... ). 上一课我们也提了一下,每种高级语言都有对应的编译器(当然对于 Python 这样的解释性语言,就不需要编译了),光是 C++

  • 打哈欠为什么会传染

    一个人打哈欠,周围的人纷纷跟着他一起打,打哈欠为什么会"传染"?美国德雷克塞尔大学的心理学家史蒂文·普拉捷克认为,所谓的打哈欠传染更容易在移情人群,即那些喜欢将自己假想成他人的那些人中发生. 为验证这一观点,普拉捷克和他在纽约州立大学的同事让志愿者观看了一段人们打哈欠的录像.结果有40%多的志愿者会随着屏幕上的人一起打哈欠,而在这些受"传染"的人中,有60%的人不止打一个哈欠.研究人员随即让这部分人接受移情能力测试,他们的分数都非常高. 普拉捷克说,这些人是那种在别

随机推荐