所谓海量数据处理,无非就是基于海量数据上的存储、处理、操作。何谓海量,就是数据量太大,导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。那解决办法呢?
针对时间,我们可以采用巧妙的算法搭配合适的数据结构,如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树;
针对空间,无非就一个办法:大而化小,分而治之(hash映射),你不是说规模太大嘛,那简单啊,就把规模大化为规模小的,各个击破不就完了嘛;
至于所谓的单机及集群问题,通俗点来讲,单机就是处理装载数据的机器有限(只要考虑cpu,内存,硬盘的数据交互),而集群,机器有多辆,适合分布式处理,并行计算(更多考虑节点和节点间的数据交互)。
海量数据处理的方法 处理海量数据问题有6种方法:
基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。
基本原理:当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素很可能在。
Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。
Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来表示某个元素是否存在,因此在存储空间方面,可以大大节省。
Bitmap排序方法:
第一步,将所有的位都置为0,从而将集合初始化为空。
第二步,通过读入文件中的每个整数来建立集合,将每个对应的位都置为1。
第三步,检验每一位,如果该位为1,就输出对应的整数。
Bloom filter可以看做是对bit-map的扩展。
基本原理及要点:实现方式,节点孩子的表示方式。
扩展:压缩实现。
基本原理及要点:利用数据的设计实现方法,对海量数据的增删改查进行处理。
基本原理及要点:一种索引方法,被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树
MapReduce是一种计算模型,简单的说就是将大批量的工作(数据)分解(MAP)执行,然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后,可以通过大量机器进行并行计算,减少整个操作的时间。
基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。
原题:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门),请你统计最热门的10个查询串,要求使用的内存不能超过1G。
数据规模大,一次处理不了,我们就需要将数据通过hash映射切分;而本题的情况属于数据量可以一次放入内存(300万个字符串假设没有重复,都是最大长度,那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理),所以只是需要一个合适的数据结构。
所以我们在此直接读数据进行hash统计,统计后的数据只有0.75G,可以直接进行排序,而对这种TopK问题,一般是采用堆来解决。
方案2:采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。
如果每个数据元素只出现一次,而且只出现在某一台机器中,那么可以采取以下步骤统计出现次数Top10的数据元素:求出每台电脑上的Top10后,然后把这100台电脑上的Top10组合起来,共1000个数据,再利用上面类似的方法求出Top10就可以了。
但如果同一个元素重复出现在不同的电脑中,则有两种方法:
方案2: 一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。
方案3: 与方案1类似,但在做完hash,分成多个文件后,可以交给多个文件来处理,采用分布式的架构来处理(比如MapReduce),最后再进行合并。
可以估计每个文件安的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
方案1:分而治之/hash映射,然后hashmap统计,最后找出所有value为1的key值。
方案2:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32 * 2 bit=1 GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。
上千万或上亿的数据,现在的机器的内存应该能存下。所以考虑采用hash_map来进行统计次数。然后利用堆取出前N个出现次数最多的数据。
方案1:如果文件比较大,无法一次性读入内存,可以采用hash取模的方法,将大文件分解为多个小文件,对于单个小文件利用hash_map统计出每个小文件中10个最常出现的词,然后再进行归并处理,找出最终的10个最常出现的词。
方案2:通过hash取模将大文件分解为多个小文件后,除了可以用hash_map统计出每个小文件中10个最常出现的词,也可以用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度),最终同样找出出现最频繁的前10个词(可用堆来实现),时间复杂度是O(nlog10)。
方案1:申请512M的内存,一个bit位代表一个unsigned int值。读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0表示不存在。
方案2:这个问题在《编程珠玑》里有很好的描述,大家可以参考下面的思路,探讨一下:又因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;
这里我们把40亿个数中的每一个用32位的二进制来表示假设这40亿个数开始放在一个文件中。
然后将这40亿个数分成两类: 最高位为0和最高位为1 并将这两类分别写入到两个文件中,其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折半了);与要查找的数的最高位比较并接着进入相应的文件再查找。再然后把这个文件为又分成两类: 次最高位为0和次最高位为1。
并将这两类分别写入到两个文件中,其中一个文件中数的个数<=10亿,而另一个>=10亿(这相当于折半了);与要查找的数的次最高位比较并接着进入相应的文件再查找。以此类推,就可以找到了,而且时间复杂度为O(logn),方案2完。
位图法比较适合于这种情况,它的做法是按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置上1,如遇到5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。
用bitmap来做这个问题。
首先对数据进行预处理。定义10亿bit位个int.在32位计算机下,一个int是32位,10亿位的话,就需要10亿除以32个int整数。大概有很多个。第一个int标记0-31这个数字范围的QQ号存不存在,比如说0000001这个QQ号,我就把第一个int的第1位置1。第二个int能够标记32-63这个范围的QQ存不存在,以此类推。把这10亿个QQ号预处理一遍。然后计算你给我的这个QQ号,它是在哪个int里面,然后找到相应的数据位,看是1还是0,就能在O(1)的时间里找到。
方案1: 顺序读取存放号码文件的中所有号码,并取139之后的八位转换为int类型;每读取号码数满一百万个(这个数据可配置)将已经读取的号码排序并存入新建的临时文件 将所有生成的号码有序的临时文件合并存入结果文件 这个算法虽然解决了空间问题,但是运行效率极低,由于IO读写操作太多,加上步骤1中的排序的算法(快速排序)本来效率就不高
方案2:bitmap
一个号码占一个bit,一共需要99999999bit,一个int32位,所以需要312.5万个int值,即1250万Byte = 12.5M,算法如下:
初始化bits[capacity] 顺序所有读入电话号码,并转换为int类型,修改位向量值bits[phoneNum]=1 遍历bits数组,如果bits[index]=1,转换index为电话号码输出
方案1:在前面的题中,我们已经提到,用一个含100个元素的最小堆完成。复杂度为O(100万*lg100)。
方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,直到比轴大的一部分比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100万*100)。
方案3:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素移除,并把x利用插入排序的思想,插入到序列L中。依次循环,直到扫描了所有元素,复杂度为O(100万*100)。