海量数据处理¶

这部分内容是海量数据处理的问题。所谓海量：

时间上：无法在较短时间内迅速解决。可以设计巧妙的算法搭配合适的数据结构解决空间上：数据量太大，无法一次全部装入内存；针对方法是大而化小，分而治之。将规模大划分为规模小的问题，各个击破

海量处理问题常用的分析解决问题的思路是：

Hash 映射/分而治之 + hash 统计/trie 树/红黑树/二叉搜索树 + 堆排序/快速排序/归并排序
Bitmap
Bloom filter
Trie 树
数据库索引
倒排索引 (Inverted Index)
双层桶划分
外排序
simhash 算法
分布处理之 Hadoop/Mapreduce

top-1 问题 —— 海量日志提取访问最多的 IP¶

海量日志处理，提取某日访问百度次数最多的那个 IP

估算¶

我们先来估算下，一个 IP 可以用 32bit 表示，总共可以表示 2^32 = 42 亿九千万个 IP 。假设一个 IP 一天内访问百度的次数不超过 40 亿次，可以用 unsigned 的数表示。用数组统计出每个 IP 地址出现的最大次数，就可以得到访问次数最大的 IP 地址

unsigned count[N],这个 N=2^32=4G 个 IP 地址 sizeof(count) = 4*N = 16G 内存，远超过 32 位机器所支持的 4G 内存大小。因此不能直接创建这个数组。

分治法/文件映射¶

假设运行使用的内存是 512MB, 512M/4 = 128M 个 IP 地址（一个 IP 地址 32 位，占 4 个字节），也就是内存中可以同时放 128M 个内存地址；另一个角度理解就是，512M内存可以统计128M个不同的IP地址的访问次数，哪怕切割的小文件中的 IP 总数大于 128M

4G/128M = 32，也就是把 IP 地址划分成 32 个不同的区间段，addr[1-xx],addr[xx-xx]..分别计算每个区间中访问次数最大的 IP，然后再比较 32 个区间段中的最大次数，就可以得到所有 IP 的做大值了。

一个区间段的 IP 地址个数任然可能撑破 128M 个，从而撑爆内存

具体实施：

把大文件映射到小文件，有 2 种方式：

取模映射。 IP%32 映射到 32 个小文件，把 model 相同的 IP 保存到同一个文件
位运算映射。把 IP 的前 5 为作为作为区间编号，即 IP>>27 结果就是 [0,31]，把相同区间的 IP 保存到同一个文件

上面的映射中，都不会出现同一个IP映射到不同小文件的情况

统计每个小文件中的最大值¶

现在文件不同的 IP 数量达到内存承受的范围了，可以统计小文件中的 IP 次数了，使用常规的 hash_map(IP,count) 来统计了。可以分块读取来减少磁盘 IO

排序堆排序/快速排序/归并排序¶

代码示例¶

类似问题¶

怎么在海量数据中找出重复次数最多的一个？
服务器内存 1G，有一个 2G 的文件，里面每行存着一个 QQ 号（5-10 位数），怎么最快找出出现过最多次的 QQ 号。（10 位数可以表示 (不到)10 亿个 QQ 号）

top-K 找出最大的 k 个数¶

类似的题目类型有：

100w 个数中找出最大的 100 个数。寻找热门查询，300 万个查询字符串中统计最热门的 10 个查询。有一个文件中保存了 2 亿个整数，每个整数都以 ' ' 分隔。求最大的 100 万个整数之和。有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。请用 5 分钟时间，找出重复出现最多的前 10 条。一个文件中包含了 1 亿个随机整数，如何快速的找到最大 (小) 的 100 万个数字?（时间复杂度：O（n lg k））有一个 1G 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M。返回频数最高的 100 个词。

分析： hashmap 统计 + 二叉堆

方案 1：在前面的题中，我们已经提到了，用一个含 100 个元素的最小堆完成。复杂度为 O(100w*lg100)。

方案 2：采用快速排序的思想，每次分割之后只考虑比轴大的一部分，知道比轴大的一部分在比 100 多的时候，采用传统排序算法排序，取前 100 个。复杂度为 O(100w*100)。

方案 3：采用局部淘汰法。选取前 100 个元素，并排序，记为序列 L。然后一次扫描剩余的元素 x，与排好序的 100 个元素中最小的元素比，如果比这个最小的要大，那么把这个最小的元素删除，并把 x 利用插入排序的思想，插入到序列 L 中。依次循环，知道扫描了所有的元素。复杂度为 O(100w*100)。

这里给个最简单 hash 函数，字符串到int类型的哈希

int hash_function(const char *p)    
{    
    int value = 0;    
    while (*p != '\0')    
    {    
        value = value * 31 + *p++;    
        if (value > HASHLEN)    
            value = value % HASHLEN;    
    }    
    return value;    
}

这个 hash 函数要确保不同的字符串 hash 出不同的一个整数。

类似的题目还有：

有一个 1G 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M。返回频数最高的 100 个词。¶

方案 1：顺序读文件中，对于每个词 x，取 clip_image014，然后按照该值存到 5000 个小文件（记为 clip_image016）中。这样每个文件大概是 200k 左右。如果其中的有的文件超过了 1M 大小，还可以按照类似的方法继续往下分，知道分解得到的小文件的大小都不超过 1M。对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用 trie 树/hash_map 等），并取出出现频率最大的 100 个词（可以用含 100 个结点的最小堆），并把 100 词及相应的频率存入文件，这样又得到了 5000 个文件。下一步就是把这 5000 个文件进行归并（类似与归并排序）的过程了。

一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词，请给出思想，给出时间复杂度分析。¶

方案 1：这题是考虑时间效率。用 trie 树统计每个词出现的次数，时间复杂度是 O(nle)（le 表示单词的平准长度）。然后是找出出现最频繁的前 10 个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是 O(nlg10)。所以总的时间复杂度，是 O(nle) 与 O(nlg10) 中较大的哪一个。

一个文本文件，找出前 10 个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解。¶

方案 1：首先根据用 hash 并求模，将文件分解为多个小文件，对于单个文件利用上题的方法求出每个文件件中 10 个最常出现的词。然后再进行归并处理，找出最终的 10 个最常出现的词。

寻找热门查询：¶

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为 1-255 字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是 1 千万，但是如果去除重复和，不超过 3 百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的 10 个查询串，要求使用的内存不能超过 1G。

(1) 请描述你解决这个问题的思路；

(2) 请给出主要的处理流程，算法，以及算法的复杂度。

方案 1：采用 trie 树，关键字域存该查询串出现的次数，没有出现为 0。最后用 10 个元素的最小推来对出现频率进行排序。

分布式中的 top-K¶

海量数据分布在 100 台电脑中，想个办法高效统计出这批数据的 TOP10。

方案 1：

s 在每台电脑上求出 TOP10，可以采用包含 10 个元素的堆完成（TOP10 小，用最大堆，TOP10 大，用最小堆）。比如求 TOP10 大，我们首先取前 10 个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是 TOP10 大。

s 求出每台电脑上的 TOP10 后，然后把这 100 台电脑上的 TOP10 组合起来，共 1000 个数据，再利用上面类似的方法求出 TOP10 就可以了。

统计指定时间段内 ip 访问量¶

假设某个网站每天有超过 10 亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的 ip 地址和对应的时间，如果现在已经记录了 1000 亿条数据，想统计一个指定时间段内的区域 ip 地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢，设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？

参考答案：用 B+ 树来组织，非叶子节点存储（某个时间点，页面访问量），叶子节点是访问的 IP 地址。这个方案的优点是查询某个时间段内的 IP 访问量很快，但是要统计某个 IP 的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。或者可以建立二级索引，分别是时间和地点来建立索引。

文件中的内容排序并去重复¶

如果文件太大，就分片 2）这里的问题是去除重复，分片后，小文件合并又是个麻烦事。 3）直接 hash 统计，假设不重复的 url 最多 300 万,采用 hash 存储需要的空间 300 万 *4

linux 中的几个命令：

sort 将文件内容排序
uniq 检查和删除文件内容中重复出现的行列
comm 比较2个已经排序的文件

对于较大文件 G 级别的文件 split -b 把大文件分割成小文件然后用 sort 分别排序 sort -m 合并结果然后在 uniq 命令去重

类似的题目有：大量的 URL 字符串，如何从中去除重复的，优化时间空间复杂度对 2 亿条手机号码删除重复记录

在 O(n lg k) 时间内，将 k 个排序表合并成一个排序表，n 为所有有序表中元素个数¶

【解析】取前 100 万个整数，构造成了一棵数组方式存储的具有小顶堆，然后接着依次取下一个整数，如果它大于最小元素亦即堆顶元素，则将其赋予堆顶元素，然后用 Heapify 调整整个堆，如此下去，则最后留在堆中的 100 万个整数即为所求 100 万个数字。该方法可大大节约内存。

搜索中的智能提示（如 " 中国 " ,"zhongguo",考虑拼音）¶

把 2 万个汉字排序，弄成一个超长的字符串

用 Int16 索引汉字的所有拼音

Int64 建立汉字和拼音的关联 -- 汉字有多音字，需要把多个拼音 pack 到一个 Int64，位操作搞定

二分 + 位移 unpack，直接做到汉字到拼音的检索

找出文件中相反的串对¶

一个文件，内含一千万行字符串，每个字符串在 1K 以内，要求找出所有相反的串对，如 abc 和 cba。

分析：文件大小上限是：1000 万 *1K ~ 10GB。不可能内存操作

设计 hash 函数使得相反串得到相同的 hash 值？

求出这个文件里的整数里不包含的一个整数¶

一个文件中有 40 亿个整数，每个整数为四个字节，内存为 1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数

40 亿 *4 = 15GB, 4 个字节表示的整数，总共有 2^32 个可能使用 位图法 来统计： 1）分配 2^29 X 2^3 = 512MB 的内存空间，每一个 bit 代表一个整数，全部初始化为 0； buffer[512x1024x1024]

读入一个数，把对应的 bit 位置为 1. 如读入的是 312 , 将对应的 bit 置为 1：312/8=39 312%8=0 ，写入位置是第 40 个字节，0 号 bit
处理完 40 亿数据后，遍历 500M 内存，找到一个 bit 为 0 的位 for(unsigned int i=0;i<0xffffffff,i++){ if(!buffer){//为 0 则不包括这个整数

} }

位图法 适用于大规模数据，通常用来判断某个数据存不存在

写入指定位: bytepos = i/8 = i>>3 bitpos = i%8 = i & 0x1F

置为 1：arr[bytepos] |= (1 << bitpos) 置为 0：arr[bytepos] &= !(1<< bitpos)

void setbit(int *bitmap,int i){ bitmap[i>>3] |= (1 << (i&0x1F) ); }

读指定位: getbit(int *bitmap,int i){ return bitmap[i>>3] & ( 1 << (i&0x1F) ); }

对文件里的整数排序¶

假设一个文件中有 9 亿条不重复的 9 位整数，现在要求对这个文件进行排序。

9 位整数做多可表示 10 亿条不重复整数 (无符号数) 9 亿 *4=3.4GB 内存，一次读入内存是不可能了。

思路一：位图法排序 1）计算需要内存： 9 亿/8/1024/1024 < 120MB ,全部初始化为 0 2）读取文件中的数据，将数据对应的 bit 位置 1 分段读取 3）遍历整个 bit，将 bit 为 1 的依次存入文件

思路二：?

{url,size} 查询子串并按 size 排序¶

给出一个文件，里面包含两个字段 {url、size}，即 url 为网址，size 为对应网址访问的次数；

要求：

问题 1、利用 Linux Shell 命令或自己设计算法，查询出 url 字符串中包含“baidu”子字符串对应的 size 字段值；

问题 2、根据问题 1 的查询结果，对其按照 size 由大到小的排列。（说明：url 数据量很大，100 亿级以上）

找出文件中的中位数¶

在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。

找出重复登陆的 QQ 号¶

腾讯服务器每秒有 2w 个 QQ 号同时上线，找出 5min 内重新登入的 qq 号并打印出来。

海量节点树中寻找共同祖先¶

有一个一亿节点的树，现在已知两个点，找这两个点的共同的祖先。

设计流量统计系统¶

某服务器流量统计器，每天有 1000 亿的访问记录数据，包括时间、url、ip。设计系统实现记录数据的保存、管理、查询。要求能实现一下功能：

（1）计算在某一时间段（精确到分）时间内的，某 url 的所有访问量。（2）计算在某一时间段（精确到分）时间内的，某 ip 的所有访问量。

a,b 文件中共同的记录¶

给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url？

方案 1：可以估计每个文件安的大小为 50G×64=320G，远远大于内存限制的 4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

s 遍历文件 a，对每个 url 求取 clip_image002，然后根据所取得的值将 url 分别存储到 1000 个小文件（记为 clip_image004）中。这样每个小文件的大约为 300M。

s 遍历文件 b，采取和 a 相同的方式将 url 分别存储到 1000 各小文件（记为 clip_image006）。这样处理后，所有可能相同的 url 都在对应的小文件（clip_image008）中，不对应的小文件不可能有相同的 url。然后我们只要求出 1000 对小文件中相同的 url 即可。

s 求每对小文件中相同的 url 时，可以把其中一个小文件的 url 存储到 hash_set 中。然后遍历另一个小文件的每个 url，看其是否在刚才构建的 hash_set 中，如果是，那么就是共同的 url，存到文件里面就可以了。

方案 2：如果允许有一定的错误率，可以使用 Bloom filter，4G 内存大概可以表示 340 亿 bit。将其中一个文件中的 url 使用 Bloom filter 映射为这 340 亿 bit，然后挨个读取另外一个文件的 url，检查是否与 Bloom filter，如果是，那么该 url 应该是共同的 url（注意会有一定的错误率）。

有 10 个文件，每个文件 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求你按照 query 的频度排序。

方案 1：

s 顺序读取 10 个文件，按照 hash(query)%10 的结果将 query 写入到另外 10 个文件（记为 clip_image010）中。这样新生成的文件每个的大小大约也 1G（假设 hash 函数是随机的）。

s 找一台内存在 2G 左右的机器，依次对 clip_image010[1] 用 hash_map(query, query_count) 来统计每个 query 出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的 query 和对应的 query_cout 输出到文件中。这样得到了 10 个排好序的文件（记为 clip_image012）。

s 对 clip_image012[1] 这 10 个文件进行归并排序（内排序与外排序相结合）。

方案 2：

一般 query 的总量是有限的，只是重复的次数比较多而已，可能对于所有的 query，一次性就可以加入到内存了。这样，我们就可以采用 trie 树/hash_map 等直接来统计每个 query 出现的次数，然后按出现次数做快速/堆/归并排序就可以了。

方案 3：

与方案 1 类似，但在做完 hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如 MapReduce），最后再进行合并。

找出不重复的整数 (QQ 号)¶

在 2.5 亿个整数中找出不重复的整数，内存不足以容纳这 2.5 亿个整数。

方案 1：采用 2-Bitmap（每个数分配 2bit，00 表示不存在，01 表示出现一次，10 表示多次，11 无意义）进行，共需内存 clip_image020 内存，还可以接受。然后扫描这 2.5 亿个整数，查看 Bitmap 中相对应位，如果是 00 变 01，01 变 10，10 保持不变。所描完事后，查看 bitmap，把对应位是 01 的整数输出即可。

方案 2：也可采用上题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

字符串去重¶

1000 万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？

方案 1：这题用 trie 树比较合适，hash_map 也应该能行。

如何随机选取 1000 个关键字¶

给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取 1000 个关键字？

类似的题目还有：

有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入流中随机取得 m 个记录

最大间隙问题¶

给定 n 个实数 clip_image042，求着 n 个实数在实轴上向量 2 个数之间的最大差值，要求线性的时间算法。

方案 1：最先想到的方法就是先对这 n 个数据进行排序，然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法：

s 找到 n 个数据中最大和最小数据 max 和 min。

s 用 n-2 个点等分区间 [min, max]，即将 [min, max] 等分为 n-1 个区间（前闭后开区间），将这些区间看作桶，编号为 clip_image044，且桶 clip_image046 的上界和桶 i+1 的下届相同，即每个桶的大小相同。每个桶的大小为：clip_image048。实际上，这些桶的边界构成了一个等差数列（首项为 min，公差为 clip_image050），且认为将 min 放入第一个桶，将 max 放入第 n-1 个桶。

s 将 n 个数放入 n-1 个桶中：将每个元素 clip_image052 分配到某个桶（编号为 index），其中 clip_image054，并求出分到每个桶的最大最小数据。

s 最大间隙：除最大最小数据 max 和 min 以外的 n-2 个数据放入 n-1 个桶中，由抽屉原理可知至少有一个桶是空的，又因为每个桶的大小相同，所以最大间隙不会在同一桶中出现，一定是某个桶的上界和气候某个桶的下界之间隙，且该量筒之间的桶（即便好在该连个便好之间的桶）一定是空桶。也就是说，最大间隙在桶 i 的上界和桶 j 的下界之间产生 clip_image056。一遍扫描即可完成。

将多个集合合并成没有交集的集合：给定一个字符串的集合，格式如：clip_image058。要求将其中交集不为空的集合合并，要求合并完成的集合之间无交集，例如上例应输出 clip_image060。¶

(1) 请描述你解决这个问题的思路；

(2) 给出主要的处理流程，算法，以及算法的复杂度；

(3) 请描述可能的改进。

方案 1：采用并查集。首先所有的字符串都在单独的并查集中。然后依扫描每个集合，顺序合并将两个相邻元素合并。例如，对于 clip_image062，首先查看 aaa 和 bbb 是否在同一个并查集中，如果不在，那么把它们所在的并查集合并，然后再看 bbb 和 ccc 是否在同一个并查集中，如果不在，那么也把它们所在的并查集合并。接下来再扫描其他的集合，当所有的集合都扫描完了，并查集代表的集合便是所求。复杂度应该是 O(NlgN) 的。改进的话，首先可以记录每个节点的根结点，改进查询。合并的时候，可以把大的和小的进行合，这样也减少复杂度。

最大子序列与最大子矩阵问题¶

数组的最大子序列问题：给定一个数组，其中元素有正，也有负，找出其中一个连续子序列，使和最大。

方案 1：这个问题可以动态规划的思想解决。设 clip_image064 表示以第 i 个元素 clip_image066 结尾的最大子序列，那么显然 clip_image068。基于这一点可以很快用代码实现。

最大子矩阵问题：给定一个矩阵（二维数组），其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。

方案 1：可以采用与最大子序列类似的思想来解决。如果我们确定了选择第 i 列和第 j 列之间的元素，那么在这个范围内，其实就是一个最大子序列问题。如何确定第 i 列和第 j 列可以词用暴搜的方法进行。代码详见我的博客。

一共有 N 个机器，每个机器上有 N 个数。每个机器最多存 O(N) 个数并对它们操作。如何找到 clip_image022 个数中的中数？¶

方案 1：先大体估计一下这些数的范围，比如这里假设这些数都是 32 位无符号整数（共有 clip_image018[1] 个）。我们把 0 到 clip_image024 的整数划分为 N 个范围段，每个段包含 clip_image026 个整数。比如，第一个段位 0 到 clip_image028，第二段为 clip_image026[1] 到 clip_image030，…，第 N 个段为 clip_image032 到 clip_image024[1]。然后，扫描每个机器上的 N 个数，把属于第一个区段的数放到第一个机器上，属于第二个区段的数放到第二个机器上，…，属于第 N 个区段的数放到第 N 个机器上。注意这个过程每个机器上存储的数应该是 O(N) 的。下面我们依次统计每个机器上数的个数，一次累加，直到找到第 k 个机器，在该机器上累加的数大于或等于 clip_image034，而在第 k-1 个机器上的累加数小于 clip_image034[1]，并把这个数记为 x。那么我们要找的中位数在第 k 个机器中，排在第 clip_image036 位。然后我们对第 k 个机器的数排序，并找出第 clip_image036[1] 个数，即为所求的中位数。复杂度是 clip_image038 的。

方案 2：先对每台机器上的数进行排序。排好序后，我们采用归并排序的思想，将这 N 个机器上的数归并起来得到最终的排序。找到第 clip_image034[2] 个便是所求。复杂度是 clip_image040 的。

海量数据处理¶

top-1 问题 —— 海量日志提取访问最多的 IP¶

估算¶

分治法/文件映射¶

统计每个小文件中的最大值¶

排序 堆排序/快速排序/归并排序¶

代码示例¶

类似问题¶

top-K 找出最大的 k 个数¶

有一个 1G 大小的一个文件，里面每一行是一个词，词的大小不超过 16 字节，内存限制大小是 1M。返回频数最高的 100 个词。¶

一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前 10 个词，请给出思想，给出时间复杂度分析。¶

一个文本文件，找出前 10 个经常出现的词，但这次文件比较长，说是上亿行或十亿行，总之无法一次读入内存，问最优解。¶

寻找热门查询：¶

分布式中的 top-K¶

统计指定时间段内 ip 访问量¶

文件中的内容排序并去重复¶

在 O(n lg k) 时间内，将 k 个排序表合并成一个排序表，n 为所有有序表中元素个数¶

搜索中的智能提示（如 " 中国 " ,"zhongguo",考虑拼音）¶

找出文件中相反的串对¶

求出这个文件里的整数里不包含的一个整数¶

对文件里的整数排序¶

{url,size} 查询子串并按 size 排序¶

找出文件中的中位数¶

找出重复登陆的 QQ 号¶

海量节点树中寻找共同祖先¶

设计流量统计系统¶

a,b 文件中共同的记录¶

找出不重复的整数 (QQ 号)¶

字符串去重¶

如何随机选取 1000 个关键字¶

最大间隙问题¶

将多个集合合并成没有交集的集合：给定一个字符串的集合，格式如：clip_image058。要求将其中交集不为空的集合合并，要求合并完成的集合之间无交集，例如上例应输出 clip_image060。¶

最大子序列与最大子矩阵问题¶

一共有 N 个机器，每个机器上有 N 个数。每个机器最多存 O(N) 个数并对它们操作。如何找到 clip_image022 个数中的中数？¶

排序堆排序/快速排序/归并排序¶