优百信息

随着信息的高速发展，越来越多(duō)的数据信息等待处理(lǐ)，如何快速的从这些海量数据中找到你所需要的数据呢(ne)?这就是大数据的处理(lǐ)问题，下面我对几个经典的大数据问题进行分(fēn)析~~~~

一. 设计算法找到每日访问百度出现次数最多(duō)的IP地址?

分(fēn)析：将所有(yǒu)的IP逐个写入到一个大文(wén)件中，因為(wèi)当IP地址采用(yòng)点分(fēn)十进制的方式表示的时候是32位的，所以最多(duō)存在2^32个IP。可(kě)以采用(yòng)映射的方式，比如模1000，将这个较大的文(wén)件映射為(wèi)1000个小(xiǎo)文(wén)件，再将每个小(xiǎo)文(wén)件加载到内存中找到每个小(xiǎo)文(wén)件中出现频率最大的IP(可(kě)以使用(yòng)hash_map的思想进行频率统计);然后在这1000个最大的IP中找出那个出现频率最大的IP，就是出现次数最多(duō)的IP了。
算法思想如下：(分(fēn)而治之+hash)

1).IP地址最多(duō)有(yǒu)2^32=4G个，所以不能(néng)直接将所有(yǒu)的IP地址加载到内存中

2).可(kě)以考虑采用(yòng)”分(fēn)而治之”的思想，就是将IP地址Hash(IP)%1024值，将海量IP分(fēn)别存储到1024个小(xiǎo)文(wén)件中，这样每个小(xiǎo)文(wén)件最多(duō)包含(2^32)/(2^10)=4M个IP地址

3).对于每一个小(xiǎo)文(wén)件，可(kě)以构建一个IP值為(wèi)key,出现次数為(wèi)vaue的hash_map，通过value的比较找到每个文(wén)件中出现次数最多(duō)的那个IP地址

4).经过上述步骤已经得到1024个出现次数最多(duō)的IP地址，再选择一定的排序算法找出这1024个IP中出现次数最多(duō)的那个IP地址

二.给两个文(wén)件，分(fēn)别有(yǒu)100亿个整数，我们只有(yǒu)1G内存，如何找到两个文(wén)件的交集?

分(fēn)析：我们知道对于整形数据来说，不管是有(yǒu)符号的还是无符号的，总共有(yǒu)2^32=4G个数据(100亿个数据中肯定存在重复的数据)，我们可(kě)以采用(yòng)位图的方式来解决，假如我们用(yòng)一个位来代表一个整形数据，那仫4G个数共占512M内存。我们的做法是将第一个文(wén)件里的数据映射到位图中，再拿(ná)第二个文(wén)件中的数据和第一个文(wén)件中的数据做对比，有(yǒu)相同的数据就是存在交集(重复的数据，交集中只会出现一次).

三.假定一个文(wén)件有(yǒu)100亿个整形数据，1G内存，如何找到出现次数不超过两次的数字?

分(fēn)析：要解决这个问题同样需要用(yòng)到位图的思想，在问题二中已经了解到采用(yòng)位图的一个位可(kě)以判断数据是否存在，那仫找到出现次数不超过两次的数字使用(yòng)一个位是无法解决的，在这里可(kě)以考虑采用(yòng)两个位的位图来解决.

根据上述分(fēn)析我们可(kě)以借助两个位，来表示数字的存在状态和存在次数，比如：00表示不存在，01表示存在一次，10表示存在两次，11表示存在超过两次;类似问题二的计算过程：如果一个数字占一位，需要512M内存即可(kě)，但是如果一个数字占两位，则需要(2^32)/(2^2)=2^30=1G内存;将所有(yǒu)数据映射到位图中查找不是11的所对应的数字就解决上述问题了。

题目扩展：其他(tā)条件不变，假如只给定512M内存该如何找到出现次数不超过两次的数字?

分(fēn)析：将数据分(fēn)批处理(lǐ)，假若给定的是有(yǒu)符号数，则先解决正数，再解决负数，此时512M正好解决上述问题.

四.给两个文(wén)件，分(fēn)别有(yǒu)100亿个query，我们只有(yǒu)1G内存，如何找到两文(wén)件交集?分(fēn)别给出精确算法和近似算法!

分(fēn)析：看到字符串首先应该反应过来的就是布隆过滤器，而问题四的近似算法就是采用(yòng)布隆过滤器的方法，之所以说布隆过滤器是近似的算法，因為(wèi)它存在一定 的误判(不存在是肯定的，存在是不肯定的);而要想精确判断字符串文(wén)件的交集，我们可(kě)以采用(yòng)分(fēn)而治之的方法：将大文(wén)件切分(fēn)為(wèi)一个一个的小(xiǎo)文(wén)件，将一个又(yòu)一个的小(xiǎo)文(wén)件拿(ná)到内存中做对比，找到对应的交集。

1.布隆过滤器的近似解决办法：

根据不同的字符串哈希算法，可(kě)以计算出不同的key值，然后进行映射，此时可(kě)以映射到不同的位置，只有(yǒu)当这几个位全部為(wèi)1的时候这个字符串才有(yǒu)可(kě)能(néng)存在(因為(wèi)当字符串过多(duō)的时候可(kě)能(néng)映射出相同的位)，只有(yǒu)一个位為(wèi)0，那仫该串一定是不存在的，所以说布隆过滤器是一种近似的解决办法。将第一个文(wén)件映射到布隆过滤器中，然后拿(ná)第二个文(wén)件中的每个串进行对比(计算出特定串的key，通过不同的哈希算法映射出不同的位，如果全為(wèi)1则认為(wèi)该串是两个文(wén)件的交集;如果有(yǒu)一位為(wèi)0那仫该串一定不是交集).

2.哈希切分(fēn)的精确解决办法：

既然叫做切分(fēn)，顾名思义就是将大文(wén)件切分(fēn)為(wèi)小(xiǎo)文(wén)件，那仫如何切分(fēn)?切分(fēn)的依据是什仫呢(ne)?如果我们在切分(fēn)的时候可(kě)以将相似或者相同的文(wén)件切分(fēn)到同一个文(wén)件中那仫是不是就加快了查找交集的速度呢(ne)?答(dá)案是肯定的。

知道了哈希切分(fēn)的依据我们应该如何处理(lǐ)呢(ne)?我们可(kě)以根据字符串的某个哈希算法得到该字符串的key，然后将key模要分(fēn)割的文(wén)件数(假设為(wèi)1000个文(wén)件，文(wén)件编号為(wèi)0~999)，我们将结果相同的字符串放到同一个文(wén)件中(两个文(wén)件中的字符串通过相同的哈希算法就会被分(fēn)到下标相同的文(wén)件中)，此时我们只需要将下标相同的文(wén)件进行比对就可(kě)以了。。。

哈希切分(fēn)明显比布隆过滤器的方法效率要高，时间复杂度為(wèi)O(N).

具有(yǒu)删除功能(néng)的BloomFilter：