转载

海量数据处理方法归类

海量数据，找出最热门（频率最高）的某一数据，或前100的数据。一般情况下数据大小几百个G，而内存限制就1个G，完成计算。

应用场景：

（1）海量日志数据，提取出某日访问百度次数最多的那个IP；

（2）搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

解决思路：主要是内存限制。如果内存够，那好，我们用用排序就OK了；那内存不够，我们就分批次来。分批次来，那么首先思考要怎么分批？显然要满足的条件就是尽量把相同的日志、IP分到同一个文件中去，这样避免多个文件中还互相包含同一条日志。顺理成章，若分为1000个小文件，根据hash(IP) % 1000将日志对号入座，然后分别对每个小文件用hashMap进行频率统计，最后再将1000个小文件中最**（前**）的日志提取出来，利用常规的排序即可。

有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序

解决思路：典型的Top K算法。模板：先用HashMap统计频率（或去重），维护一个K大小的堆，统计Top K就行了。

给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

解决思路：可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,...,a999）中。这样每个小文件的大约为300M。

遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,...,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,...,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数

方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。此法以内存为代价。方法总结：内存不够，分治之；如何分治，取hash；想取TOP K，就用堆！

正文到此结束