肥西建设局官方网站,招商加盟网站模板程序,优化设计方案,网站开发的基本条件十七道海量数据处理面试题与Bit-map具体解释作者#xff1a;小桥流水#xff0c;redfox66#xff0c;July。前言本博客内以前整理过有关海量数据处理的10道面试题#xff08;十道海量数据处理面试题与十个方法大总结#xff09;#xff0c;此次除了反复了之前的10道面试题… 十七道海量数据处理面试题与Bit-map具体解释作者小桥流水redfox66July。前言 本博客内以前整理过有关海量数据处理的10道面试题十道海量数据处理面试题与十个方法大总结此次除了反复了之前的10道面试题之后又一次多整理了7道。仅作各位參考不作它用。 同一时候程序猿编程艺术系列将又一次開始创作第十一章以后的部分题目来源将取自下文中的17道海量数据处理的面试题。由于我们觉得下文的每一道面试题都值得又一次思考又一次深究与学习。再者编程艺术系列的前十章也是这么来的。若您有不论什么问题或建议欢迎不吝指正。谢谢。第一部分、十五道海量数据处理面试题1. 给定a、b两个文件各存放50亿个url每一个url各占64字节内存限制是4G让你找出a、b文件共同的url 方案1能够预计每一个文件安的大小为50G×64320G远远大于内存限制的4G。所以不可能将其全然载入到内存中处理。考虑採取分而治之的方法。遍历文件a对每一个url求取然后依据所取得的值将url分别存储到1000个小文件记为,这里漏写个了a1中。这样每一个小文件的大约为300M。遍历文件b採取和a同样的方式将url分别存储到1000小文件里记为。这样处理后全部可能同样的url都在相应的小文件中不正确应的小文件不可能有同样的url。然后我们仅仅要求出1000对小文件里同样的url就可以。求每对小文件里同样的url时能够把当中一个小文件的url存储到hash_set中。然后遍历还有一个小文件的每一个url看其是否在刚才构建的hash_set中假设是那么就是共同的url存到文件里面就能够了。 方案2假设同意有一定的错误率能够使用Bloom filter4G内存大概能够表示340亿bit。将当中一个文件里的url使用Bloom filter映射为这340亿bit然后挨个读取另外一个文件的url检查是否与Bloom filter假设是那么该url应该是共同的url注意会有一定的错误率。 读者反馈crowgnshash后要推断每一个文件大小假设hash分的不均衡有文件较大还应继续hash分文件换个hash算法第二次再分较大的文件一直分到没有较大的文件为止。这样文件标号能够用A1-2表示第一次hash编号为1文件较大所以參加第二次hash编号为2由于1存在第一次hash假设有大文件不能用直接set的方法。建议对每一个文件都先用字符串自然顺序排序然后具有同样hash编号的如都是1-3而不能a编号是1b编号是1-1和1-2能够直接从头到尾比較一遍。对于层级不一致的如a1b有1-11-2-11-2-2层级浅的要和层级深的每一个文件都比較一次才干确认每一个同样的uri。2. 有10个文件每一个文件1G每一个文件的每一行存放的都是用户的query每一个文件的query都可能反复。要求你依照query的频度排序。方案1顺序读取10个文件依照hash(query)%10的结果将query写入到另外10个文件记为中。这样新生成的文件每一个的大小大约也1G假设hash函数是随机的。找一台内存在2G左右的机器依次对用hash_map(query, query_count)来统计每一个query出现的次数。利用高速/堆/归并排序依照出现次数进行排序。将排序好的query和相应的query_cout输出到文件里。这样得到了10个排好序的文件,此处有误更正为b0,b1,b2,b9。对这10个文件进行归并排序内排序与外排序相结合。方案2 一般query的总量是有限的仅仅是反复的次数比較多而已可能对于全部的query一次性就能够增加到内存了。这样我们就能够採用trie树/hash_map等直接来统计每一个query出现的次数然后按出现次数做高速/堆/归并排序就能够了 读者反馈店小二原文第二个样例中“找一台内存在2G左右的机器依次对用hash_map(query, query_count)来统计每一个query出现的次数。”由于query会反复作为key的话应该使用hash_multimap 。hash_map 不同意key反复。hywangw:店小二所述的肯定是错的hash_map(query,query_count)是用来统计每一个query的出现次数 又不是存储他们的值 出现一次 把count1 就可以了 用multimap干什么多谢hywangw。方案3 与方案1相似但在做完hash分成多个文件后能够交给多个文件来处理採用分布式的架构来处理比方MapReduce最后再进行合并。3. 有一个1G大小的一个文件里面每一行是一个词词的大小不超过16字节内存大小限制是1M。返回频数最高的100个词。 方案1顺序读文件里对于每一个词x取然后依照该值存到5000个小文件记为中。这样每一个文件大概是200k左右。假设当中的有的文件超过了1M大小还能够依照相似的方法继续往下分直到分解得到的小文件的大小都不超过1M。对每一个小文件统计每一个文件里出现的词以及相应的频率能够採用trie树/hash_map等并取出出现频率最大的100个词能够用含100个结点的最小堆并把100词及相应的频率存入文件这样又得到了5000个文件。下一步就是把这5000个文件进行归并相似与归并排序的过程了。4. 海量日志数据提取出某日訪问百度次数最多的那个IP。 方案1首先是这一天而且是訪问百度的日志中的IP取出来逐个写入到一个大文件里。注意到IP是32位的最多有2^32个IP。同样能够採用映射的方法比方模1000把整个大文件映射为1000个小文件再找出每一个小文中出现频率最大的IP能够採用hash_map进行频率统计然后再找出频率最大的几个及相应的频率。然后再在这1000个最大的IP中找出那个频率最大的IP即为所求。5. 在2.5亿个整数中找出不反复的整数内存不足以容纳这2.5亿个整数。 方案1採用2-Bitmap每一个数分配2bit00表示不存在01表示出现一次10表示多次11无意义进行共需内存2^32*2bit1GB内存还能够接受。然后扫描这2.5亿个整数查看Bitmap中相相应位假设是00变0101变1010保持不变。所描完事后查看bitmap把相应位是01的整数输出就可以。 方案2也可採用上题相似的方法进行划分小文件的方法。然后在小文件里找出不反复的整数并排序。然后再进行归并注意去除反复的元素。6. 海量数据分布在100台电脑中想个办法高效统计出这批数据的TOP10。方案1在每台电脑上求出TOP10能够採用包括10个元素的堆完毕TOP10小用最大堆TOP10大用最小堆。比方求TOP10大我们首先取前10个元素调整成最小堆假设发现然后扫描后面的数据并与堆顶元素比較假设比堆顶元素大那么用该元素替换堆顶然后再调整为最小堆。最后堆中的元素就是TOP10大。求出每台电脑上的TOP10后然后把这100台电脑上的TOP10组合起来共1000个数据再利用上面相似的方法求出TOP10就能够了。很多其它能够參考第三章、寻找最小的k个数以及第三章续、Top K算法问题的实现 读者反馈QinLeopard第6题的方法中是不是不能保证每一个电脑上的前十条肯定包括最后频率最高的前十条呢比方说第一个文件里A(4), B(5), C(6), D(3)第二个文件里A(4),B(5),C(3),D(6)第三个文件里: A(6), B(5), C(4), D(3)假设要选Top(1), 选出来的结果是A但结果应该是B。 July我想这位读者可能没有明白提议。本题目中的TOP10是指最大的10个数而不是指出现频率最多的10个数。但假设说如今有另外一提要你求频率最多的 10个相当于求訪问次数最多的10个IP地址那道题即是本文中上面的第4题。特此说明。7. 怎么在海量数据中找出反复次数最多的一个 方案1先做hash然后求模映射为小文件求出每一个小文件里反复次数最多的一个并记录反复次数。然后找出上一步求出的数据中反复次数最多的一个就是所求具体參考前面的题。8. 上千万或上亿数据有反复统计当中出现次数最多的钱N个数据。 方案1上千万或上亿的数据如今的机器的内存应该能存下。所以考虑採用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了能够用第6题提到的堆机制完毕。9. 1000万字符串当中有些是反复的须要把反复的全部去掉保留没有反复的字符串。请怎么设计和实现 方案1这题用trie树比較合适hash_map也应该能行。10. 一个文本文件大约有一万行每行一个词要求统计出当中最频繁出现的前10个词请给出思想给出时间复杂度分析。 方案1这题是考虑时间效率。用trie树统计每一个词出现的次数时间复杂度是O(n*le)le表示单词的平准长度。然后是找出出现最频繁的前10个词能够用堆来实现前面的题中已经讲到了时间复杂度是O(n*lg10)。所以总的时间复杂度是O(n*le)与O(n*lg10)中较大的哪一个。11. 一个文本文件找出前10个常常出现的词但这次文件比較长说是上亿行或十亿行总之无法一次读入内存问最优解。 方案1首先依据用hash并求模将文件分解为多个小文件对于单个文件利用上题的方法求出每一个文件件中10个最常出现的词。然后再进行归并处理找出终于的10个最常出现的词。12. 100w个数中找出最大的100个数。 方案1採用局部淘汰法。选取前100个元素并排序记为序列L。然后一次扫描剩余的元素x与排好序的100个元素中最小的元素比假设比这个最小的要大那么把这个最小的元素删除并把x利用插入排序的思想插入到序列L中。依次循环知道扫描了全部的元素。复杂度为O(100w*100)。 方案2採用高速排序的思想每次切割之后仅仅考虑比轴大的一部分知道比轴大的一部分在比100多的时候採用传统排序算法排序取前100个。复杂度为O(100w*100)。 方案3在前面的题中我们已经提到了用一个含100个元素的最小堆完毕。复杂度为O(100w*lg100)。13. 寻找热门查询搜索引擎会通过日志文件把用户每次检索使用的全部检索串都记录下来每一个查询串的长度为1-255字节。假设眼下有一千万个记录这些查询串的反复读比較高尽管总数是1千万可是假设去除反复和不超过3百万个。一个查询串的反复度越高说明查询它的用户越多也就越热门。请你统计最热门的10个查询串要求使用的内存不能超过1G。(1) 请描写叙述你解决问题的思路(2) 请给出基本的处理流程算法以及算法的复杂度。 方案1採用trie树keyword域存该查询串出现的次数没有出现为0。最后用10个元素的最小推来对出现频率进行排序。 关于此问题的具体解答请參考此文的第3.1节第三章续、Top K算法问题的实现。14. 一共同拥有N个机器每一个机器上有N个数。每一个机器最多存O(N)个数并对它们操作。怎样找到N^2个数中的中数 方案1先大体预计一下这些数的范围比方这里假设这些数都是32位无符号整数共同拥有2^32个。我们把0到2^32-1的整数划分为N个范围段每一个段包括2^32/N个整数。比方第一个段位0到2^32/N-1第二段为2^32/N到2^32/N-1…第N个段为2^32N-1/N到2^32-1。然后扫描每一个机器上的N个数把属于第一个区段的数放到第一个机器上属于第二个区段的数放到第二个机器上…属于第N个区段的数放到第N个机器上。注意这个过程每一个机器上存储的数应该是O(N)的。以下我们依次统计每一个机器上数的个数一次累加直到找到第k个机器在该机器上累加的数大于或等于N^2/2而在第k-1个机器上的累加数小于N^2/2并把这个数记为x。那么我们要找的中位数在第k个机器中排在第N^2/2-x位。然后我们对第k个机器的数排序并找出第N^2/2-x个数即为所求的中位数的复杂度是ON^2的。 方案2先对每台机器上的数进行排序。排好序后我们採用归并排序的思想将这N个机器上的数归并起来得到终于的排序。找到第N^2/2个便是所求。复杂度是ON^2*lgN^2的。15. 最大间隙问题给定n个实数求着n个实数在实轴上向量2个数之间的最大差值要求线性的时间算法。方案1最先想到的方法就是先对这n个数据进行排序然后一遍扫描就可以确定相邻的最大间隙。但该方法不能满足线性时间的要求。故採取例如以下方法找到n个数据中最大和最小数据max和min。用n-2个点等分区间[min, max]即将[min, max]等分为n-1个区间前闭后开区间将这些区间看作桶编号为且桶i 的上界和桶i1的下届同样即每一个桶的大小同样。每一个桶的大小为。实际上这些桶的边界构成了一个等差数列首项为min公差为且觉得将min放入第一个桶将max放入第n-1个桶。将n个数放入n-1个桶中将每一个元素x[i] 分配到某个桶编号为index当中这括号中多了个“”并求出分到每一个桶的最大最小数据。最大间隙除最大最小数据max和min以外的n-2个数据放入n-1个桶中由抽屉原理可知至少有一个桶是空的又由于每一个桶的大小同样所以最大间隙不会在同一桶中出现一定是某个桶的上界和气候某个桶的下界之间隙且该量筒之间的桶即便好在该连个便好之间的桶一定是空桶。也就是说最大间隙在桶i的上界和桶j的下界之间产生ji1。一遍扫描就可以完毕。16. 将多个集合合并成没有交集的集合 给定一个字符串的集合格式如。要求将当中交集不为空的集合合并要求合并完毕的集合之间无交集比如上例应输出。(1) 请描写叙述你解决问题的思路(2) 给出基本的处理流程算法以及算法的复杂度(3) 请描写叙述可能的改进。 方案1採用并查集。首先全部的字符串都在单独的并查集中。然后依扫描每一个集合顺序合并将两个相邻元素合并。比如对于首先查看aaa和bbb是否在同一个并查集中假设不在那么把它们所在的并查集合并然后再看bbb和ccc是否在同一个并查集中假设不在那么也把它们所在的并查集合并。接下来再扫描其它的集合当全部的集合都扫描完了并查集代表的集合便是所求。复杂度应该是O(NlgN)的。改进的话首先能够记录每一个节点的根结点改进查询。合并的时候能够把大的和小的进行合这样也降低复杂度。17. 最大子序列与最大子矩阵问题数组的最大子序列问题给定一个数组当中元素有正也有负找出当中一个连续子序列使和最大。 方案1这个问题能够动态规划的思想解决。设b[i]表示以第i个元素a[i]结尾的最大子序列那么显然。基于这一点能够非常快用代码实现。最大子矩阵问题给定一个矩阵二维数组当中数据有大有小请找一个子矩阵使得子矩阵的和最大并输出这个和。 方案2能够採用与最大子序列相似的思想来解决。假设我们确定了选择第i列和第j列之间的元素那么在这个范围内事实上就是一个最大子序列问题。怎样确定第i列和第j列能够词用暴搜的方法进行。 第二部分、海量数据处理之Bti-map具体解释 Bloom Filter已在上一篇文章海量数据处理之Bloom Filter具体解释中予以具体阐述本文接下来着重阐述Bit-map。有不论什么问题欢迎不吝指正。什么是Bit-map 所谓的Bit-map就是用一个bit位来标记某个元素相应的Value 而Key即是该元素。由于採用了Bit为单位来存储数据因此在存储空间方面能够大大节省。 假设说了这么多还没明白什么是Bit-map那么我们来看一个具体的样例假设我们要对0-7内的5个元素(4,7,2,5,3)排序这里假设这些元素没有反复。那么我们就能够採用Bit-map的方法来达到排序的目的。要表示8个数我们就仅仅须要8个Bit1Bytes首先我们开辟1Byte的空间将这些空间的全部Bit位都置为0(例如以下图) 然后遍历这5个元素首先第一个元素是4那么就把4相应的位置为1能够这样操作 p(i/8)|(0×01(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况这里默觉得Big-ending,由于是从零開始的所以要把第五位置为一例如以下图 然后再处理第二个元素7将第八位置为1,接着再处理第三个元素一直到最后处理全然部的元素将相应的位置为1这时候的内存的Bit位的状态例如以下然后我们如今遍历一遍Bit区域将该位是一的位的编号输出23457这样就达到了排序的目的。以下的代码给出了一个BitMap的使用方法排序。//定义每一个Byte中有8个Bit位
#include memory.h
#define BYTESIZE 8
void SetBit(char *p, int posi)
{for(int i0; i (posi/BYTESIZE); i){p;}*p *p|(0x01(posi%BYTESIZE));//将该Bit位赋值1return;
}void BitMapSortDemo()
{//为了简单起见我们不考虑负数int num[] {3,5,2,10,6,12,8,14,9};//BufferLen这个值是依据待排序的数据中最大值确定的//待排序中的最大值是14因此仅仅须要2个Bytes(16个Bit)//就能够了。const int BufferLen 2;char *pBuffer new char[BufferLen];//要将全部的Bit位置为0否则结果不可预知。memset(pBuffer,0,BufferLen);for(int i0;i9;i){//首先将相应Bit位上置为1SetBit(pBuffer,num[i]);}//输出排序结果for(int i0;iBufferLen;i)//每次处理一个字节(Byte){for(int j0;jBYTESIZE;j)//处理该字节中的每一个Bit位{//推断该位上是否是1进行输出这里的推断比較笨。//首先得到该第j位的掩码0x01j将内存区中的//位和此掩码作与操作。最后推断掩码是否和处理后的//结果同样if((*pBuffer(0x01j)) (0x01j)){printf(%d ,i*BYTESIZE j);}}pBuffer;}
}int _tmain(int argc, _TCHAR* argv[])
{BitMapSortDemo();return 0;
}可进行数据的高速查找判重删除一般来说数据范围是int的10倍以下基本原理及要点使用bit数组来表示某些元素是否存在比方8位电话号码扩展Bloom filter能够看做是对bit-map的扩展关于Bloom filter请參见海量数据处理之Bloom filter具体解释。问题实例1)已知某个文件内包括一些电话号码每一个号码为8位数字统计不同号码的个数。 8位最多99 999 999大概须要99m个bit大概10几m字节的内存就可以。 能够理解为从0-99 999 999的数字每一个数字相应一个Bit位所以仅仅须要99M个Bit1.2MBytes这样就用了小小的1.2M左右的内存表示了全部的8位数的电话2)2.5亿个整数中找出不反复的整数的个数内存空间不足以容纳这2.5亿个整数。 将bit-map扩展一下用2bit表示一个数就可以0表示未出现1表示出现一次2表示出现2次及以上在遍历这些数的时候假设相应位置的值是0则将其置为1假设是1将其置为2假设是2则保持不变。或者我们不用2bit来进行表示我们用两个bit-map就可以模拟实现这个2bit-map都是一样的道理。參考http://www.cnblogs.com/youwang/archive/2010/07/20/1781431.html。http://blog.redfox66.com/post/2010/09/26/mass-data-4-bitmap.aspx。完。 转载于:https://www.cnblogs.com/mfrbuaa/p/4304023.html
