《2022年2022年海量数据处理小结 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年海量数据处理小结 .pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、海量的数据处理问题，对其进行处理是一项艰巨而复杂的任务。原因有以下几个方面：一、数据量过大，数据中什么情况都可能存在。如果说有10条数据，那么大不了每条去逐一检查，人为处理，如果有上百条数据，也可以考虑，如果数据上到千万级别，甚至过亿，那不是手工能解决的了，必须通过工具或者程序进行处理，尤其海量的数据中，什么情况都可能存在，例如，数据中某处格式出了问题，尤其在程序处理时，前面还能正常处理，突然到了某个地方问题出现了，程序终止了。二、软硬件要求高，系统资源占用率高。对海量的数据进行处理，除了好的方法，最重要的就是合理使用工具，合理分配系统资源。一般情况，如果处理的数据过TB 级，小型机是要考虑的
2、，普通的机子如果有好的方法可以考虑，不过也必须加大CPU 和内存，就象面对着千军万马，光有勇气没有一兵一卒是很难取胜的。三、要求很高的处理方法和技巧。这也是本文的写作目的所在，好的处理方法是一位工程师长期工作经验的积累，也是个人的经验的总结。没有通用的处理方法，但有通用的原理和规则。那么处理海量数据有哪些经验和技巧呢，我把我所知道的罗列一下，以供大家参考：一、选用优秀的数据库工具现在的数据库工具厂家比较多，对海量数据的处理对所使用的数据库工具要求比较高，一般使用Oracle 或者 DB2，微软公司最近发布的SQL Server 2005 性能也不错。另外在BI 领域：数据库，数据仓库，多维数据
3、库，数据挖掘等相关工具也要进行选择，象好的ETL 工具和好的OLAP 工具都十分必要，例如Informatic ，Eassbase等。笔者在实际数据分析项目中，对每天6000 万条的日志数据进行处理，使用SQL Server 2000 需要花费 6 小时，而使用SQL Server 2005 则只需要花费3 小时。二、编写优良的程序代码处理数据离不开优秀的程序代码，尤其在进行复杂数据处理时，必须使用程序。好的程序代码对数据的处理至关重要，这不仅仅是数据处理准确度的问题，更是数据处理效率的问题。良好的程序代码应该包含好的算法，包含好的处理流程，包含好的效率，包含好的异常处理机制等。三、对海量数据
4、进行分区操作对海量数据进行分区操作十分必要，例如针对按年份存取的数据，我们可以按年进行分区，不同的数据库有不同的分区方式，不过处理机制大体相同。例如SQL Server 的数据库分区是将不同的数据存于不同的文件组下，而不同的文件组存于不同的磁盘分区下，这样将数据分散开，减小磁盘 I/O，减小了系统负荷，而且还可以将日志，索引等放于不同的分区下。四、建立广泛的索引对海量的数据处理，对大表建立索引是必行的，建立索引要考虑到具体情况，例如针对大表的分组、排序等字段，都要建立相应索引，一般还可以建立复合索引，对经常插入的表则建立索引时要小心，笔者在处理数据时，曾经在一个ETL 流程中，当插入表时，首先
5、删除索引，然后插入完毕，建立索引，并实施聚合操作，聚合完成后，再次插入前还是删除索引，所以索引要用到好的时机，索引的填充因子和聚集、非聚集索引都要考虑。五、建立缓存机制当数据量增加时，一般的处理工具都要考虑到缓存问题。缓存大小设置的好差也关系到数据处理的成败，例如，笔者在处理2 亿条数据聚合操作时，缓存设置为100000 条/Buffer ，这对于这个级别的数据量是可行的。六、加大虚拟内存如果系统资源有限，内存提示不足，则可以靠增加虚拟内存来解决。笔者在实际项目中曾经遇到针对18 亿条的数据进行处理，内存为1GB，1 个 P4 2.4G 的 CPU，对这么大的数据量进行聚合操作是有问题的，提示
6、内存不足，那么采用了加大虚拟内存的方法来解决，在6 块磁盘分区上分别建立了6个 4096M 的磁盘分区，用于虚拟内存，这样虚拟的内存则增加为4096*6 + 1024 = 25600 M，解决了数据处理中的内存不足问题。七、 分批处理海量数据处理难因为数据量大，那么解决海量数据处理难的问题其中一个技巧是减少数据量。可以对海量数据分批处理，然后处理后的数据再进行合并操作，这样逐个击破，有利于小数据量的处理，不至于面对大数据量带来的问题，不过这种方法也要因时因势进行，如果不允许拆分数据，还需要另想办法。不过一般的数据按天、按月、按年等存储的，都可以采用先分后合的方法，对数据进行分开处理。八、使用临
7、时表和中间表数据量增加时，处理中要考虑提前汇总。这样做的目的是化整为零，大表变小表，分块处理完成后， 再利用一定的规则进行合并，处理过程中的临时表的使用和中间结果的保存都非常重要，如果对于超海量的数据，大表处理不了，只能拆分为多个小表。如果处理过程中需要多步汇总操作，可按名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 汇总步骤一步步来，不要一条语句完成，一口气吃掉一个胖子。九、优化查询SQL 语句在对海量数据进行查询处理过程中
8、，查询的SQL 语句的性能对查询效率的影响是非常大的， 编写高效优良的SQL 脚本和存储过程是数据库工作人员的职责，也是检验数据库工作人员水平的一个标准，在对SQL 语句的编写过程中，例如减少关联，少用或不用游标，设计好高效的数据库表结构等都十分必要。笔者在工作中试着对1 亿行的数据使用游标，运行3 个小时没有出结果，这是一定要改用程序处理了。十、使用文本格式进行处理对一般的数据处理可以使用数据库，如果对复杂的数据处理，必须借助程序，那么在程序操作数据库和程序操作文本之间选择，是一定要选择程序操作文本的，原因为：程序操作文本速度快；对文本进行处理不容易出错；文本的存储不受限制等。例如一般的海量
9、的网络日志都是文本格式或者 csv格式（文本格式） ，对它进行处理牵扯到数据清洗，是要利用程序进行处理的，而不建议导入数据库再做清洗。十一、定制强大的清洗规则和出错处理机制海量数据中存在着不一致性，极有可能出现某处的瑕疵。例如，同样的数据中的时间字段，有的可能为非标准的时间，出现的原因可能为应用程序的错误，系统的错误等，这是在进行数据处理时，必须制定强大的数据清洗规则和出错处理机制。十二、 建立视图或者物化视图视图中的数据来源于基表，对海量数据的处理，可以将数据按一定的规则分散到各个基表中，查询或处理过程中可以基于视图进行，这样分散了磁盘I/O，正如 10 根绳子吊着一根柱子和一根吊着一根柱子
10、的区别。十三、避免使用32 位机子（极端情况）目前的计算机很多都是32 位的，那么编写的程序对内存的需要便受限制，而很多的海量数据处理是必须大量消耗内存的，这便要求更好性能的机子，其中对位数的限制也十分重要。十四、考虑操作系统问题海量数据处理过程中，除了对数据库，处理程序等要求比较高以外，对操作系统的要求也放到了重要的位置，一般是必须使用服务器的，而且对系统的安全性和稳定性等要求也比较高。尤其对操作系统自身的缓存机制，临时空间的处理等问题都需要综合考虑。十五、使用数据仓库和多维数据库存储数据量加大是一定要考虑OLAP 的，传统的报表可能5、6 个小时出来结果，而基于Cube 的查询可能只需要几
11、分钟，因此处理海量数据的利器是OLAP 多维分析，即建立数据仓库，建立多维数据集，基于多维数据集进行报表展现和数据挖掘等。十六、使用采样数据，进行数据挖掘基于海量数据的数据挖掘正在逐步兴起，面对着超海量的数据，一般的挖掘软件或算法往往采用数据抽样的方式进行处理，这样的误差不会很高，大大提高了处理效率和处理的成功率。一般采样时要注意数据的完整性和，防止过大的偏差。笔者曾经对1 亿 2 千万行的表数据进行采样，抽取出400 万行，经测试软件测试处理的误差为千分之五，客户可以接受。还有一些方法，需要在不同的情况和场合下运用，例如使用代理键等操作，这样的好处是加快了聚合时间，因为对数值型的聚合比对字符
12、型的聚合快得多。类似的情况需要针对不同的需求进行处理。海量数据是发展趋势，对数据分析和挖掘也越来越重要，从海量数据中提取有用信息重要而紧迫，这便要求处理要准确，精度要高，而且处理时间要短，得到有价值信息要快，所以，对海量数据的研究很有前途，也很值得进行广泛深入的研究。一般来说第7 种方案是最常用的，有的主要就是使用第7 种方案，选择的余地也非常的大，不只是俺月，日，年，也可以按周等等划分，灵活性较高而面对大量数据的处理一般都是分批次处理，之前我做一个文本分类器，面对1g 多的索引（索引1g 多，但是分类时需要的数据就大得多了），40-50 分钟就可以跑完所有分类：一是分批操作。二是给 jvm
13、回收内存的时间，比如每次20w 的数据进行分类，完成之后睡眠一段时间，每睡眠一端时间就手动 gc 一次。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 通过这些方式取得了很明显得见效。海量数据处理专题（一）大数据量的问题是很多面试笔试中经常出现的问题，比如baidu google 腾讯这样的一些涉及到海量数据的公司经常会问到。下面的方法是我对海量数据的处理方法进行了一个一般性的总结，当然这些方法可能并不能完全覆盖所有的问题，但
14、是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不一定最优，如果你有更好的处理方法，欢迎与我讨论。本贴从解决这类问题的方法入手，开辟一系列专题来解决海量数据问题。拟包含以下几个方面。1.Bloom Filter 2.Hash 3.Bit-Map 4.堆(Heap) 5.双层桶划分6.数据库索引7.倒排索引（ Inverted Index）8.外排序9.Trie 树10.MapReduce 在这些解决方案之上，再借助一定的例子来剖析海量数据处理问题的解决方案。欢迎大家关注。海量数据处理专题（二）【什么是 Bloom Filter】Bloom
15、Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive） 。因此，Bloom Filter不适合那些 “ 零错误 ” 的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。这里有一篇关于Bloom Filter的详细介绍，不太懂的博友可以看看。【适用范围】可以用来实现数据字典，进行数据的判重，或者集合求交集【基本原理及要点
16、】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - 对于原理来说很简单，位数组+k 个独立 hash 函数。将 hash函数对应的值的位数组置1，查找时如果发现所有 hash函数对应位都是1 说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个 counter数组代替位
17、数组，就可以支持删除了。还有一个比较重要的问题，如何根据输入元素个数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 倍。这样 k 大概是 8 个。注意这里 m与 n 的单位不同， m是 bit为单位，而n 则是以元
18、素个数为单位( 准确的说是不同元素的个数 ) 。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。【扩展】Bloom filter将集合中的元素映射到位数组中，用k（k 为哈希函数个数）个映射位是否全1 表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用 counter中的最小值来近似表示元素的出现频率。【问题实例】给你 A,B 两个文件，各存放50 亿条 URL，
19、每条 URL 占用 64 字节，内存限制是4G，让你找出A,B文件共同的 URL。如果是三个乃至n 个文件呢？根据这个问题我们来计算下内存的占用，4G=232大概是 40 亿*8 大概是 340 亿，n=50 亿，如果按出错率 0.01算需要的大概是650 亿个 bit。 现在可用的是340 亿，相差并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换成ip ，则大大简单了。海量数据处理专题（三）什么是 HashHash ，一般翻译做“ 散列 ” ，也有直接音译为“ 哈希 ” 的，就是把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度
20、的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要 的函数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - HASH 主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128 位的编码 ,这些编码值叫做 HASH 值. 也可以说， hash
21、就是找到一种数据内容和数据存放地址之间的映射关系。数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法 拉链法，我们可以理解为 “ 链表的数组 ” ，如图：左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。元素特征转变为数组下标的方法
22、就是散列法。散列法当然不止一种，下面列出三种比较常用的。1 ，除法散列法最直观的一种，上图使用的就是这种散列法，公式：index = value % 16 学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“ 除法散列法 ” 。2 ，平方散列法求 index是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的CPU 来说，估计我们感觉不出名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - 来），所以我们考虑把除法换成
23、乘法和一个位移操作。公式：index = (value * value) 28 如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的index都是 0 非常失败。也许你还有个问题，value如果很大， value * value不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取index 。3 ，斐波那契（ Fibonacci）散列法平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿 value本身当作乘数呢？答案是肯定的。1，对于 16 位整数而言，这个乘数是40503 2，对于 32
24、位整数而言，这个乘数是2654435769 3，对于 64 位整数而言，这个乘数是11400714819323198485 这几个 “ 理想乘数 ” 是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，如果你还有兴趣，就到网上查找一下“ 斐波那契数列 ” 等关键字，我数学水平有限，不知道怎么描述清楚为什么，另外斐波那契数列的值居然和太阳系八大行星的轨道半径的比例出奇吻合，很神奇，对么？对我们常见的32 位整数而言，公式：i ndex = (value * 2654435769) 28 如果用这种斐波那契散列法的话，那我上面的图就变成这
25、样了：很明显，用斐波那契散列法调整之后要比原来的取摸散列法好很多。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - 【适用范围】快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。【基本原理及要点】hash 函数选择，针对字符串，整数，排列，具体相应的hash 方法。碰撞处理，一种是open hashing，也称为拉链法；另一种就是closed hashing，也称开地址法， opened addressing。【扩展】
26、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存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个key ，就把新 key 存储在左边的T1 子表中，
27、2-left也由此而来 。在查找一个key 时，必须进行两次hash ，同时查找两个位置。【问题实例】1). 海量日志数据，提取出某日访问百度次数最多的那个IP 。IP 的数目还是有限的，最多232个，所以可以考虑使用hash 将 ip 直接存入内存，然后进行统计。海量数据处理专题（四）【什么是 Bit-map】所谓的 Bit-map就是用一个bit 位来标记某个元素对应的Value ， 而 Key 即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。如果说了这么多还没明白什么是Bit-map，那么我们来看一个具体的例子，假设我们要对0-7 内的 5 个元素(4,7
28、,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8 个数，我们就只需要8 个 Bit （1Bytes ），首先我们开辟1Byte 的空间，将这些空间的所有 Bit 位都置为 0( 如下图： ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - 然 后 遍 历 这5个 元 素 ， 首 先 第 一 个 元 素 是4 ， 那 么 就 把4对 应 的 位 置 为1 （ 可 以
29、 这 样 操 作p+(i/8)|(0 x01(i%8) 当然了这里的操作涉及到Big-ending和 Little-ending的情况 ，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一（如下图）：然后再处理第二个元素7 ，将第八位置为1, ，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1 ，这时候的内存的Bit 位的状态如下：然后我们现在遍历一遍Bit 区域，将该位是一的位的编号输出（2，3 ，4，5，7），这样就达到了排序的目的。下面的代码给出了一个BitMap的用法：排序。/ 定义每个 Byte 中有 8 个 Bit 位#include mem
30、ory.h#define BYTESIZE 8 void SetBit(char *p, int posi) for(int i=0; i (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这个值是根据待排序的数据中最大值确定的/ 待排序中的最大值是14 ，因此只需要2 个 Bytes(16个 Bit) 名师资料总结 - - -精品
31、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 14 页 - - - - - - - - - / 就可以了。const int BufferLen = 2; char *pBuffer = new charBufferLen; / 要将所有的 Bit 位置为 0 ，否则结果不可预知。memset(pBuffer,0,BufferLen); for(int i=0;i9;i+) / 首先将相应Bit 位上置为 1 SetBit(pBuffer,numi); / 输出排序结果for(int i=0;iB
32、ufferLen;i+)/每次处理一个字节(Byte) for(int j=0;jBYTESIZE;j+)/处理该字节中的每个Bit 位 / 判断该位上是否是1 ，进行输出，这里的判断比较笨。/ 首先得到该第j 位的掩码（ 0 x01 j），将内存区中的/ 位和此掩码作与操作。最后判断掩码是否和处理后的/ 结果相同if(*pBuffer&(0 x01 j) = (0 x01 j) printf(%d ,i*BYTESIZE + j); pBuffer+; int _tmain(int argc, _TCHAR* argv) BitMapSortDemo(); return 0; 【适用范围】名
33、师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - 可进行数据的快速查找，判重，删除，一般来说数据范围是int 的 10 倍以下【基本原理及要点】使用 bit 数组来表示某些元素是否存在，比如8 位电话号码【扩展】Bloom filter可以看做是对bit-map的扩展【问题实例】1) 已知某个文件内包含一些电话号码，每个号码为8 位数字，统计不同号码的个数。8 位最多 99 999 999，大概需要 99m个 bit，大概 10
34、几 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；如果是 2 ，则保持不变。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bi
35、t-map，都是一样的道理。海量数据处理专题（五）【什么是堆】概念：堆是一种特殊的二叉树，具备以下两种性质1）每个节点的值都大于（或者都小于，称为最小堆）其子节点的值2）树是完全平衡的，并且最后一层的树叶都在最左边这样就定义了一个最大堆。如下图用一个数组来表示堆：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - 那么下面介绍二叉堆：二叉堆是一种完全二叉树，其任意子树的左右节点（如果有的话）的键值一定比根节点大，上图其实就是一个
36、二叉堆。你一定发觉了，最小的一个元素就是数组第一个元素，那么二叉堆这种有序队列如何入队呢？看图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - 假设要在这个二叉堆里入队一个单元，键值为2 ，那只需在数组末尾加入这个元素，然后尽可能把这个元素往上挪，直到挪不动，经过了这种复杂度为(logn) 的操作，二叉堆还是二叉堆。那如何出队呢？也不难，看图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -
37、- - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - 出队一定是出数组的第一个元素，这么来第一个元素以前的位置就成了空位，我们需要把这个空位挪至叶子节点，然后把数组最后一个元素插入这个空位，把这个“ 空位 ” 尽量往上挪。这种操作的复杂度也是 (logn) 。【适用范围】海量数据前 n 大，并且n 比较小，堆可以放入内存【基本原理及要点】最大堆求前 n 小，最小堆求前n 大。方法，比如求前n 小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换那个最大元素。这样最后得到的n 个元素就是最小的
38、n 个。适合大数据量，求前 n 小， n 的大小比较小的情况，这样可以扫描一遍即可得到所有的前n 元素，效率很高。【扩展】双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。【问题实例】1)100w个数中找最大的前100 个数。用一个 100 个元素大小的最小堆即可。海量数据处理专题（六）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 【什么是双层桶】事实上，与其说双层桶划分是一种数据结构，不如说它是一种算法设计思想。面对
39、一堆大量的数据我们无法处理的时候，我们可以将其分成一个个小的单元，然后根据一定的策略来处理这些小单元，从而达到目的。【适用范围】第 k 大，中位数，不重复或重复的数字【基本原理及要点】因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子，分治才是其根本（只是“ 只分不治 ” ）。【扩展】当有时候需要用一个小范围的数据来构造一个大数据，也是可以利用这种思想，相比之下不同的，只是其中的逆过程。【问题实例】1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。有点像鸽巢原理，整数个数为
40、232,也就是，我们可以将这232个数，划分为 28个区域 ( 比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。当然这个题也可以用我们前面讲过的BitMap方法解决，正所谓条条大道通罗马 2).5亿个 int找它们的中位数。这个例子比上面那个更明显。首先我们将int 划分为 216个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。实际上，如
41、果不是int 是 int64 ，我们可以经过3 次这样的划分即可降低到可以接受的程度。即可以先将int64分成 224个区域，然后确定区域的第几大数，在将该区域分成220个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有220，就可以直接利用direct addr table进行统计了。3). 现在有一个0-30000的随机数生成器 。请根据这个随机数生成器，设计一个抽奖范围是0-350000彩票中奖号码列表，其中要包含20000个中奖号码。这个题刚好和上面两个思想相反，一个0 到 3 万的随机数生成器要生成一个0 到 35 万的随机数。那么我们完全可以将0-35万的区间分成35
42、/3=12个区间，然后每个区间的长度都小于等于3 万，这样我们就可以用题目给的随机数生成器来生成了，然后再加上该区间的基数。那么要每个区间生成多少个随机数呢？计算公式就是：区间长度* 随机数密度，在本题目中就是30000*（20000/350000）。最后要注意一点，该题目是有隐含条件的：彩票，这意味着你生成的随机数里面不能有重复，这也是我为什么用双层桶划分思想的另外一个原因。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -