《2022年2022年海量数据处理专题共页 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年海量数据处理专题共页 .pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第 1 页海量数据 处理专题海量数据处理专题(一)大数据量的问题是很多面试笔试中经常出现的问题，比如baidu google腾讯这样的一些涉及到海量数据的公司经常会问到。下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，欢迎与我讨论。本贴从解决这类问题的方法入手，开辟一系列专题来解决海量数据问题。拟包含以下几个方面。Bloom FilterHashBit-Map堆(Heap)双层桶划分数据库索引倒排索引(I
2、nverted Index)外排序 Trie 树 MapReduce 在这些解决方案之上，再借助一定的例子来剖析海量数据处理问题的解决方案。欢迎大家关注。海量数据处理专题(二)【什么是 Bloom Filter】Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此，Bloom Filter不适合那些 零错误 的应用场合。而在能容忍低错误率的应用场合下，B
3、loom Filter通过极少的错误换取了存储空间的极大节省。这里有一篇关于 Bloom Filter的详细介绍，不太懂的博友可以看看。【适用范围】可以用来实现数据字典，进行数据的判重，或者集合求交集【基本原理及要点】对于原理来说很简单，位数组+k 个独立 hash 函数。将 hash 函数对应的值的位数组置 1，查找时如果发现所有hash 函数对应位都是 1 说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个 counter 数组
4、代替位数组，就可以支持删除了。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -第 2 页还有一个比较重要的问题，如何根据输入元素个数n，确定位数组 m的大小及 hash 函数个数。当 hash 函数个数 k=(ln2)*(m/n)时错误率最小。在错误率不大于 E的情况下，m至少要等于 n*lg(1/E)才能表示任意 n 个元素的集合。但 m还应该更大些，因为还要保证bit数组里至少一半为0，则 m应该=nlg(1/E)*lge大概就是 nlg(1/E)1.44倍(lg表示以 2 为底的对数)。举个例子我们假设错误率为0.01，则此时 m应大概是 n 的 13 倍。这样
5、 k大概是 8 个。注意这里 m与 n 的单位不同，m是 bit为单位，而 n 则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用 bloom filter内存上通常都是节省的。【扩展】Bloom filter将集合中的元素映射到位数组中，用k(k 为哈希函数个数)个映射位是否全1 表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter 中的最小值来近
6、似表示元素的出现频率。【问题实例】给你 A,B 两个文件，各存放50亿条 URL，每条 URL占用 64 字节，内存限制是 4G，让你找出 A,B 文件共同的 URL。如果是三个乃至n 个文件呢?根据这个问题我们来计算下内存的占用，4G=232大概是 40 亿*8 大概是340 亿，n=50亿，如果按出错率0.01 算需要的大概是650 亿个 bit。现在可用的是 340亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip，则大大简单了。海量数据处理专题(三)什么是 Hash Hash，一般翻译做 散列，也有直接音译为 哈希 的，就是把任意长度的输入(
7、又叫做预映射，pre-image)，通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。HASH 主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的 128位的编码,这些编码值叫做HASH 值.也可以说，hash 就是找到一种数据内容和数据存放地址之间的映射关系。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -第 3 页数组的特点是：寻址容易，插入和
8、删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构?答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法-拉链法，我们可以理解为 链表的数组 ，如图：左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的。1，除法散列法最直观的一种，上图
9、使用的就是这种散列法，公式：index=value%16 学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫 除法散列法。2，平方散列法求 index 是非常频繁的操作，而乘法的运算要比除法来得省时(对现在的CPU来说，估计我们感觉不出来)，所以我们考虑把除法换成乘法和一个位移操作。公式：index=(value*value)28 如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index 都是 0-非常失败。也许你还有个问题，value 如果很大，value*value不会溢出吗?答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获
10、取相乘结果，而是为了获取index。3，斐波那契(Fibonacci)散列法平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿 value 本身当作乘数呢?答案是肯定的。1，对于 16位整数而言，这个乘数是40503 2，对于 32 位整数而言，这个乘数是 2654435769 3，对于 64 位整数而言，这个乘数是11400714819323198485 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -第 4 页这几个 理想乘数 是如何得出来的呢?这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，如果
11、你还有兴趣，就到网上查找一下斐波那契数列 等关键字，我数学水平有限，不知道怎么描述清楚为什么，另外斐波那契数列的值居然和太阳系八大行星的轨道半径的比例出奇吻合，很神奇，对么?对我们常见的 32位整数而言，公式：i ndex=(value*2654435769)28 如果用这种斐波那契散列法的话，那我上面的图就变成这样了：很明显，用斐波那契散列法调整之后要比原来的取摸散列法好很多。【适用范围】快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。【基本原理及要点】hash 函数选择，针对字符串，整数，排列，具体相应的hash 方法。碰撞处理，一种是open hashing，也称为拉链法；另
12、一种就是closed hashing，也称开地址法，opened addressing。【扩展】d-left hashing中的 d 是多个的意思，我们先简化这个问题，看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半，分别叫做 T1和 T2，给 T1和 T2 分别配备一个哈希函数，h1 和 h2。在存储一个新的 key 时，同时用两个哈希函数进行计算，得出两个地址h1key 和h2key。这时需要检查T1中的 h1key 位置和 T2中的 h2key 位置，哪一个位置已经存储的(有碰撞的)key 比较多，然后将新key 存储在负载少的位置。如
13、果两边一样多，比如两个位置都为空或者都存储了一个key，就把新 key 存储在左边的 T1子表中，2-left也由此而来。在查找一个key 时，必须进行两次 hash，同时查找两个位置。【问题实例】1).海量日志数据，提取出某日访问百度次数最多的那个IP。IP 的数目还是有限的，最多232 个，所以可以考虑使用hash 将 ip 直接存入内存，然后进行统计。海量数据处理专题(四)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -第 5 页【什么是 Bit-map】所谓的 Bit-map 就是用一个 bit 位来标记某个元素对应的Value，而 Key即是该元素。由于采用
14、了Bit 为单位来存储数据，因此在存储空间方面，可以大大节省。如果说了这么多还没明白什么是Bit-map，那么我们来看一个具体的例子，假设我们要对0-7 内的 5 个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map 的方法来达到排序的目的。要表示8 个数，我们就只需要8 个 Bit(1Bytes)，首先我们开辟1Byte 的空间，将这些空间的所有 Bit 位都置为 0(如下图：)然后遍历这 5个元素，首先第一个元素是4，那么就把 4 对应的位置为1(可以这样操作 p+(i/8)|(0 x01(i%8)当然了这里的操作涉及到Big-ending和 Li
15、ttle-ending的情况，这里默认为Big-ending),因为是从零开始的，所以要把第五位置为一(如下图)：然后再处理第二个元素7，将第八位置为 1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit 位的状态如下：然后我们现在遍历一遍Bit 区域，将该位是一的位的编号输出(2，3，4，5，7)，这样就达到了排序的目的。下面的代码给出了一个BitMap 的用法：排序。/定义每个 Byte 中有 8 个 Bit 位#include#define BYTESIZE 8 void SetBit(char*p,int posi)for(int i=0；i(
16、posi/BYTESIZE)；i+)p+；*p=*p|(0 x01(posi%BYTESIZE)；/将该 Bit 位赋值 1 return；void BitMapSortDemo()/为了简单起见，我们不考虑负数int num=3,5,2,10,6,12,8,14,9；/BufferLen这个值是根据待排序的数据中最大值确定的名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 10 页 -第 6 页/待排序中的最大值是14，因此只需要 2 个 Bytes(16 个 Bit)/就可以了。const int BufferLen=2；char*pBuffer=new charBufferL
17、en；/要将所有的 Bit 位置为 0，否则结果不可预知。memset(pBuffer,0,BufferLen)；for(int i=0；i9；i+)/首先将相应 Bit 位上置为 1 SetBit(pBuffer,numi)；/输出排序结果for(int i=0；iBufferLen；i+)/每次处理一个字节(Byte)for(int j=0；jBYTESIZE；j+)/处理该字节中的每个Bit 位/判断该位上是否是1，进行输出，这里的判断比较笨。/首先得到该第 j 位的掩码(0 x01j)，将内存区中的/位和此掩码作与操作。最后判断掩码是否和处理后的/结果相同if(*pBuffer&(0
18、x01j)=(0 x01j)printf(%d,i*BYTESIZE+j)；pBuffer+；int _tmain(int argc,_TCHAR*argv)BitMapSortDemo()；return 0；【适用范围】可进行数据的快速查找，判重，删除，一般来说数据范围是int 的 10 倍以下【基本原理及要点】使用 bit 数组来表示某些元素是否存在，比如8 位电话号码【扩展】Bloom filter可以看做是对 bit-map 的扩展名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 10 页 -第 7 页【问题实例】1)已知某个文件内包含一些电话号码，每个号码为8 位数字，统
19、计不同号码的个数。8 位最多 99 999 999，大概需要 99m个 bit，大概 10 几 m字节的内存即可。(可以理解为从 0-99 999 999 的数字，每个数字对应一个Bit 位，所以只需要 99M个 Bit=1.2MBytes，这样，就用了小小的1.2M左右的内存表示了所有的 8 位数的电话)2)2.5 亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。将 bit-map 扩展一下，用 2bit 表示一个数即可，0 表示未出现，1 表示出现一次，2 表示出现 2 次及以上，在遍历这些数的时候，如果对应位置的值是 0，则将其置为 1；如果是 1，将其置为 2；如
20、果是 2，则保持不变。或者我们不用 2bit 来进行表示，我们用两个bit-map 即可模拟实现这个2bit-map，都是一样的道理。海量数据处理专题(五)【什么是堆】概念：堆是一种特殊的二叉树，具备以下两种性质1)每个节点的值都大于(或者都小于，称为最小堆)其子节点的值2)树是完全平衡的，并且最后一层的树叶都在最左边这样就定义了一个最大堆。如下图用一个数组来表示堆：那么下面介绍二叉堆：二叉堆是一种完全二叉树，其任意子树的左右节点(如果有的话)的键值一定比根节点大，上图其实就是一个二叉堆。你一定发觉了，最小的一个元素就是数组第一个元素，那么二叉堆这种有序队列如何入队呢?看图：假设要在这个二叉堆
21、里入队一个单元，键值为2，那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复杂度为(logn)的操作，二叉堆还是二叉堆。那如何出队呢?也不难，看图：名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -第 8 页出队一定是出数组的第一个元素，这么来第一个元素以前的位置就成了空位，我们需要把这个空位挪至叶子节点，然后把数组最后一个元素插入这个空位，把这个 空位尽量往上挪。这种操作的复杂度也是(logn)。【适用范围】海量数据前 n大，并且 n 比较小，堆可以放入内存【基本原理及要点】最大堆求前 n小，最小堆求前n 大。方法，比如求前n 小，我们
22、比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n 个元素就是最小的n 个。适合大数据量，求前n 小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n 元素，效率很高。【扩展】双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。【问题实例】1)100w 个数中找最大的前100 个数。用一个 100个元素大小的最小堆即可。海量数据处理专题(六)【什么是双层桶】事实上，与其说双层桶划分是一种数据结构，不如说它是一种算法设计思想。面对一堆大量的数据我们无法处理的时候，我们可以将其分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的
23、。【适用范围】第 k 大，中位数，不重复或重复的数字【基本原理及要点】因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子，分治才是其根本(只是只分不治)。【扩展】当有时候需要用一个小范围的数据来构造一个大数据，也是可以利用这种思想，相比之下不同的，只是其中的逆过程。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 10 页 -第 9 页【问题实例】1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5 亿个整数。有点像鸽巢原理，整数个数为232,也就是，我们可以将这232 个
24、数，划分为 28 个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap 就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。当然这个题也可以用我们前面讲过的BitMap 方法解决，正所谓条条大道通罗马 2).5 亿个 int找它们的中位数。这个例子比上面那个更明显。首先我们将int 划分为 216 个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。实际上，如果不是int是 int64，我
25、们可以经过 3 次这样的划分即可降低到可以接受的程度。即可以先将int64 分成 224 个区域，然后确定区域的第几大数，在将该区域分成220 个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有220，就可以直接利用direct addr table进行统计了。3).现在有一个 0-30000 的随机数生成器。请根据这个随机数生成器，设计一个抽奖范围是0-350000 彩票中奖号码列表，其中要包含20000个中奖号码。这个题刚好和上面两个思想相反，一个0 到 3 万的随机数生成器要生成一个 0 到 35 万的随机数。那么我们完全可以将0-35 万的区间分成 35/3=12 个区间
26、，然后每个区间的长度都小于等于3 万，这样我们就可以用题目给的随机数生成器来生成了，然后再加上该区间的基数。那么要每个区间生成多少个随机数呢?计算公式就是：区间长度*随机数密度，在本题目中就是30000*(20000/350000)。最后要注意一点，该题目是有隐含条件的：彩票，这意味着你生成的随机数里面不能有重复，这也是我为什么用双层桶划分思想的另外一个原因。特别声明：1：资料来源于互 联网，版权归属原作者名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -第 10 页2：资料内容属于网 络意见，与本账号立场无关3：如有侵 权，请告知，立即 删除。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -