教你如何迅速秒杀99%的海量数据处理面试题(4)-CDA数据分析师官网

热线电话：13121318867

教你如何迅速秒杀99%的海量数据处理面试题(4)

2015-01-24

密匙五、外排序

　　适用范围：大数据的排序，去重
　　基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
　　扩展：
　　问题实例：
　　1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。
　　这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。

关于多路归并算法及外排序的具体应用场景，请参见此文：第十章、如何给10^7个数据量的磁盘文件排序。

密匙六、分布式处理 Mapreduce

适用范围：数据量大，但是数据种类小可以放入内存
　　基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。
　　扩展：
　　问题实例：

The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents:
海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)

CDA数据分析师考试相关入口一览（建议收藏）：

▷ 想报名CDA认证考试，点击>>> “CDA报名”