2019秋招复习笔记--海量数据处理（整理中）

红太狼 2023-06-05 12:39 3阅读 0赞

## 1、海量日志数据，提取出某日访问百度次数最多的那个IP。 ##

[来源][Link 1]

> 算法思想：分而治之+Hash  
> 1.IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理；   
> 2.可以考虑采用“分而治之”的思想，按照IP地址的Hash(IP)%1024值（hash映射），把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址；   
> 3.对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；  
> 4.可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP；  
> 需要注意的是，相同的IP经过Hash映射之后一定处于同一组中，故这种方法一定能统计到出现频率最大的那个IP。

## 2. 100G的硬盘上的整数型数据， 1G的内存。找出这100G数据里面所有不重复的数据。最少需要多大的辅助内存。 ##

来源：腾讯面试

> **解法1：位图**
> 
> int型的整数一共有232个，我们申请232 bits, 也就是232位， 用1位表示一个数是否出现了，0表示未出现，1表示出现了。比如4出现了，我们将这232位的第4位置为1。10000出现了则把第10000位置为1。这样232 bits = 232/8 = 229B, 我们知道210约等于1000， 230约等于109。故229 B  = 2\-1 \* 109 B = 2\-1 \* 1GB = 500MB
> 
> ；
> 
> **拓展**
> 
> 如果用两位表示数出现的次数就可以分别统计出现0次、出现1次、出现2次和出现多次的数字。00表示未出现，01表示出现1次，10表示出现两次，11表示两次以上。然后扫描100亿个数，查看位图中对应的位置，如果是00,01,10，则加1变成01,10,11；如果是11，则不变。最后再扫描一遍位图，输出01，10对应的数。  2^32 \* 2 = 8Gbits = 1GB。
> 
>     那么这样做的情况下怎样找到这个数呢？我举个例子，例如我们此时读入一个数是：64，64对应的所在bit位是：64*2=128，也就是说第 127 和 128 位共同
>     标示了它的出现状态。其他的以此类推。每当我们读出一个数，我们就这样去找到它对应的bit位，先读出bit位的值，再做记录，已经是01的，再次来到，那么
>     就应该修改为10。最后的我们这样得出结果：扫描整个位图，如果是10的，就下标/2得出这个数。

整理源:
    https://blog.csdn.net/v_JULY_v/article/details/6279498
    https://blog.csdn.net/IT_YUAN/article/details/8106573
    https://blog.csdn.net/v_july_v/article/details/7382693

转载于:https://www.cnblogs.com/greatLong/p/11462610.html

[Link 1]: https://blog.csdn.net/v_JULY_v/article/details/6279498