第10章 海量数据处理
计算机硬件的扩容确实可以极大地提高程序的处理速度，但考虑到其技术、成本等方面的因素，它并非只有一条途径。而随着互联网、机器学习、深度学习、大数据、人工智能、云计算、物联网以及移动通信技术的发展，每时每刻，数以亿计的用户产生着数量巨大的信息，海量数据时代已经来临。因此通过对海量数据的挖掘能有效地揭示用户的行为模式，加深对用户需求的理解，提取用户的集体智慧，从而为研发人员决策提供依据，提升产品用户体验，进而占领市场，所以当前各大互联网公司都将研究工作的重点放在了海量数据分析上。但是，只寄希望于硬件扩容是很难满足海量数据的分析需要的，如何利用现有条件进行海量信息处理，已经成为各大互联网公司亟待解决的问题。所以，海量信息处理正日益成为当前程序员笔试、面试中一个新的亮点。
不同于常规量级数据中提取信息，在海量信息中提取有用数据，存在以下几个方面的问题。首先，数据量过大，数据中什么情况都可能存在，如果信息数量只有20条，人工就可以逐条进行查找、比对。可是当数据规模扩展到数千条、数亿条甚至更多时，只通过人工已经无法解决存在的问题，必须通过工具或者程序进行处理。其次，对海量数据进行信息处理，还需要有良好的软硬件配置，合理使用工具，合理分配系统资源。通常情况下，如果需要处理的数据量非常大，超过了TB级，小型机及大型工作站是要考虑的，普通的计算机如果有好的处理方法也可以考虑，如通过联机做成工作集群。最后，对海量数据进行信息处理时，要求很好的处理方法和技巧，如何进行数据挖掘算法的设计以及如何进行数据的存储访问等都是研究的难点。
针对海量数据的处理，可以使用的方法非常多，常见的方法有Hash法、Bit-map（位图）法、Bloom filter 法、数据库优化法、倒排索引法、外排序法、Trie 树、堆、双层桶法以及MapReduce 法等。其中，Hash 法、Bit-map（位图）法、Trie 树以及堆等方法的考查频率最高、使用范围最为广泛，是读者需要重点掌握的方法。
10.1 如何从大量的url中找出相同的url
难度系数：★★★★☆
被考查系数：★★★★☆
题目描述：
给定a、b两个文件，各存放50亿个url，每个url各占64B，内存限制是4GB，找出a、b两个文件共同的url。
分析与解答：
因为每个url需要占64B，所以50亿个url占用的空间大小为50亿×64=5GB×64=320GB。由于内存大小只有4GB，因此不可能一次性把所有的url都加载到内存中处理。对于这个类型的题目，一般都需要使用分治法，即把一个文件中的url按照某一特征分成多个文件，使得每个文件的内容都小于4GB，这样就可以把这个文件一次性读到内存中进行处理了。对于本题而言，主要的实现思路为以下几点。
1）遍历文件a，对遍历到的url求hash（url）%500，根据计算结果把遍历到的url分别存储到a0，a1，a2，…，a499（将计算结果为i的url存储到文件ai中），这样每个文件的大小约为600MB。当某一个文件中url的大小超过2GB时，可以按照类似的思路把这个文件继续分为更小的子文件（例如，如果a1大小超过2GB，那么可以把文件继续分成a11, a12, …）。
2）使用同样的方法遍历文件b，把文件b中的url分别存储到文件b0，b1，…，b499中。
3）通过上面的划分，与ai中url相同的url一定在bi中。由于ai与bi中所有的url的大小不会超过4GB，因此可以把它们同时读入到内存中进行处理。具体思路：遍历文件ai，把遍历到的url存入到hash_set中，接着遍历文件bi中的url，如果这个url在hash_set中存在，那么说明这个url是这两个文件共同的url，可以把这个url保存到另外一个单独的文件中。当把文件a0～a499都遍历完成后，就找到了两个文件共同的url。
10.2 如何从大量数据中找出高频词
难度系数：★★★★☆
被考查系数：★★★★★
题目描述：
有一个1GB大小的文件，文件里面每一行是一个词，每个词的大小不超过16B，内存大小限制是1MB，要求返回频数最高的100个词。
分析与解答：
由于文件大小为1GB，而内存大小只有1MB，因此不可能一次把所有的词读入到内存中处理，需要采用分治的方法，把一个大的文件分解成多个小的子文件，从而保证每个文件的大小都小于1MB，进而可以直接被读取到内存中处理。具体的思路如下：
1）遍历文件。对遍历到的每一个词，执行如下hash操作：hash（x）%2000，将结果为i的词存放到文件ai中，通过这个分解步骤，可以使每个子文件的大小为400KB左右。如果这个操作后某个文件的大小超过1MB了，那么就可以采用相同的方法对这个文件继续分解，直到文件的大小小于1MB为止。
2）统计出每个文件中出现频率最高的100个词。最简单的方法为，使用hash_map来实现，具体实现方法：遍历文件中的所有词，对于遍历到的词，如果在hash_map中不存在，那么把这个词存入hash_map中（键为这个词，值为1），如果这个词在hash_map中已经存在了，那么把这个词对应的值加1。遍历完后可以非常容易地找出出现频率最高的100个词。
3）第2）步找出了每个文件出现频率最高的100个词，这一步可以通过维护一个小顶堆来找出所有词中出现频率最高的100个。具体方法：遍历第一个文件，把第一个文件中出现频率最高的100个词构建成一个小顶堆（如果第一个文件中词的个数小于100，可以继续遍历第二个文件，直到构建好有100个结点的小顶堆为止）。继续遍历，如果遍历到的词的出现次数大于堆顶上词的出现次数，可以用新遍历到的词替换堆顶的词，然后重新调整这个堆为小顶堆。当遍历完所有文件后，这个小顶堆中的词就是出现频率最高的100个词。当然这一步也可以采用类似归并排序的方法把所有文件中出现频率最高的100个词排序，最终找出出现频率最高的100个词。
引申：怎么在海量数据中找出重复次数最多的一个？
前面的算法是求解top100，而这道题目只是求解top1，可以使用同样的思路来求解。唯一不同的是，在求解出每个文件中出现次数最多的数据后，接下来从各个文件中出现次数最多的数据中找出出现次数最多的数，不需要使用小顶堆，只需要使用一个变量就可以完成。方法很简单，此处不再赘述。
10.3 如何找出某一天访问百度网站最多的IP
难度系数：★★★★☆
被考查系数：★★★★★
题目描述：
现有海量日志数据保存在一个超级大的文件中，该文件无法直接读入内存，要求从中提取某天访问百度次数最多的那个IP。
分析与解答：
由于这道题只关心某一天访问百度最多的IP，因此可以先对文件进行一次遍历，把这一天访问百度网站的IP的相关信息记录到一个单独的文件中。接下来可以用上一节介绍的方法来求解。由于求解思路是一样的，这里就不再详细介绍了。唯一需要确定的是，把一个大文件分为几个小文件比较合适。以IPv4为例，由于一个IP地址占用32bit，因此最多会有232种取值情况。如果使用hash（IP）%1024值，那么就把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4M个IP地址。如果使用2048个小文件，那么每个文件会最多包含2M个IP地址。因此，对于这类题目而言，首先需要确定可用内存的大小，然后确定数据的大小。由这两个参数就可以确定hash函数应该怎么设置才能保证每个文件的大小都不超过内存的大小，从而可以保证每个小文件都能被一次性加载到内存中。
10.4 如何在大量的数据中找出不重复的整数
难度系数：★★★★☆
被考查系数：★★★★★
题目描述：
在2.5亿个整数中找出不重复的整数。注意：内存不足以容纳这2.5亿个整数。
分析与解答：
由于这道题目与前面的题目类似，也是无法一次性把所有数据加载到内存中，因此也可以采用类似的方法求解。
方法一：分治法
采用hash函数的方法，把这2.5亿个整数划分到更小的文件中，从而保证每个文件的大小不超过可用的内存大小。然后对每个小文件而言，所有的数据都可以一次性被加载到内存中，因此可以使用hash_map或hash_set来找到每个小文件中不重复的整数。当处理完所有的文件后就可以找出这2.5亿个整数中所有的不重复的整数。
方法二：位图法
对于整数相关的算法的求解，位图法是一种非常实用的算法。对本题而言，如果可用的内存空间超过1GB就可以使用这种方法。具体思路：假设整数占用4B（如果占用8B，则求解思路类似，只不过需要占用更大的内存），也就是32bit，可以表示的整数的个数为232。由于本题只查找不重复的数，而不关心具体数字出现的次数，因此可以分别使用2个bit来表示各个数字的状态：用00表示这个数字没有出现过，01表示出现过1次，10表示出现了多次， 11暂不使用。
根据上面的逻辑，在遍历这2.5亿个整数时，如果这个整数对应的位图中的位为00，那么就修改成01；如果为01，则修改为10；如果为10，则保持原值不变。这样当所有数据遍历完成后，可以再遍历一遍位图，位图中值为01的bit对应的数字就是没有重复的数字。
10.5 如何在大量的数据中判断一个数是否存在
难度系数：★★★★☆
被考查系数：★★★★☆
题目描述：
在2.5亿个整数中判断一个数是否存在。注意：内存不足以容纳这2.5亿个整数。
分析与解答：
显然2.5亿数据量太大，不可能一次性把所有的数据都加载到内存中，那么最容易想到的方法就是分治法。
方法一：分治法
对于大数据相关的算法题，分治法是一个非常好的方法。针对这道题，主要的思路：可以根据实际可用内存的情况，确定一个hash函数，如hash（value）%1000，通过这个hash函数可以把这2.5亿个数字划分到1000个文件中（a1，a2，…，a1000），然后对待查找的数字使用相同的hash函数求出hash值，假设计算出的hash值为i，如果这个数存在，那么它一定在文件ai中。通过这种方法就可以把题目的问题转换为文件ai中是否存在这个数。那么在接下来的求解过程中可以选用的思路比较多，如下所示：
1）由于划分后的文件比较小，可以直接被装载到内存中，可以把文件中所有的数字都保存到hash_set中，然后判断待查找的数字是否存在。
2）如果这个文件中的数字占用的空间还是太大，那么就可以用相同的方法把这个文件继续划分为更小的文件，然后确定待查找的数字可能存在的文件，最后在相应的文件中继续查找。
方法二：位图法
对于这类判断数字是否存在、判断数字是否重复的问题，位图法是一种非常高效的方法。这里以32位整型为例，它可以表示数字的个数为232。可以申请一个位图，让每个整数对应位图中的一个bit，这样232个数需要位图的大小为512MB。具体实现的思路：申请一个512MB大小的位图，并把所有的位都初始化为0；接着遍历所有的整数，对遍历到的数字，把相应位置上的bit设置为1。最后判断待查找的数对应的位图上的值是多少，如果是0，则表示这个数字不存在，如果是1，则表示这个数字存在。
10.6 如何查询最热门的查询串
难度系数：★★★★☆
被考查系数：★★★★★
题目描述：
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度为1～255B。
假设目前有1000万个记录（这些查询串的重复度比较高，虽然总数是1000万，但如果除去重复后，则不超过300万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门）。请统计最热门的10个查询串，要求使用的内存不能超过1GB。
分析与解答：
从题目中可以发现，每个查询串最长为255B，1000万个字符串需要占用2.55GB内存，因此无法把所有字符串同时读入到内存中处理。对于这种类型的题目，分治法是一个非常实用的方法。
方法一：分治法
对字符串设置一个hash 函数，通过这个hash 函数把字符串划分到更多更小的文件中，从而保证每个小文件中的字符串都可以直接被加载到内存中处理，然后求出每个文件中出现次数最多的10个字符串；最后通过一个小顶堆统计出所有文件中出现最多的10个字符串。
从功能角度出发，这种方法是可行的，但是因为需要对文件遍历两遍，而且hash函数也需要被调用1000万次，所以性能不是很好。针对这道题的特殊性，下面介绍另外一种性能较好的方法。
方法二：hash_map法
虽然字符串的总数比较多，但是字符串的种类不超过300万个，因此可以考虑把所有字符串出现的次数保存在一个hash_map 中（键为字符串，值为字符串出现的次数）。hash_map所需要的空间为300万×（255+4）=3M×259=777MB（其中，数值4表示用4个字节记录字符串出现次数）。由此可见，1GB的内存空间是足够用的。基于以上的分析，本题的求解思路如下：
1）遍历字符串，如果字符串在hash_map中不存在，则直接存入hash_map中，键为这个字符串，值为1。如果字符串在hash_map中已经存在，则把对应的值直接加1。这一步操作的时间复杂度为O（N），其中N为字符串的数量。
2）在第一步的基础上找出出现频率最高的10个字符串。可以通过小顶堆的方法来完成，遍历hash_map的前10个元素，并根据字符串出现的次数构建一个小顶堆，然后接着遍历hash_map，只要遍历到的字符串的出现次数大于堆顶字符串的出现次数，就用遍历的字符串替换堆顶的字符串，然后把堆调整为小顶堆。
3）对所有剩余的字符串都遍历一遍，遍历完成后堆中的10个字符串就是出现次数最多的字符串。这一步的时间复杂度为O（Nlog10）。
方法三：trie树法
方法二中使用hash_map 来统计每个字符串出现的次数。当这些字符串有大量相同前缀时，可以考虑使用trie 树来统计字符串出现的次数。可以在树的结点中保存字符串出现的次数，0表示没有出现。具体的实现方法：在遍历字符串的时候，在trie树中查找对应的字符串，如果找到，则把结点中保存的字符串出现的次数加1，否则为这个字符串构建新的结点，构建完成后把叶子结点中字符串的出现次数设置为1。这样遍历完字符串后就可以知道每个字符串的出现次数，然后通过遍历这个树就可以找出出现次数最多的字符串。
trie树经常被用来统计字符串的出现次数。它的另外一个大的用途就是字符串查找，判断是否有重复的字符串等。
10.7 如何统计不同电话号码的个数
难度系数：★★★★☆
被考查系数：★★★★☆
题目描述：
已知某个文件内包含一些电话号码，每个号码为8位数字，统计不同号码的个数。
分析与解答：
这个题目本质上也是求解数据重复的问题，对于这类问题，首先会考虑位图法。对本题而言，8位电话号码可以表示的范围为00000000～99999999。如果用1bit表示一个号码，那么总共需要1亿个bit，总共需要大约100MB的内存。
通过上面的分析可知，这道题的主要思路：申请一个位图并初始化为0，然后遍历所有电话号码，把遍历到的电话号码对应的位图中的bit设置为1。当遍历完成后，如果bit值为1，则表示这个电话号码在文件中存在，否则这个bit 对应的电话号码在文件中不存在。所以bit值为1的数量就是不同电话号码的个数。
求解这道题时，最核心的算法是如何确定电话号码对应的是位图中的哪一位。下面重点介绍这个转化的方法，这里使用下面的对应方法。
00000000对应位图最后一位：0×0000…000001。
00000001对应位图倒数第二位：0×0000…0000010（1向左移1位）。
00000002对应位图倒数第三位：0×0000…0000100（1向左移2位）。
……
00000012对应位图的倒数第十三位：0×0000…0001 0000 0000 0000。
通常而言，位图都是通过一个整数数组来实现的（这里假设一个整数占用4B）。由此可以得出，通过电话号码获取位图中对应位置的方法为（假设电话号码为P）：
1）通过P/32就可以计算出该电话号码在bitmap数组中的下标（因为每个整数占用32bit，通过这个公式就可以确定这个电话号码需要移动多少个32位，也就是可以确定它对应的bit在数组中的位置）。
2）通过P%32就可以计算出这个电话号码在这个整型数字中具体的bit的位置，也就是1这个数字对应的左移次数。因此，只要把1向左移P%32位，然后把得到的值与这个数组中的值做或运算，就可以把这个电话号码在位图中对应的位设置为1。
这个转换的操作可以通过一个非常简单的函数来实现：
10.8 如何从5亿个数中找出中位数
难度系数：★★★★☆
被考查系数：★★★★☆
题目描述：
从5亿个数中找出中位数。数据排序后，位置在最中间的数就是中位数。当样本数为奇数时，中位数=（N+1）/2；当样本数为偶数时，中位数为N/2与1+N/2的均值。
分析与解答：
如果这道题目没有内存大小的限制，则可以把所有的数字排序后找出中位数，但是最好的排序算法的时间复杂度都是O（NlogN）（N为数字的个数）。这里介绍另外一种求解中位数的算法——双堆法。
方法一：双堆法
这个算法的主要思路是维护两个堆，一个大顶堆，一个小顶堆，且这两个堆需要满足如下两个特性。
特性一：大顶堆中最大的数小于或等于小顶堆中最小的数。
特性二：保证这两个堆中的元素个数的差不能超过1。
若数据总数为偶数时，当这两个堆建立好以后，中位数显然就是两个堆顶元素的平均值。当数据总数为奇数时，根据两个堆的大小，中位数一定在数据多的堆的堆顶。对本题而言，具体实现思路：维护两个堆maxHeap与minHeap，这两个堆的大小分别为max_size和min_size，然后开始遍历数字。对于遍历到的数字data：
1）如果data＜maxHeap的堆顶元素，此时为了满足特性1，只能把data插入到maxHeap中。为了满足特性二，需要分以下几种情况讨论。
① 如果max_size≤min_size，则说明大顶堆元素个数小于小顶堆元素个数，此时把data直接插入大顶堆中，并把这个堆调整为大顶堆。
② 如果max_size＞min_size，为了保持两个堆元素个数的差不超过1，则需要把maxHeap堆顶的元素移动到minHeap中，接着把data插入到maxHeap中。同时通过对堆的调整，分别让两个堆保持大顶堆与小顶堆的特性。
2）如果maxHeap堆顶元素≤data≤minHeap堆顶元素，则为了满足特性一，可以把data插入任意一个堆中，为了满足特性二，需要分以下几种情况讨论：
① 如果max_size＜min_size，显然需要把data插入到maxHeap中；
② 如果max_size＞min_size，显然需要把data插入到minHeap中；
③ 如果max_size==min_size，可以把data插入到任意一个堆中。
3）如果data＞maxHeap的堆顶元素，此时为了满足特性一，只能把data插入到minHeap中。为了满足特性二，需要分以下几种情况讨论：
① 如果max_size≥min_size，那么把data插入到minHeap中；
② 如果max_size＜min_size，那么需要把minHeap堆顶元素移到maxHeap中，然后把data插入到minHeap中。
通过上述方法可以把5亿个数构建成两个堆，两个堆顶元素的平均值就是中位数。
由于需要把所有的数据都加载到内存中，当数据量很大时，因为无法把数据一次性加载到内存中，因此这种方法比较适用于数据量小的情况。对本题而言，5亿个数字，每个数字在内存中占4B，5亿个数字需要的内存空间为2GB内存。当可用的内存不足2GB时，显然不能使用这种方法，下面介绍另外一种方法。
方法二：分治法
分治法的核心思想是把一个大的问题逐渐转换为规模较小的问题来求解。对于本题而言，顺序读取这5亿个数字；
1）对于读取到的数字num，如果它对应的二进制中最高位为1，则把这个数字写入到f1中，如果最高位是0，则写入到f0中。通过这一步就可以把这5亿个数字划分成两部分，而且f0中的数字都大于f1中的数字（因为最高位是符号位）。
2）通过上面的划分很容易知道中位数是在f0中还是在f1中。假设f1中有1亿个数，那么中位数一定在文件f0中，且它的值为f0文件中的数字排序的第1.5亿个数与它后面一个数的平均值。
3）对于f0，可以用次高位的二进制的值继续把这个文件一分为二，使用同样的思路可以确定中位数是哪个文件中的第几个数。直到划分后的文件可以被加载到内存时，把数据加载到内存中以后排序，从而找出中位数。
需要注意的是，这里有一种特殊情况需要考虑，当数据总数为偶数时，如果把文件一分为二后发现两个文件中的数据有相同的个数，那么中位数就是f0文件中的最大值与f1文件中的最小值的平均值。如果要求一个文件中所有数据的最大值或最小值，可以使用前面介绍的分治法进行求解。
10.9 如何按照query的频度排序
难度系数：★★★★☆
被考查系数：★★★★★
题目描述：
有10个文件，大小均为1GB，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求按照query的频度排序。
分析与解答：
对于这种题，如果query的重复度比较大，则可以考虑一次性把所有query读入到内存中处理；如果query的重复率不高，可用的内存不足以容纳所有的query，那么就需要使用分治法或者其他的方法来解决。
方法一：hash_map法
如果query的重复率比较高，则说明不同的query总数比较小，可以考虑把所有的query都加载到内存中的hash_map中（由于hash_map中针对每个不同的query只保存一个键值对，因此，这些query 占用的空间会远小于10GB，有希望把它们一次性都加载到内存中）。接着就可以对hash_map按照query出现的次数进行排序。
方法二：分治法
这种方法需要根据数据量的大小以及可用内存的大小来确定问题划分的规模。对本题而言，可以顺序遍历10个文件中的query，通过hash函数hash（query）%10把这些query划分到10个文件中。通过这样的划分，每个文件的大小为1GB左右，当然可以根据实际情况来调整hash函数。如果可用内存很小，则可以把这些query划分到更多更小的文件中。
如果划分后的文件还是比较大，则可以使用相同的方法继续划分，直到每个文件都可以被读取到内存中进行处理为止，然后对每个划分后的小文件使用hash_map统计每个query出现的次数，最后根据出现次数排序，并把排序好的query 以及出现次数写入到另外一个单独的文件中。这样针对每个文件，都可以得到一个按照query出现次数排序的文件。
接着对所有的文件按照query 的出现次数进行排序，这里可以使用归并排序（由于无法把所有的query都读入到内存中，因此这里需要使用外排序）。