全部博文（124）
分类：
2010-09-04 15:15:49
检索（查询）
|
静态检索 |
动态检索 |
Hash检索 |
|
顺序存储结构 |
随机存储结构 |
消除地址冲突： 1. 开放定址法 2. 拉链法 |
|
不适合做插入/删除操作 |
检索表在检索过程中动态生成，检索成功即返回，不成功则插入 |
|
|
二分法检索 分块检索 |
二叉检索树 B+树 |
大规模数据（排序）
|
方法 |
平均时间复杂度 |
最坏时间复杂度 |
空间复杂度 |
改进 |
|
快排 |
O(nlogn) |
O(n2) |
O(1) |
|
|
堆排 |
O(nlogn) |
O(nlogn) |
O(1) |
|
|
二路归并 |
O(nlogn) |
O(nlogn) |
O(1) |
先用直接插入排序求得较长有序子序列，然后归并 |
数据量较大时为避免记录移动，可采用链式存储结构
——插入排序(直接插入/希尔排序) + 归并排序
难于在链表上实现的排序方法：——快排 + 堆排
2 强用链表存储，改进的方法为：
1. 建立关键字索引，对索引表排序，结束后花O(n)时间代价重排记录。
2. 引入整形数组t[]，t[i]=I；交换R[i]和R[j]的时候只交换t[i]和t[j]。结束后花O(n)时间按t中次序重排记录。
=======================================================================================
|
Bitmap |
数据判重/集合求交集、节省内存 |
Couting BloomFilter |
支持元素删除 |
|
d-left BloomFilter |
支持负载均衡 |
||
|
n-bit BloomFilter |
Couting的简单扩展 |
|
堆 |
求小规模海量数据中前n大/小的值、中位数 |
最大堆 |
前n小 |
|
|
最小堆 |
前n大 |
|||
|
双堆 |
中位数 |
|||
|
索引 |
数据库系统/文件系统 |
B树 |
聚集索引与非聚集索引 |
|
|
B+树 |
||||
1、有1亿个浮点数，请找出其中
对大的10000个。提示：假设每个浮点数占4个字节，1亿个浮点数就要站到相当大的空间，因此不能一次将全部读入内存进行排序。
可
以发现如果一次读入那么机器的内存肯定是受不了的，因此我们只有想其他方法解决，解决方式为了高效还是得符合一定的该概率解决，结果并不一定准确，但是应
该可以作对大部分的数据。
(1.我们可以把1亿个浮点数分组为100W个一组，这样就分为了100个组，第一次在每个组中找出最大的1W个数，第
二次查询的时候就是100W个数中再找出最大的1W个数。
PS:100W个数中再找出最大的1W个数用类似快排的思想搞定。
还有
一种更效率的思路是：
1、读入的头10000个数，直接创建二叉排序树。O(1)
2、对以后每个读入的数，比较是否比前10000个数中
最小的大。(N次比较)如果小的话接着读下面的数。O(N)
3、如果大，查找二叉排序树，找到应当插入的位置。
4、删除当前最小的结点。
5、
重复步骤2，直到10亿个数全都读完。
6、按照中序遍历输出当前二叉排序树中的所有10000个数字。
基本上算法的时间复杂度是O(N)
次比较
算法的空间复杂度是10000(常数)
基于上面的想法，可以用最小堆来实现，这样没加入一个比10000个树中最小的数大时的复杂度为log10000.
2、有一篇英文文章(也就是说每个单词之间由空格分隔)，请找出“csdn”着个单词出现的次数，要求效率最高，并写出算法的时间级。
可
以把单词看成一个N进制数，CSDN相当于('c'-'a')*N^3+('s'-'a')*N^2+('d'-'a')*N+('n'-'a'),然后
查找这个数出现的次数就是答案,也可以建立一颗字典树，然后去计数！
PS:N可以取32，64等
3.假设有1kw个身份证号，以及他们对应的数据。身份证号可能重复，要求找出出现次数最多的身份证号。
简单进行
hash搞定,O(n),如果数据量再扩大我就不知道怎么搞了，用磁盘的话，IO数据是接受不了的
4. 百度每天都会接受数亿的查询请求,
如何在这么多的查询(Query)中找出高频的Query是一个不小的挑战.
而你的任务则更加艰巨,
你需要在极其有限的资源下来找出这些高频的Query.(使用内存不得多于1MB)
。输入文件是一行一个Query,
以文件结束符结尾。每个Query字节数L(一个汉字两个字节)满足：0<=16.
输入大小不超过1GB（包括换行符）。
输出你认为最高频的100个query.
每行一个, 不能有重复,
不能多输出,
但可以少输出(见样例).
hash，然后建立
hash[103][100]的节点的表，每次找出出现次数最少的进行替换。
1.象搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前十
条，我们每次输入的一个字符串为不超过255byte,内存使用只有1G,
请描述思想，写出算发（c语言），空间和时间复杂度，
2.国内
的一些帖吧，如baidu,有几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最好，请描述思想，写出算发（c语言），空间和时间
复杂度
第一题：全部存入内存也是可以的300w*255<1G,当然进行字符串hash，然后进行统计
第二题：思想多级索引，第一
级对主题进行索引，第二级对帖子，可以用一些复杂的数据结构维护，比方说B+树进行维护
题目描述：若有很大一组数据，数据的个数是N(每个数占4个字节),内存大小为M个字节,其中M<4*N,使得不能在现有内存情况下通过
直接排序找到这N个数的中位数。
转一道网上类似题目的解答：
题目：在一个文件中有
10G 个整数，乱序排列，要求找出中位数。内存限制为
2G。只写出思路即可（内存限制为
2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。
关于中位数：数据排序后，位置在最中间的数
值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=
(N+1)/2 ;
当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。
分析：明
显是一道工程性很强的题目，和一般的查找中位数的题目有几点不同。
1.
原数据不能读进内存，不然可以用快速选择，如果数的范围合适的话还可以考虑桶排序或者计数排序，但这里假设是32位整数，仍有4G种取值，需要一个16G
大小的数组来计数。
2.
若看成从N个数中找出第K大的数，如果K个数可以读进内存，可以利用最小或最大堆，但这里K=N/2,有5G个数，仍然不能读进内存。
3.
接上，对于N个数和K个数都不能一次读进内存的情况，《编程之美》里给出一个方案：设k
解法：首先假设是32位无符号整数。
1.
读一遍10G个整数，把整数映射到256M个区段中，用一个64位无符号整数给每个相应区段记数。
说明：整数范围是0
- 2^32 - 1，一共有4G种取值，映射到256M个区段，则每个区段有16（4G/256M
= 16）种值，每16个值算一段，
0～15是第1段，16～31是第2段，……2^32-16
～2^32-1是第256M段。一个64位无符号整数最大值是0～8G-1，这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。
2.
从前到后对每一段的计数累加，当累加的和超过5G时停止，找出这个区段（即累加停止时达到的区段，也是中位数所在的区段）的数值范围，设为
[a，a+15]，同时记录累加到前一个区段的总数，设为m。然后，释放除这个区段占用的内存。
3.
再读一遍10G个整数，把在[a，a+15]内的每个值计数，即有16个计数。
4.
对新的计数依次累加，每次的和设为n，当m+n的值超过5G时停止，此时的这个计数所对应的数就是中位数。
总结：
1.以上方法只
要读两遍整数，对每个整数也只是常数时间的操作，总体来说是线性时间。
2.
考虑其他情况。
若是有符号的整数，只需改变映射即
可。若是64为整数，则增加每个区段的范围，那么在第二次读数时，要考虑更多的计数。若过某个计数溢出，那么可认定所在的区段或代表整数为所求，这里只需
做好相应的处理。噢，忘了还要找第5G+1大的数了，相信有了以上的成果，找到这个数也不难了吧。
3.
时空权衡。
花费256个
区段也许只是恰好配合2GB的内存（其实也不是，呵呵）。可以增大区段范围，减少区段数目，节省一些内存，虽然增加第二部分的对单个数值的计数，但第一部
分对每个区段的计数加快了（总体改变？？待测）。
4.
映射时尽量用位操作，由于每个区段的起点都是2的整数幂，映射起来也很方便。
10亿个整数，要求选取重复次数最多的100个整数
下面是一种解答，如果不愿意看的话，很简单，遍历数组，然后用hash表统计，value为出现的次数，然 后findmax 100次，下面的第五问解答很好
要解答这个问题，首先要弄清楚下面几个条件。
（1）有内存限制吗？
（2）整数的
范围是多少？有符号，无符号，32位还是64位？
（3）整数集的内容大吗？（即出现的整数空间的大小大吗？）
（4）如果只需要求模糊
解，怎么解？
（5）求数组中的第k大元素？
（6）相关问题：求一个整数列中出现次数最多的整数
（7）相关问题：有一个整数
数组，请求出两两之差绝对值最小的值,记住，只要得出最小值即可，不需要求出是哪两个数。
（1）如果没有内存限制，且假设是32位无
符号的整数。最方便的办法就是建立一个整形数组，int hash[2^32]（赞不考虑程序的虚地址空间上限），然后对这10亿个数进行一次遍历，这
样，可以得到这2^32个数各自出现的次数，再对这个hash数组进行取第k大元素，100次后，就可以取出这出现次数最多的前100个数。遍历10亿个
数的时间复杂度是O(n)，n=10^10，求第k大元素的时间复杂度是O(m)，m=2^32(=4294967296)，那么本算法的时间复杂度是
O(n)，空间复杂度是O(s)，s=2^32。内存要2^32*4=16G
（2）如果有内存限制，或者必须满足程序虚地址空间上限。那么可以
对整数空间进行分段处理，比如只提供512M内存，则将2^32个整数划分成32个空间
0~2^(27)-1，2^(27)~2^(28)-1，...，31*2^(27)~2^(32)-1。对原来的10亿个数遍历32次，每次遍历，得到
每个空间的整数的出现次数，并求出此空间中，出现次数最多的前100个整数，保存下来。这样32次之后，就得到了出现次数前3200的整数，再对这
3200个整数取第k大元素，得到出现次数最多的前100个整数。这个算法的时间复杂度也是O(n)，空间复杂度降低多少不知道，但是内存使用降低不少。
（3）如果整数空间比较小，也就是说这10亿个数中有很多重复的数，最方便的办法估计就是维护一个HashTable对象ht，key就是整数
值，value就是该整数值出现的次数。遍历这10亿个元素，得到ht后再对这个ht求第k大元素。那么这个算法的时间复杂度就是
O(n)，n=10^10，空间复杂度是O(m)，m为整数空间大小。
（4）随机采样（或者将原来的顺序打乱，然后再顺序采样）。对样本中的整
数进行出现次数的统计，这个时候采用HashTable的办法最好，时间复杂度是O(n)。如果对使用的空间有所限制，那么只能对该样本进行排序，再对排
序后的样本进行100次遍历得到出现次数最多的前100个整数，则时间复杂度是O(nlogn)，空间复杂度是O(1)。
（5）好像有两种算
法。假设要求数组a[1...n]中第k大元素。
（a）递归快排算法。若n<44（经验值）则直接排序返回第k大元素，否则，将
1到n分成n/5个组，每个组5个元素，然后求这n/5个组的每组的中项元素，再求这n/5个中项元素的中项元素mm（注意，这里也可以用递归调用自身的
方法）。然后对数组a根据mm分成三组，a1中的所有元素小于mm，a2中的所有元素等于mm，a3中的所有元素大于mm，如果|a1|>=k，则
第k大元素在a1中，如果|a1|+|a2|>=k|a1|,则第k大元素就是mm，如果k>|a1|+|a2|，则第k大元素在a3中，再
继续递归调用。这个算法的时间复杂度是O(n)。（注意，这里的中项mm也可以随机选择a中的元素，其时间复杂度也近似于O(n)，而且系数也比较小）。
（b）基于位查找（仅对于无符号整数的查找）。将32位整数的二进制位分为4段，每段8位，先比较a中所有元素高8位，找出第k大元素
高8位的范围，再对应这高8位的范围在次高八位中找第k大元素的范围，...这样4次之后就可以找到第k大元素的。可以举个例子便于理解，在10个3位整
数中找第k大元素，将3位分成3段，每段1位，每位之可能是0，1。如果这10个数的最高位0的个数m大于等于k，则第k大元素的最高位为0，再在最高位
为0的元素中找次高位为第k大元素；如果10个数中最高位0的个数m大于k，则在最高位为1的元素中找此高位为第m-k大元素。...
（6）这
个问题是前面那个问题的特例。有没有特殊的解法使效率又提高一些呢？我觉得没有，因为1和100本来就是常数级，和n比它们的差别是忽略不计的。
（7）
简单的解法是对这个数组排序，然后再对排好序的数组进行一次遍历就可得到两两绝对值最差的最小值，时间复杂度是O(nlogn)。网上说求a的
min，max和长度n，如果Dmax = (max-min+1)/n = 0，那么就说明数组a中有重复的元素，直接返回0。但是如果
Dmax = (max-min+1)/n > 0,那么就以Dmax为箱的长度装入a的元素，再在箱内和箱间比较。我不懂为什么，但是这个空间复
杂度是O(max)，而且好像如果a是1, 2, 3...100，那么Dmax就是1了，那么a不是没有动吗？还有人说够找数组
b，b[i] = a[i] - a[i+1]，则a[i]-a[j]=b[i]+b[i+1]+...+b[j-1]也不知下文了，看来这个题比较搞
啊。就是奥赛题，BS。
有一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出
现的前十个词。
（1） 用hash表统计出现的字符串，并计数：用hash键值计数即出现几次就用相应数字作为键值
（2） 用带有删除的快速排序或堆排序找出最大的十个数
********************************BAIDU*******************************************
1. 给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。
2.
有10个文件，每个文件1G，
每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序
3.
有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词
4.海量日志数据，提取出某日访问百度次数最多的那个IP。
5.2.5亿个整数中找出不重复的整数，内存空间不足以容纳这2.5亿个整数。
6.海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
7.怎么在海量数据中找出重复次数最多的一个
8.上千万or亿数据（有重复），统计其中出现次数最多的前N个数据。
统计可以用hash,二叉数,trie树。对统计结果用堆求出现的前n大数据。增加点限制可以提高效率，比如
出现次数>数据总数／N的一定是在前N个之内
9.1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？
10.一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前十个词。请给出思想，给时间复杂度分析。
11.一个文本文件，也是找出前十个最经常出现的词，但这次文件比较长，说是上亿行或者十亿行，总之无法一次读入内存，问最优解。
12.有10个文件，每个文件1G，
每个文件的每一行都存放的是用户的query，每个文件的query都可能重复要按照query的频度排序
13.100w个数中找最大的前100个数
14.寻找热门查询：
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，
这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，
也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。
15.一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。
如何找到N^2个数的中数(median)？
