经典的大数据问题

客官°小女子只卖身不卖艺 2022-07-11 05:40 196阅读 0赞

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

**一. 设计算法找到每日访问百度出现次数最多的IP地址？**

**分析**：将所有的IP逐个写入到一个大文件中，因为当IP地址采用点分十进制的方式表示的时候是32位的，所以最多存在2^32个IP。可以采用映射的方式，比如模1000，将这个较大的文件映射为1000个小文件，再将每个小文件加载到内存中找到每个小文件中出现频率最大的IP(可以使用**hash\_map**的思想进行频率统计)；然后在这1000个最大的IP中找出那个出现频率最大的IP，就是出现次数最多的IP了。

算法思想如下：(**分而治之+hash**)

1).IP地址最多有2^32=4G个，所以不能直接将所有的IP地址加载到内存中

2).可以考虑采用"分而治之"的思想，就是将IP地址Hash(IP)%1024值，将海量IP分别存储到1024个小文件中，这样每个小文件最多包含(2^32)/(2^10)=4M个IP地址

3).对于每一个小文件，可以构建一个IP值为key,出现次数为vaue的hash\_map，通过value的比较找到每个文件中出现次数最多的那个IP地址

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

**二.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？**

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

![Center][]

**三.假定一个文件有100亿个整形数据，1G内存，如何找到出现次数不超过两次的数字？**

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

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

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

分析：将数据分批处理，假若给定的是有符号数，则先解决正数，再解决负数，此时512M正好解决上述问题.

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

分析：看到字符串首先应该反应过来的就是布隆过滤器，而问题四的近似算法就是采用布隆过滤器的方法，之所以说布隆过滤器是近似的算法，因为它存在一定 的误判(**不存在是肯定的，存在是不肯定的**)；而要想精确判断字符串文件的交集，我们可以采用**分而治之**的方法：将大文件切分为一个一个的小文件，将一个又一个的小文件拿到内存中做对比，找到对应的交集。

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

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

2.**哈希切分的精确解决办法：**

既然叫做切分，顾名思义就是将大文件切分为小文件，那仫如何切分？切分的依据是什仫呢？如果我们**在切分的时候可以将相似或者相同的文件切分到同一个文件中**那仫是不是就加快了查找交集的速度呢？答案是肯定的。

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

**哈希切分明显比布隆过滤器的方法效率要高，时间复杂度为O(N).**

具有删除功能的BloomFilter：

struct __HashFunc1
    {
    	size_t BKDRHash(const char *str)  
    	{  
    		register size_t hash = 0;  
    		while (size_t ch = (size_t)*str++)  
    		{         
    			hash = hash * 131 + ch;
    			// 也可以乘以31、131、1313、13131、131313.. 
    		}  
    		return hash;
    	}  
    	size_t operator()(const string& str)
    	{
    		return BKDRHash(str.c_str());
    	}
    };
    
    struct __HashFunc2
    {
    	size_t SDBMHash(const char *str)  
    	{  
    		register size_t hash = 0;  
    		while (size_t ch = (size_t)*str++)  
    		{  
    			hash = 65599 * hash + ch;         
    			//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
    		}  
    		return hash;  
    	}  
    	size_t operator()(const string& str)
    	{
    		return SDBMHash(str.c_str());
    	}
    };
    
    struct __HashFunc3
    {
    	size_t RSHash(const char *str)  
    	{  
    		register size_t hash = 0;  
    		size_t magic = 63689;     
    		while (size_t ch = (size_t)*str++)  
    		{  
    			hash = hash * magic + ch;  
    			magic *= 378551;  
    		}  
    		return hash;  
    	}  
    	size_t operator()(const string& str)
    	{
    		return RSHash(str.c_str());
    	}
    };
    
    struct __HashFunc4
    {
    	size_t APHash(const char *str)  
    	{  
    		register size_t hash = 0;  
    		size_t ch;  
    		for (long i = 0; ch = (size_t)*str++; i++)  
    		{  
    			if ((i & 1) == 0)  
    			{  
    				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));  
    			}  
    			else  
    			{  
    				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));  
    			}  
    		}  
    		return hash;  
    	}  
    	size_t operator()(const string& str)
    	{
    		return APHash(str.c_str());
    	}
    };
    
    struct __HashFunc5
    {
    	size_t JSHash(const char *str)  
    	{  
    		if(!*str)        // 这是由本人添加，以保证空字符串返回哈希值0  
    			return 0;  
    		register size_t hash = 1315423911;  
    		while (size_t ch = (size_t)*str++)  
    		{  
    			hash ^= ((hash << 5) + ch + (hash >> 2));  
    		}  
    		return hash;  
    	}  
    	size_t operator()(const string& str)
    	{
    		return JSHash(str.c_str());
    	}
    };
    
    template<class K=string,
    class HashFunc1=__HashFunc1,
    class HashFunc2=__HashFunc2,
    class HashFunc3=__HashFunc3,
    class HashFunc4=__HashFunc4,
    class HashFunc5=__HashFunc5>
    class BloomFilter
    {
    public:
    	BloomFilter(size_t num)
    		:_bitMap(num*5)
    		,_range(num*5)
    	{}
    	void Set(const K& key)
    	{
    		size_t hash1=HashFunc1()(key)%_range;
    		size_t hash2=HashFunc2()(key)%_range;
    		size_t hash3=HashFunc3()(key)%_range;
    		size_t hash4=HashFunc4()(key)%_range;
    		size_t hash5=HashFunc5()(key)%_range;
    		_bitMap.Set(hash1);
    		_bitMap.Set(hash2);
    		_bitMap.Set(hash3);
    		_bitMap.Set(hash4);
    		_bitMap.Set(hash5);
    
    		cout<<hash1<<endl;
    		cout<<hash2<<endl;
    		cout<<hash3<<endl;
    		cout<<hash4<<endl;
    		cout<<hash5<<endl<<endl;
    	}
    	//void Reset(const K& key);
    	bool Test(const K& key)
    	{
    		size_t hash1=HashFunc1()(key)%_range;
    		if(_bitMap.Test(hash1) == false)
    			return false;
    		size_t hash2=HashFunc2()(key)%_range;
    		if(_bitMap.Test(hash2) == false)
    			return false;
    		size_t hash3=HashFunc3()(key)%_range;
    		if(_bitMap.Test(hash3) == false)
    			return false;
    		size_t hash4=HashFunc4()(key)%_range;
    		if(_bitMap.Test(hash4) == false)
    			return false;
    		size_t hash5=HashFunc5()(key)%_range;
    		if(_bitMap.Test(hash5) == false)
    			return false;
    
    		return true;
    	}
    protected:
    	BitMap _bitMap;
    	size_t _range;
    };
    //具有删除功能的布隆过滤器(引用计数)
    template<class K=string,
    class HashFunc1=__HashFunc1,
    class HashFunc2=__HashFunc2,
    class HashFunc3=__HashFunc3,
    class HashFunc4=__HashFunc4,
    class HashFunc5=__HashFunc5>
    class RefBoolFilter
    {
    public:
    	RefBoolFilter(size_t num)
    	{
    		_range=5*num;
    		_refbitMap.resize(_range);
    	}
    	void Set(const K& key)
    	{
    		size_t hash1=HashFunc1()(key)%_range;
    		size_t hash2=HashFunc2()(key)%_range;
    		size_t hash3=HashFunc3()(key)%_range;
    		size_t hash4=HashFunc4()(key)%_range;
    		size_t hash5=HashFunc5()(key)%_range;
    
    		_refbitMap[hash1]++;
    		_refbitMap[hash2]++;
    		_refbitMap[hash3]++;
    		_refbitMap[hash4]++;
    		_refbitMap[hash5]++;
    	}
    	bool Reset(const K& key)
    	{
    		size_t hash1=HashFunc1()(key)%_range;
    		size_t hash2=HashFunc2()(key)%_range;
    		size_t hash3=HashFunc3()(key)%_range;
    		size_t hash4=HashFunc4()(key)%_range;
    		size_t hash5=HashFunc5()(key)%_range;
    		if (_refbitMap[hash1] == 0
    			||_refbitMap[hash2] == 0
    			||_refbitMap[hash3] == 0
    			||_refbitMap[hash4] == 0
    			||_refbitMap[hash5] == 0)
    		{
    			return false;
    		}
    		_refbitMap[hash1]--;
    		_refbitMap[hash2]--;
    		_refbitMap[hash3]--;
    		_refbitMap[hash4]--;
    		_refbitMap[hash5]--;
    		return true;
    	}
    protected:
    	vector<size_t> _refbitMap;
    	size_t _range;
    };

在上面实现的布隆过滤器中引用了不同的哈希算法，有想研究哈希算法的的童鞋可参考下列链接：

http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html

**五.有一个词典，包含N个英文单词，现在任意给一个字符串，设计算法找出包含这个字符串的所有英文单词!**

分析：**字典树**，要找到满足题意的单词我们需要一层一层遍历字典树，在每层中找一次与给定单词首字母相同的那个位置，进行遍历查找。

以上大数据问题的来源参考九章算法第七讲~~~~

[Center]: /images/20220711/bf312c0d576b44a3b5e803fc04b89c79.png