阿里面试 - 海量数据

2/2/2021 面试Alibaba

# 阿里面试 - 海量数据

# 问题

  • 1、海量数据处理,两个大文件中的相同记录
  • 2、100亿个整数,找出中位数

# 思路

大数据问题的思想都是分治法,网上找了两篇答案

海量数据的核心思想是分治法,简单来说就是空间不够,方法来凑

# 解答

# 海量数据处理:两个大文件中的相同记录

问题分析:文件太大,无法全量读取到内存遍历。

解决办法:

  • 1、利用哈希的离散性(不同的数据哈希值大部分是不同的),所以我们可以获取到不同的哈希值来进行区分不同记录。
  • 2、在记录计算了哈希值以后,我们可以将其写到哈希值对应的文件中,这样可以保证相同哈希值的记录存在同一个文件中。
  • 3、两个文件都是用这种方法来计算,那么相同记录就一定会在同一个文件中了。也就分离出相同记录了

上面文章中还使用了哈希取模的方法(hash值%1000),这是为了减少文件生成数量,简单来说12345%1000 和 39345%1000,得到的结果都是 345。这样会出现不同的记录存储在同一个文件里,在得到文件后,还需要对小文件进行常规的数据处理,从小文件里分离出相同记录就简单了。

# 100亿个整数,找出中位数

问题分析:与问题1相同

解决办法

  • 1、自定义一个数组,数组的大小是想要划分的区间。比如划分100个区间,那么每个区间就代表1~1亿的数据区间,注意!区间用来存储数据出现的次数,而不是数据本身。
  • 2、遍历100亿数据,当数据出现过一次,就在对应的区间+1,最终得到了数据在100个区间里出现的次数。
  • 3、你的区间是有序的(arr[0] 存储的是1-1亿的数据、arr[1]存储的是1亿零1~2亿的数据……),通过我们的区间数组上存储的数据出现次数,我们可以得知中位数一定会落在某个区间上。
  • 4、如果这个区间数据依旧无法一次性读取到内存,继续1~3步骤。
  • 5、如果可以满足一次性读取到内存,并且计算速度也不是很慢,我们就可以做常规的遍历处理(比如二分查找),找到具体的中位数的数值。

当然,中间还有个细节需要处理,就是区间和数据的映射,这个就不细讲了~ 主要是分治思想,细节上的实现方式有很多种。

# 扩展

Q: 分治思想,是以有限的资源多线程处理,动态分片的。还是有限容器,类似于磁盘page扫描,打表存放数据?数据需要有序处理么?

A: 和多线程没有太大关系。主要是时间和空间的因素。 一种是时间太慢,一种是空间不够。上面两个都是内存空间不足,所以需要分支。 一般空间问题都是指内存,因为内存是比磁盘要贵的,所以,大数据量无法一次性读取到内存,就可以转换到磁盘上来处理。 但这个时间效率上,肯定是要降低的。

数据是否有序,取决于你想要得到的结果。 上面的找中位数问题,虽然也涉及到二分查找,但他本身数据是无序的,那么大量的数据排序是我们时间上无法接受的。 但因为我们的数组区间有序,所以就可以规避掉大数据量的排序问题。

Q: 提到分治,会想到边缘计算,利用闲置客户机分发分片后的计算内容,将计算结果返回代理服务器

A: 边缘计算也是一种实现方式。本质上是将大问题拆解成小问题。 至于是你自己分步来处理,还是你交给100个人来处理,都是分治的实现方式。

Q: 利用数组的有序性,是指,不同分片小范围排序获取结果返回新的数组,就这样不断递归回溯得出最终计算结果么? 分治思想,在数据库层面是不是就是集群分片?JAVA里面也有fork join的实现是不是也可以理解为分治

A: 这个是说上面100亿数据的问题,100亿数据是无序的,但是我们定义的数组是有序的 arr[0] 存储 1~1亿arr[1] 存储 1亿零1~2亿 ……这个数组是有序的。 我们通过映射的方式,将大量的数据映射到某个区间,只需要关注有序的区间就可以了,不需要同时关注100亿数据的有序性了。 用左神的一句话来说:二分查找不一定需要有序,只要数据能满足一定规则,淘汰掉一部分数据,就能用二分。 集群分片解决的是分布式相关的问题,fork join 可以理解为分治。 但是这样的理解只是交给多个人同时处理,多线程的方式,是用加人力的方式来做的分支。 一般算法面试题的话,更希望得到分步处理的方式。

Q: 概率统计问题么?

A: 是,区间方法就是用统计法来解决大数据的问题

Q: 统计学——中位数、众数 (opens new window) 这样的话,就既体现了分步,也提现了效率。面试可以拿高分?

A: 面试主要考验的是人的思路,两种说出来都是加分的~ 主要是开线程或者边缘计算的方式,实际上还是需要更多的资源的,线程用的是CPU,计算还需要内存和硬盘。我们做技术的,肯定更关注怎么在最低成本下解决问题

来源:いつも何度でも


收录时间:2021-02-02

最后更新时间: 10/11/2021, 3:33:08 PM