海量数据处理

题目1

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址 。

解法

  思路就是先哈希切割哈子，可以先用字符串哈希函数，对每一个 Ip 地址 进行切割，因为是100G ， 那么我们就切割成1000份吧，每个文件就100MB 。
  当第一步完成哈希切割后，不同的ip地址落到了不同的文件中，然后我们进行对单个文件的读取计数，用一个map去统计。map< string,int> CountIpMax, 用这个map去读取单个文件，保存下单个文件的最大出现次数。
  重复第二步，读取完1000个文件后，答案就出来了。

题目2

与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

解法

  我们首先对该数据进行哈希切割使每一个ip落入到不同的文件中，然后建立个最小堆，因为找到前K个最大的。最小堆可以用优先级队列，priority_queue< vector< pair< string,int>>, greateMyFun> , greateMyFun 这个仿函数可以这样写:

struct greateMyFun
{
     bool operator(pair<string,int> & parent , pair<string,int>& child )
       {
            return parent->second > child -> secont ;
       }
} 

然后我们就可以建立一个最小堆啦，这个最小堆按照 ip 的出现次数做比较。
  我们开始的时候，先读取K个ip到堆里，之后每读一个根堆顶最比较，然后比堆顶大，堆顶和元素交换，然后从堆顶开始向下调整，如果比堆顶还小，还肯定不是前K个最大的元素了。
  当我们遍历完，所有被哈希切割的文件后，有找到啦~~

用Linux命令实现

sort logfile | uniq -c | sort -nr | head -K
sort 默认是用字符串的比较方法比较大小的，俩个字符串比较大小的时候，遇见第一个不同字符，第一个不同字符，谁的ASCII码大，就是那个字符串大。
sort -n 选项 ： 按照数字大小比较
sort -r : 本来sort 从小到大输出，现在逆置从大到小输出。
head -K : K是一个具体的数字，输出最大的K个。
uniq -c : uniq 是把相邻的去重，加C是并显示出出现次数。
总结上面这个命令： 先把所有字符串重复的放一起，然后去重统计次数，最后按出现的次数大小排序，最后输出前K个。

题目3

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法?

精确解法

  假设每一个请求大概60字节吧，那么100亿个请求，大概60G。俩个则120G。
  我们用哈希切割对每一个大数据文件都切割6000份。具体就是用字符串哈希函数对每一个Query进行哈希，然后得到的整数再用除留余数法%6000，把每个query映射到不同的文件中。
  接着进行统计，先用set统计第一大数据文件的第 i 号小文件，然后再读取第二个大数据文件的第 i 个小文件时，对每个query进行find 在就是在，不在就是不在。

近似算法

  用布隆过滤器，开2的32次方-1个大小的位（最大个数的位），对第一个大数据文件的数据进行映射，然后再读取第二个大数据文件，每读一个query 就find 下，让布隆过滤器判断是否在里面，如果在布隆中就是交集中的元素。因为布隆存在误判，在不一定准确，不在一定准确，所有是近似算法。

题目4

给上千个文件，每个文件大小为1K—100M。给n个词，设计算法对每个词找到所有包含它的文件，你只有100K内存

变形，返回包含它的所有文件

  思路用倒排索引来解决，即建立一个 map , map < string , list< filename , count> > ，用map 去统计每个字符在那个文件出现了多少次。
  然后统计完后，给一个单词，就遍历该单词的链表，返回出现最大的次数就行。