转自：兵马俑BBS http://bbs.xjtu.edu.cn
发信人: appsony (懒羊羊), 信区: Algorithm
标 题: 跟风发点补充的--大数据处理
发信站: 兵马俑BBS (Fri Nov 27 19:13:23 2009), 本站(bbs.xjtu.edu.cn)
用来应付面试题，祝大家找工作顺利。
1.完美哈希函数(Perfect Hash Function)
所谓完美哈希函数，就是指没有冲突的哈希函数，设定义域为X，值域为Y, n=|X|,m=|Y|，那么肯定有m>=n,如果对于不同的key1,key2属于X,有h(key1)!=h(key2)，那么称h为完美哈希函数，当m=n时，h称为最小完美哈希函数（这个时候就是一一映射了）。
相信大家在处理大规模字符串数据的时候，经常遇到这样的需求：首先需要把数据中出现的每个不同字符串分配一个唯一的整数ID，以后就用这个整数来代替这个字符串了。这个时候只要找到一个字符串的完美哈希函数，就可以解决了。
算法：假设有2个随机的哈希函数h1和h2,都将字符串映射到0..m-1域内，假设现在有一个g函数，使得 (g(h1(str_i))+g(h2(str_i))) % n = i,那么这个哈希函数就可以作为最小完美哈希函数了。由于h1和h2已知，现在的目标就是要找到g函数，建立一个m个顶点的图，然后添加n条边，第i条边为(h1(str_i),h2(str_i)),边权为i，可以证明：只要这个图是一个无环图，就一定存在满足条件的g函数：每次找一个没有分配g值的顶点v，令g[v]=0，然后从这个顶点开始深度优先遍历，给其它每个点分配相应的g值。
问题：算法最关键的问题是m值的选取，这个涉及到2方面的取舍：1.m值不能太大，否则g函数定义域太大，内存存不下 2.m值不能太小，否则生成的图有环的概率会非常大。
解决方法：设置更多的随机函数，比如h1,h2,h3,这个时候哈希函数就是(g(h1(str_i))+g(h2(str_i)+g(h3(str_i))) % n = i，可以证明，此时m值不需要很大，就能使生成的图无环的概率很大。
2.排序二叉树
排序二叉树是一个动态的数据结构，一般说的排序二叉树的用途就是动态的快速查找某一个数。但是如果我们在二叉树的结点上增加更多的信息，就能发挥更nb的作用了。
实例：有一个在线论坛，发帖量和回复量都非常大，帖子按照新发表或者新回复的时间来排序，要你设计一个算法，来快速的选出第n页的所有帖子（假设每页显示20个帖子）。
解决方法：这个就是要动态的查询一堆数里面第x大到第y大之间的所有数了，可以增加，删除，修改那些数。如果在普通的二叉排序树的结点上增加一个域，表示它的左子树中的结点数，那么就可以很好的解决这个问题了。
void search(tree t, int x, int y) {
if(x > y) return;
if(y <= t.left_num) {
search(t.left_child, x, y);
return;
}
if(x > t.left_num + 1) {
search(t.right_child, x - t.left_num - 1, y - t.left_num - 1);
return;
}
search(t.left_child, x, t.left_num);
选取t;
search(t.right_child, 1, y - t.left_num - 1);
}
注意：上面说的二叉树在面对大规模数据时，是指的平衡二叉树。
扩展：陈启峰的SBT树，有兴趣的可以去研究下。
3.树状数组
假设有n个元素的数组a，每次可以在某个元素上执行加上一个数或者减去一个数的操作，然后需要能够快速的求出a[0]+a[1]+a[2]+...a[i]。这个可以用树状数组解决，每次更新或者询问的时间复杂度都是O(logn).
应用实例：qq拼音输入法引入了等级制度，用户会不定期的发送一个积分w到服务器，然后服务器把这个w累加到用户的总积分，并快速的返回这个用户的总积分在全球的排名。
解决方法：1. 由于这个问题实质还是动态的求某个数的排名（也就是求集合中比这个数小的数有多少个），可以利用上面平衡二叉树或者SBT树来解决，但是由于用户众多，树太大，只能保存在磁盘上。
2.注意到这个问题有个显著的特点：用户量很大，但是用户的积分值不可能很大。假设用户的积分值最大为10^6，那么开一个10^6的数组a,a[i] 表示积分为i的用户有多少个，那么当需要给某个用户增加积分时，假设这个用户原始积分为o,那么首先使a[o]=a[o]-1,然后 a[o+w]=a[o+w]+1,询问积分为i的用户的排名，实质就是求a[0]+a[1]+a[2]+...a[w-1]，这个用上面说到的树状数组就可以了。时间空间效率都非常好。
4.索引
数据库里面的聚族索引和非聚族索引
这方面的问题挺重要的，但是了解的人不是很多。一般来说，聚族索引就是数据的存放顺序和聚族索引的顺序是一致的（有时数据会直接存放到聚族索引那个磁盘页中），而非聚族索引则不然，在非聚族索引中，需要存放一个磁盘地址指向真实的数据块，而且连续的非聚族索引会对应着不连续的数据块。由于数据只可能有一种存放顺序，所以一个数据表中只能有一个聚族索引，但是可以有多个非聚族索引。
查询效率区别：由于上面说到的区别，这2个索引在应对不同类别的查询时，效率是不同的。一般来说，聚族索引可以很高效的应对各种查询，但是非聚族索引基本只能高效的应对结果集是少量的查询，比如select * from A where id=1。对于范围类查询，比如select * from A where id>1 and id<1000,如果id字段是非聚族索引，那么效率远远没有聚族索引高，因为数据库每找到一个索引页后，还需要单独的一次io去取数据块，而且由于非聚族索引的特点，这些数据块是不连续的，导致磁头会不停的寻道，浪费很多io时间。