本系列文章对海量数据面试题进行了归类和总结,给出海量数据处理问题的通用解决思路,后面附有例题,希望大家能够举一反三。
首先考虑是否需要将大文件分成小文件,针对数据太大,内存受限,只能是将大文件化成小文件(取模映射);
当大文件转化了小文件,那么我们便可以采用常规的Hashmap(ip,value)来进行频率统计;
统计完了之后,便进行排序。
注意:1GB = (2^10)^3 = 2^30 = 1073741824B ~= 11亿B
(1)分而治之/hash映射:顺序读文件中对于每个词x取hash(x)%5000,然后按照该值存到5000个小文件(记为x0,x1,…x4999)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。
(2)hash统计:对每个小文件,采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
(3)堆/归并排序:取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100个词及相应的频率存入文件,这样又得到了5000个文件。最后就是把这5000个文件进行归并(类似于归并排序)的过程了。
(1)由于IP是32位的,最多有个2^32个IP,约4GB;
(2)可以采用映射的方法,比如模1000,把整个日志大文件映射为1000个小文件;
(3)再找出每个小文中出现频率最大的IP(可以采用Hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。
(4)然后再在这1000个最大的IP中,找出那个频率最大的IP。
事实上只有300万的Query,每个Query255B,文件最大是7.65亿B < 1GB。因此我们可以考虑把他们都放进内存中去,而现在只是需要一个合适的数据结构,在这里,Hash Table绝对是我们优先的选择。所以我们摒弃分而治之/hash映射的方法,直接上hash统计,然后排序。
可以估计每个文件的大小为5G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
(1)将a、b均按照相同的hash方法分散到1000个小文件中:a1-a1000、b1-b1000;
(2)a1和b1比较,去重相同的url;
(3)依次类推,将所有相同url合并;