【数据结构】大数据处理面试题解法

前端之家收集整理的这篇文章主要介绍了【数据结构】大数据处理面试题解法前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

大数据处理的思路一般是这样的:把一个内存中放不下的文件按照一定的方法切分成小文件,再看是否有合适的数据结构能解决这个问题。当然,有时候不用切分,用位图也可以解决,根据具体问题而定。接下来我们看看下面几道大数据的面试题,这种题一般面试官也只是需要一个思路。

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

问题分析:

100G普通机器内存中肯定是放不下的,目前使用的IP地址相当于一个32位的字符串,所以,这么大的文件,我们考虑切分,但是仅仅切分还不行,假设有1G可用的内存,那我们切分成100份,那还得把这100个文件全部遍历一遍,把每一个出现的IP都统计一下次数,最后找到出现次数最多的IP,这是一种解法,不过效率不高。

解决方案:

把这32位的IP通过字符串哈希函数转化成对应的整形,把100G文件分成1000个,从硬盘中读取这些IP,转化成整形后对文件个数取余,余数是多少就放进哪个文件里,这样就保证相同的IP一定是在同一个文件里。这种方法也叫做Hash分桶法。分好之后去统计每个文件里出现次数最多的,问题就转化成找这1000个IP出现次数最多的一个。

(2)与上题条件相同,如何找到top K的IP?

问题分析:

上一题是找出现次数最多的1个,这个是最多的前K个,很容易想到的是像刚才一样,找出每个文件次数最多的,出来再找前K个,然而这样实际上是不对的。为啥呢?因为不能保证某个文件里的最大的就一定比另一个文件里最小的大。比如文件1里出现次数最多是10次,而文件2里出现次数最少的是100次。

解决方案:

跟第一题一样先采用Hash分桶法分好,然后找出每个文件里的top K,最后top K 进行汇总。如何找出top k 呢?这里完全可以考虑建立一个K个数据的小堆,最后堆里保留的就是k个最大的数,为啥要建立小堆?正常想着不是应该建立大堆吗?可以参考我之前写的关于堆的博客,最后有说到:http://blog.csdn.net/pointer_y/article/details/52791518

(3)给定100亿个整数,设计算法找到只出现一次的整数。

问题分析:

首先,100亿整数内存肯定放不下,其次,整数范围是到42亿多,所以,这100亿里一定有很多重复的数字。一般首先想到的就是切分,切到内存中能放下,然后遍历去找。太慢了,它找只出现一次的,可以考虑用位图。

解决方案:

位图一般是用1个位来表示数存在或者不存在,这里它找只出现1次的,所以用两个位来表示,两个位就是4个状态,我们只使用3个状态就好,分别是不存在,出现1次,出现多次,具体多次我们不管,这里只管出现1次的。用两个位表示一个数,42亿个数大概需要开1个G大的位图就ok。

(4)给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?

问题分析:

内存放不下,我们首先想到了切割,把A文件切分成100份,拿B文件去比对。缺点依然是慢,效率不高。

解决方案:

哈希分桶法,100亿个整数分到1000个文件里(一般用哈希分桶法分的文件数都比较多),每个数对1000取余,放到余数对应的文件里。两个文件都经过哈希分桶后,只需要对比编号一致的文件,因为哈希分桶保证了大小相同的整数一定分到同一个文件里。这样就高效很多了。

( 5)1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数。

问题分析:

这个题和第三题很类似。不过它找的是不超过两次的,即是出现1次和出现两次的。

解决方案:

依然使用位图,用两个位来表示一个数,四个状态分别是:没有出现,出现一次,出现2次,出现多次。这次我们关注的出现1次的和出现2次的。

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

问题分析:

这又是一个找交集的问题,所以可以考虑用哈希分桶法解决,那么近似的算法是什么呢?把字符串转化成整形,当一个元素被加入集合时,通过 KHash 函数将这个元素映射成一个位阵列(Bit array)中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:

画图示意:


解决方案:

精确算法用哈希分桶法,和前面的题很类似,近似的用布隆过滤器,得到的结果是近似的。

( 7)如何扩展BloomFilter( 布隆过滤器)使得它支持删除元素的操作?

问题分析:

因为一个字符串是用多个位表示的,其他字符串很可能与要删除的字符串占用了相同的位(如上图),所以,不能直接删除,影响了其他字符状态的表示。

解决方案:

采用引用计数,不过因为字符串出现的次数可能比较大,一个char是不行的,我们用size_t,但是这样就失去了布隆过滤器省空间的优势,这也是没办法的,如果文件太大,那就只能先进行切分了。采用引用计数就不用再拿一个位来表示存在不存在了,直接拿引用计数来表示,为0代表不存在。我在这里实现了一个支持删除的布隆。

源码:

#include<iostream>
#include<vector>
#include<string>
using namespace std;

struct HashFunc1
{
	size_t operator()(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;
	}
};

struct HashFunc2
{
	size_t operator()(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;
	}
};

struct HashFunc3
{
	size_t operator()(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;
	}
};

struct HashFunc4
{
	size_t operator()(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;
	}
};

struct HashFunc5
{
	size_t operator()(const char* str)
	{
		if (!*str)        
		   return 0;
		register size_t hash = 1315423911;
	    while (size_t ch = (size_t)*str++)
		{
		    hash ^= ((hash << 5) + ch + (hash >> 2));
		}
		return hash;
	}
};
//一个字符串类型的布隆过滤器
template<class T=string,class _HashFunc1=HashFunc1,class _HashFunc2=HashFunc2,class _HashFunc3=HashFunc3,class _HashFunc4=HashFunc4,class _HashFunc5=HashFunc5>
class BloomFilter
{
public:
	BloomFilter(int num)
		:_range(num * 5)
	{
		_RefBloomfilter.resize(_range);
	}

	void Set(const char* str)
	{
		//分别通过5个字符串hash函数得到5个对应的位置
		size_t hash1 = HashFunc1()(str) %_range; 
		size_t hash2 = HashFunc2()(str) % _range;
		size_t hash3 = HashFunc3()(str) % _range;
		size_t hash4 = HashFunc4()(str) % _range;
		size_t hash5 = HashFunc5()(str) % _range;
		_RefBloomfilter[hash1]++;
		_RefBloomfilter[hash2]++;
		_RefBloomfilter[hash3]++;
		_RefBloomfilter[hash4]++;
		_RefBloomfilter[hash5]++;
		printf("%d,%d,%d",hash1,hash2,hash3,hash4,hash5);  //可以输出5个位置看一看
		cout << endl;
	}

	bool ReSet(const char* str)  //删除
	{
		size_t hash1 = HashFunc1()(str) % _range;
		size_t hash2 = HashFunc2()(str) % _range;
		size_t hash3 = HashFunc3()(str) % _range;
		size_t hash4 = HashFunc4()(str) % _range;
		size_t hash5 = HashFunc5()(str) % _range;
		if (_RefBloomfilter[hash1] == 0 || _RefBloomfilter[hash2] == 0 
			|| _RefBloomfilter[hash3] == 0 || _RefBloomfilter[hash4] == 0 
			|| _RefBloomfilter[hash5] == 0)
			return false;
		_RefBloomfilter[hash1]--;
		_RefBloomfilter[hash2]--;
		_RefBloomfilter[hash3]--;
		_RefBloomfilter[hash4]--;
		_RefBloomfilter[hash5]--;
		return true;
	}

	bool Test(const char* str)  //查找
	{
		size_t hash1 = HashFunc1()(str) % _range;
		size_t hash2 = HashFunc2()(str) % _range;
		size_t hash3 = HashFunc3()(str) % _range;
		size_t hash4 = HashFunc4()(str) % _range;
		size_t hash5 = HashFunc5()(str) % _range;
		if (_RefBloomfilter[hash1]&&
			_RefBloomfilter[hash2] && 
			_RefBloomfilter[hash3] && 
			_RefBloomfilter[hash4] && 
			_RefBloomfilter[hash5])//都不为0则存在
			return true;
		else
			return false;
	}
protected:
	vector<size_t> _RefBloomfilter;  //为了支持删除,直接使用一个size_t 的vector来做引用计数
	size_t _range;
};

void TestBloomfilter()
{
	BloomFilter<> bf(100);
	string url1("http://write.blog.csdn.net/postedit/53088473");
	string url2("http://blog.csdn.net/pointer_y/article/details/52926334");
	string url3("http://blog.csdn.net/pointer_y/article/details/52776595");
	bf.Set(url1.c_str());
	bf.Set(url2.c_str());
	bf.Set(url3.c_str());
	cout << bf.Test(url1.c_str()) << endl;
	bf.ReSet(url1.c_str());
	cout << bf.Test(url1.c_str())<<endl;
}

结果分析:我只用了3个字符串测试了一下,这三个字符串所占用的位置并没有重复。没有删除前查找字符串1结果是找到了,删除后结果为0没有找到。这是一个支持删除的布隆过滤器,一般的布隆是用位图来实现的,存在还是不存在用多个位来表示就好,很省空间,而要它支持删除就不行了。

前面多次提到位图的概念,那位图是什么呢?即用一个位来表示对应的数据存在还是不存在,STL中也存在位图,我自己实现了一个,只包含了常用的set,reset,test 3个方法

#pragma once
#include<iostream>
#include<vector>
using namespace std;

class BitMap
{
public:
	BitMap(size_t size)
	{
		_bitMap.resize((size>>5)+1);
	}
	void Set(const int& x)
	{
		int index = x >> 5;   //除效率不高,所以这里用右移5位表示除以32,得到x所在的数据个数
		int bit = x % 32;     //得到x的位

		_bitMap[index] |= (1 << bit);
	}
	void ReSet(const int& x)
	{
		int index = x >> 5;
		int bit = x % 32;

		_bitMap[index] &= (~(1 << bit));
	}
	bool Test(const int& x)
	{
		int index = x >> 5;
		int bit = x % 32;

		return _bitMap[index] & (1 << bit);
	}
private:
	vector<size_t> _bitMap;
};

void TestBitMap()
{
	BitMap bm(40);
	bm.Set(10);
	bm.Test(10);
	bm.Test(20);
}
这是我对于大数据问题的一些看法,分享出来,如上述问题有更优的解决方案,请不吝赐教~ 原文链接:https://www.f2er.com/datastructure/382409.html

猜你在找的数据结构相关文章