海里数据处理面试题中的一些概念介绍
今天下午阅读了《十道海量数据处理面试题与十个方法大总结》一文,具体内容不再赘述。只是将其中几个不太熟悉的知识点整理一下。 1、Bitmap算法所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。 如果说了这么多还没明白什么是Bit-map,那么我们来看一个具体的例子,假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte 的空间,将这些空间的所有Bit位都置为0(如下图:)
然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0x01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending),因为是从零开始的,所以要把第五位置为一(如下图):
然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态如下:
然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。 案例:①:对10亿个不重复的整数进行排序。 ②:找出10亿个数字中重复的数字。 当然我只有普通的服务器,就算2G的内存吧,在这种场景下,我们可以选择位图算法 2、Trie树?????? Trie树也称字典树,因为其效率很高,所以在在字符串查找、前缀匹配等中应用很广泛,其高效率是以空间为代价的。 一.Trie树的原理 ??? 利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。 ??? 下面以英文单词构建的字典树为例,这棵Trie树中每个结点包括26个孩子结点,因为总共有26个英文字母(假设单词都是小写字母组成)。 ??? 则可声明包含Trie树的结点信息的结构体: #define MAX 26 typedef struct TrieNode //Trie结点声明 { bool isStr; //标记该结点处是否构成单词 struct TrieNode *next[MAX]; //儿子分支 }Trie; ??? 其中next是一个指针数组,存放着指向各个孩子结点的指针。 ??? 如给出字符串"abc","ab","bd","dda",根据该字符串序列构建一棵Trie树。则构建的树如下: ???? ?Trie树的根结点不包含任何信息,第一个字符串为"abc",第一个字母为'a',因此根结点中数组next下标为'a'-97的值不为NULL,其他同理,构建的Trie树如图所示,红色结点表示在该处可以构成一个单词。很显然,如果要查找单词"abc"是否存在,查找长度则为O(len),len为要查找的字符串的长度。而若采用一般的逐个匹配查找,则查找长度为O(len*n),n为字符串的个数。显然基于Trie树的查找效率要高很多。 但是却是以空间为代价的,比如图中每个结点所占的空间都为(26*4+1)Byte=105Byte,那么这棵Trie树所占的空间则为105*8Byte=840Byte,而普通的逐个查找所占空间只需(3+2+2+3)Byte=10Byte。 二.Trie树的操作 ??? 在Trie树中主要有3个操作,插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况,因此只考虑删除整棵树。 1.插入 ? 假设存在字符串str,Trie树的根结点为root。i=0,p=root。 ? 1)取str[i],判断p->next[str[i]-97]是否为空,若为空,则建立结点temp,并将p->next[str[i]-97]指向temp,然后p指向temp; ?? 若不为空,则p=p->next[str[i]-97]; ? 2)i++,继续取str[i],循环1)中的操作,直到遇到结束符' ',此时将当前结点p中的isStr置为true。 2.查找 ? 假设要查找的字符串为str,Trie树的根结点为root,i=0,p=root ? 1)取str[i],判断判断p->next[str[i]-97]是否为空,若为空,则返回false;若不为空,则p=p->next[str[i]-97],继续取字符。 ? 2)重复1)中的操作直到遇到结束符' ',若当前结点p不为空并且isStr为true,则返回true,否则返回false。 3.删除 ? 删除可以以递归的形式进行删除。 关于Trie树的测试程序,可以参考此处:http://www.cnblogs.com/dolphin0520/archive/2011/10/11/2207886.html (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- perl – 哪一个是好习惯,一个词汇文件句柄或一个typeglob?
- Learning Perl: 5.5. Formatted Output with printf
- delphi 将webbrowser的cookie给idhttp用
- java – Storm和Spring 4集成
- 计科1111-1114班《算法》加分题(20-50分)
- java – 想要创建一个过滤器来检查cookie,然后从控制器保存
- VCL组件之重要的公用属性
- 在PERL中将SHA1十六进制转换为base64编码(对于Apache htpas
- php – Laravel“类型错误:使用PUT / PATCH方法更新记录时
- perl读文件第m到n行的实例