logo头像

Aoho's Blog

由散列表到BitMap的概念与应用(三):面试中的海量数据处理

面试题

在面试软件开发工程师时,经常会遇到海量数据排序和去重的面试题,特别是大数据岗位。

例1:给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,找出a、b文件共同的url?

  • 首先我们最常想到的方法是读取文件a,建立哈希表,然后再读取文件b,遍历文件b中每个url,对于每个遍历,我们都执行查找hash表的操作,若hash表中搜索到了,则说明两文件共有,存入一个集合。
  • 但上述方法有一个明显问题,加载一个文件的数据需要50亿*64bytes = 320G远远大于4G内存,何况我们还需要分配哈希表数据结构所使用的空间,所以不可能一次性把文件中所有数据构建一个整体的hash表。

如何解答

针对上述问题,我们分治算法的思想。

step1

遍历文件a,对每个url求取hash(url)%1000,然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,…,a999,每个小文件约300M),为什么是1000?主要根据内存大小和要分治的文件大小来计算,我们就大致可以把320G大小分为1000份,每份大约300M。

step2

遍历文件b,采取和a相同的方式将url分别存储到1000个小文件(记为b0,b1,…,b999)。

文件a的hash映射和文件b的hash映射函数要保持一致,这样的话相同的url就会保存在对应的小文件中。比如,如果a中有一个url记录data1被hash到了a99文件中,那么如果b中也有相同url,则一定被hash到了b99中。

所以现在问题转换成了:找出1000对小文件中每一对相同的url(不对应的小文件不可能有相同的url)

step3

因为每个小文件大约300M,所以我们再可以采用上面解答中的想法。

解题思路

常见的高效解答思路有:堆排序法、分治策略和BitMap(位图法)。

堆排序法

堆排序是4种平均时间复杂度为nlogn的排序方法之一,其优点在于当求M个数中的前n个最大数,和最小数的时候性能极好。所以当从海量数据中要找出前m个最大值或最小值,而对其他值没有要求时,使用堆排序法效果很好。

从1亿个整数里找出100个最大的数

  • 读取前100个数字,建立最大值堆。
  • 依次读取余下的数,与最大值堆作比较,维持最大值堆。可以每次读取的数量为一个磁盘页面,将每个页面的数据依次进堆比较,这样节省IO时间。
  • 将堆进行排序,即可得到100个有序最大值。

这里采用堆排序将空间复杂度讲得很低,要排序1亿个数,但一次性只需读取100个数字,或者设置其他基数,不需要一次性读完所有数据,降低对内存要求。

分治策略

总体思想:分而治之。通过分治将大数据变成小数据进行处理,再合并。

首先区分内部排序和外部排序:

  • 内部排序:内部排序是指待排序序列可以全部装入内存的排序过程,适用于规模较小的元素序列。
  • 外部排序:外部排序是指大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,才能达到排序整个文件的目的。

步骤:

  • 从大数据中抽取样本,将需要排序的数据切分为多个样本数大致相等的区间
  • 将大数据文件切分为多个小数据文件,这里要考虑IO次数和硬件资源问题,例如可将小数据文件数设定为1G(要预留内存给执行时的程序使用)
  • 使用最优的算法对小数据文件的数据进行排序,将排序结果按照步骤1划分的区间进行存储
  • 对各个数据区间内的排序结果文件进行处理,最终每个区间得到一个排序结果的文件
  • 将各个区间的排序结果合并

其次要注意待排序数据的特点。如果待排序数据具有某些特点,往往能够有更加有效的方法解决。
同时,这种思想也更加贴近大数据应用的思维方式。

BitMap(位图法)

32位机器上,一个整形,比如int a; 在内存中占32bit位,可以用对应的32bit位对应十进制的0-31个数,BitMap算法利用这种思想处理大量数据的排序与查询.

其优点是运算效率高,不许进行比较和移位,且占用内存少,比如N=10000000;只需占用内存为N/8=1250000Byte=1.25M。

解答示例

例2:在特定的场合下:
对10亿个不重复的整数进行排序。
找出10亿个数字中重复的数字。

如上的题目一般会限制内存。

我们换一个与上面示例相似的题目进行演示解答过程。

例3:一台主机,2G内存,40亿个不重复的没排过序的unsigned int的整数的文件,然后再给一个整数,如何快速判断这个整数是否在那40亿个数当中?

我们可以有几种方法解答如上的题目。

遍历法

如果内存足够将40亿个数全部放到内存中,逐个遍历,此时时间复杂度为O(N)。可是现在在内存不足,需要分批读一部分数据到内存然后在做判断,加上I/O操作的时间,时间复杂度远远大于O(N)。

这时,性能问题主要集中在I/O操作,和遍历数组上。那么有没有降低时间复杂度的方法呢?答案是肯定的,如果我们假定内存是足够的,只去优化时间,可以得到下面的方法。

直接寻址表法

申请一个4G超大数组char a[0~2^32-1],将文件中出现的数字置为1,没有出现的置为0。
例如文件存在一个整数1000022,就将a[100002211]=1。

a 0 1 2 2^32-1
value 1 0 1 0 0

这时时间复杂度为O(1),可是空间问题还没有解决。分析下我们的算法,以所需判断的整数为数组下标,用0/1来区分整数是否在。一共用了一个字节来作为标记位,而事实上1Bit就足够标记了。如果能把这部分空间优化掉,4G/8 < 2G 那么就可以解决问题了。看下面的方法。

BitMap

在前面两篇文章中,我们讲过BitMap的概念和应用。

将整数映射到bit上,例如整数10,10/8=1,10%8=2,那么就将a[1]的b[2]置为1。这样时间复杂度即是O(1),内存也得到了压缩。

a 0 1 2 2^32/8-1
bit 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
flag 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

逆向思维优化

unsinged int只有接近43亿(unsigned int最大值为2^32-1=4294967295,最大不超过43亿),我们还可以用某种方式存储没有出现过的3亿个数(使用数组{大小为3亿中最大的数/8 bytes}存储),如果出现在3亿个数里面,说明不在40亿里面。3亿个数存储空间一般小于40亿个。ps:存储4294967296(不到43亿)需要512MB, 而存储294967296只需要35.16MB。

这里需要注意的是,BitMap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。当数据类似(1,1000,10万)只有3个数据的时候,用BitMap时间复杂度和空间复杂度相当大,只有当数据比较密集时才有优势。

总结

在处理海量数据时,我们会想到这些数据的存储结构。在所有具有性能优化的数据结构中,大家使用最多的就是hash表,是的,在具有定位查找上具有O(1)的常量时间,多么的简洁优美。但是数据量大了,内存就不够了。当然也可以使用类似外排序来解决问题的,由于要走IO所以时间上又不行。BitMap基于位的映射,用一个Bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此BitMap在存储空间方面,可以大大节省。

本文总结了几种常用的海量数据处理方法,我们可以根据实际的题意(空间、时间限制)进行灵活应用。了解散列表和BitMap可以参见前面两篇文章

思考

最后,留一个思考题给大家,和上面的解答过程类似,有兴趣的可以在文章下面留言讨论。

例4:现有3G的数据量,数据类型为整型,找出其中重复的数据。
数据:每个数据不大于20亿,且每个数据最多重复一次。
内存:最多用300M的内存进行操作。

参考

  1. 大数据排序算法:外部排序,bitmap算法;大数据去重算法:hash算法,bitmap算法
  2. 大量数据去重:Bitmap和布隆过滤器(Bloom Filter)
微信打赏

赞赏是不耍流氓的鼓励

评论系统未开启,无法评论!