第六章 海量数据处理
6.0 本章导读
所谓海量数据处理,是指基于海量数据的存储、处理、和操作。正因为数据量太大,所以导致
要么无法在较短时间内迅速解决,要么无法一次性装入内存。
事实上,针对时间问题,可以采用巧妙的算法搭配合适的数据结构(如布隆过滤器、哈希、位
图、堆、数据库、倒排索引、Trie 树)来解决;而对于空间问题,可以采取分而治之(哈希映
射)的方法,也就是说,把规模大的数据转化为规模小的,从而各个击破。
此外,针对常说的单机及集群问题,通俗来讲,单机就是指处理装载数据的机器有限(只要考
虑 CPU、内存、和硬盘之间的数据交互),而集群的意思是指机器有多台,适合分布式处理或
并行计算,更多考虑节点与节点之间的数据交互。
一般说来,处理海量数据问题,有以下十种典型方法:
1.哈希分治;
2.simhash 算法;
3.外排序;
4.MapReduce;
5.多层划分;
6.位图;
7.布隆过滤器;
8.Trie 树;
9.数据库;
10.倒排索引。
受理论之限,本章将摒弃绝大部分的细节,只谈方法和模式论,注重用最通俗、最直白的语言
阐述相关问题。最后,有一点必须强调的是,全章行文是基于面试题的分析基础之上的,具体
实践过程中,还得视具体情况具体分析,且各个场景下需要考虑的细节也远比本章所描述的任
何一种解决方案复杂得多。
6.1 关联式容器
一般来说,STL 容器分为:
序列式容器(vector/list/deque/stack/queue/heap),和关联式容器。
o 其中,关联式容器又分为 set(集合)和 map(映射表)两大类,以及这两大类的衍
生体 multiset(多键集合)和 multimap(多键映射表),这些容器均以 RB-
tree(red-black tree, 红黑树)完成。
o 此外,还有第 3 类关联式容器,如 hashtable(散列表),以及以 hashtable 为底
层机制完成的 hash_set(散列集合)/hash_map(散列映射表)/hash_multiset(散列
多键集合)/hash_multimap(散列多键映射表)。也就是说,set/map/multiset/
multimap 都内含一个 RB-tree,而 hash_set/hash_map/hash_multiset/
hash_multimap 都内含一个 hashtable。
所谓关联式容器,类似关联式数据库,每笔数据或每个元素都有一个键值(key)和一个实值
(value),即所谓的 Key-Value(键-值对)。当元素被插入到关联式容器中时,容器内部结构(RB-
tree/hashtable)便依照其键值大小,以某种特定规则将这个元素放置于适当位置。
包括在非关联式数据库中,比如,在 MongoDB 内,文档(document)是最基本的数据组织形式,
每个文档也是以 Key-Value(键-值对)的方式组织起来。一个文档可以有多个 Key-Value 组合,
每个 Value 可以是不同的类型,比如 String、Integer、List 等等。
{ "name" : "July",
"sex" : "male",
"age" : 23 }
set/map/multiset/multimap
set,同 map 一样,所有元素都会根据元素的键值自动被排序,因为 set/map 两者的所有各种
操作,都只是转而调用 RB-tree 的操作行为,不过,值得注意的是,两者都不允许两个元素有
相同的键值。
不同的是:set 的元素不像 map 那样可以同时拥有实值(value)和键值(key),set 元素的键值就
是实值,实值就是键值,而 map 的所有元素都是 pair,同时拥有实值(value)和键值(key),pair
的第一个元素被视为键值,第二个元素被视为实值。
至于 multiset/multimap,他们的特性及用法和 set/map 完全相同,唯一的差别就在于它们允许
键值重复,即所有的插入操作基于 RB-tree 的 insert_equal()而非 insert_unique()。
hash_set/hash_map/hash_multiset/hash_multimap
hash_set/hash_map,两者的一切操作都是基于 hashtable 之上。不同的是,hash_set 同 set
一样,同时拥有实值和键值,且实质就是键值,键值就是实值,而 hash_map 同 map 一样,每
一个元素同时拥有一个实值(value)和一个键值(key),所以其使用方式,和上面的 map 基本相
同。但由于 hash_set/hash_map 都是基于 hashtable 之上,所以不具备自动排序功能。为什么?
因为 hashtable 没有自动排序功能。
至于 hash_multiset/hash_multimap 的特性与上面的 multiset/multimap 完全相同,唯一的差别
就是它们 hash_multiset/hash_multimap 的底层实现机制是 hashtable(而 multiset/multimap,
上面说了,底层实现机制是 RB-tree),所以它们的元素都不会被自动排序,不过也都允许键
值重复。
所以,综上,说白了,什么样的结构决定其什么样的性质,因为 set/map/multiset/multimap 都
是基于 RB-tree 之上,所以有自动排序功能,而 hash_set/hash_map/hash_multiset/
hash_multimap 都是基于 hashtable 之上,所以不含有自动排序功能,至于加个前缀 multi_无
非就是允许键值重复而已。
6.2 分而治之
方法介绍
对于海量数据而言,由于无法一次性装进内存处理,导致我们不得不把海量的数据通过 hash
映射分割成相应的小块数据,然后再针对各个小块数据通过 hash_map 进行统计或其它操作。
那什么是 hash 映射呢?简单来说,就是为了便于计算机在有限的内存中处理 big 数据,我们通
过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取余的方式映射成小数
存放在内存中,或大文件映射成多个小文件),而这个映射散列方式便是我们通常所说的 hash
函数,设计的好的 hash 函数能让数据均匀分布而减少冲突。
问题实例
1、海量日志数据,提取出某日访问百度次数最多的那个 IP
分析:百度作为国内第一大搜索引擎,每天访问它的 IP 数量巨大,如果想一次性把所有 IP 数
据装进内存处理,则内存容量明显不够,故针对数据太大,内存受限的情况,可以把大文件转
化成(取模映射)小文件,从而大而化小,逐个处理。
换言之,先映射,而后统计,最后排序。
解法:具体分为以下 3 个步骤
1.分而治之/hash 映射
o 首先把这一天访问百度日志的所有 IP 提取出来,然后逐个写入到一个大文件
中,接着采用映射的方法,比如%1000,把整个大文件映射为 1000 个小文件。
2.hash_map 统计
o 当大文件转化成了小文件,那么我们便可以采用 hash_map(ip, value)来分别对
1000 个小文件中的 IP 进行频率统计,再找出每个小文件中出现频率最大的
IP。
3.堆/快速排序
o 统计出 1000 个频率最大的 IP 后,依据各自频率的大小进行排序(可采取堆排
序),找出那个频率最大的 IP,即为所求。
注:Hash 取模是一种等价映射,不会存在同一个元素分散到不同小文件中去的情况,即这里
采用的是%1000 算法,那么同一个 IP 在 hash 后,只可能落在同一个文件中,不可能被分散的。
2、寻找热门查询,300 万个查询字符串中统计最热门的 10 个查询
原题:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的
长度为 1-255 字节。假设目前有一千万个记录,请你统计最热门的 10 个查询串,要求使用的内
存不能超过 1G。
分析:这些查询串的重复度比较高,虽然总数是 1 千万,但如果除去重复后,不超过 3 百万个。
一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。
由上面第 1 题,我们知道,数据大则划为小的,例如一亿个 ip 求 Top 10,可先%1000 将 ip 分
到 1000 个小文件中去,并保证一种 ip 只出现在一个文件中,再对每个小文件中的 ip 进行
hash_map 统计并按数量排序,最后归并或者最小堆依次处理每个小文件的 top10 以得到最后
的结果。
但对于本题,数据规模比较小,能一次性装入内存。因为根据题目描述,虽然有一千万个
Query,但是由于重复度比较高,故去除重复后,事实上只有 300 万的 Query,每个
Query255Byte,因此我们可以考虑把他们都放进内存中去(300 万个字符串假设没有重复,都
是最大长度,那么最多占用内存 3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行
处理)。
所以我们放弃分而治之/hash 映射的步骤,直接上 hash_map 统计,然后排序。So,针对此类
典型的 TOP K 问题,采取的对策往往是:hash_map + 堆。
解法:
1.hash_map 统计
o 先对这批海量数据预处理。具体方法是:维护一个 Key 为 Query 字串,Value
为该 Query 出现次数的 hash_map,即 hash_map(Query, Value),每次读取一
个 Query,如果该字串不在 Table 中,那么加入该字串,并将 Value 值设为
1;如果该字串在 Table 中,那么将该字串的计数加 1 即可。最终我们在 O(N)
的时间复杂度内用 hash_map 完成了统计;
2.堆排序
o 借助堆这个数据结构,找出 Top K,时间复杂度为 N‘logK。即借助堆结构,我
们可以在 log 量级的时间内查找和调整/移动。因此,维护一个 K(该题目中是
10)大小的小根堆,然后遍历 300 万的 Query,分别和根元素进行对比。所以,
我们最终的时间复杂度是:O(n) + N' * O(logk),其中,N 为 1000 万,N’为
300 万。
关于第 2 步堆排序,可以维护 k 个元素的最小堆,即用容量为 k 的最小堆存储最先遍历到的 k
个数,并假设它们即是最大的 k 个数,建堆费时 O(k),并调整堆(费时 O(logk))后,有
k1>k2>...kmin(kmin 设为小顶堆中最小元素)。继续遍历数列,每次遍历一个元素 x,与堆顶
元素比较,若 x>kmin,则更新堆(x 入堆,用时 logk),否则不更新堆。这样下来,总费时
O(klogk+
(
n-k
)
logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均
为 logk。
当然,你也可以采用 trie 树,关键字域存该查询串出现的次数,没有出现为 0。最后用 10 个元
素的最小推来对出现频率进行排序。
3、有一个 1G 大小的一个文件,里面每一行是一个词,词的大小不超过 16 字节,内存限制大
小是 1M。返回频数最高的 100 个词
解法:
1.分而治之/hash 映射
o 顺序读取文件,对于每个词 x,取 hash(x)%5000,然后把该值存到 5000 个小
文件(记为 x0,x1,...x4999)中。这样每个文件大概是 200k 左右。当然,如果
其中有的小文件超过了 1M 大小,还可以按照类似的方法继续往下分,直到分
解得到的小文件的大小都不超过 1M。
2.hash_map 统计
o 对每个小文件,采用 trie 树/hash_map 等统计每个文件中出现的词以及相应的
频率。
3.堆/归并排序
o 取出出现频率最大的 100 个词(可以用含 100 个结点的最小堆)后,再把 100
个词及相应的频率存入文件,这样又得到了 5000 个文件。最后就是把这 5000
个文件进行归并(类似于归并排序)的过程了。
4、海量数据分布在 100 台电脑中,想个办法高效统计出这批数据的 TOP10
解法一:
- 1
- 2
前往页