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

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

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

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内存，如何找到两个文件交集？分别给出精确 算法和近似算法。

问题分析：

这又是一个找交集的问题，所以可以考虑用哈希分桶法解决，那么近似的算法是什么呢？把字符串转化成整形，当一个元素被加入集合时，通过 K 个Hash 函数将这个元素映射成一个位阵列（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

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

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test