深圳推广网站,wordpress 投票网站,网站建设600元包,搜索引擎优化技术文章目录 前言从40个亿中产生一个不存在的整数位图存储数据的原理使用10MB来存储如何确定分块的区间 用2GB内存在20亿的整数中找到出现次数最多的数从100亿个URL中查找的问题40亿个非负整数中找出两次的数。总结 前言 提示#xff1a;人生之中总有空白#xff0c;但有时… 文章目录 前言从40个亿中产生一个不存在的整数位图存储数据的原理使用10MB来存储如何确定分块的区间 用2GB内存在20亿的整数中找到出现次数最多的数从100亿个URL中查找的问题40亿个非负整数中找出两次的数。总结 前言 提示人生之中总有空白但有时我们称它为人生的副歌。在一些或长或短的时间段里您听不见它于是以为已经忘记了这段副歌。然后有一天在您独自一人周边又没有什么可以分散注意力的时候这段副歌忽然又响起来。就像儿歌的歌词它依旧充满魔力。 --帕特里克·莫迪亚诺《隐形墨水》 理解前面的题目是不是很难但是抓住重点理解起来是很容易的这里再强调一些经典问题查找 从40个亿中产生一个不存在的整数
题目要求给定一个输入文件包含40亿个非负整数请设计一个算法产生一个不存在该文件的整数假如你有1GB的内存你该怎么完成这个任务。
进阶如果只有10MB的内存呢你该怎么处理
这里不用写代码如果你能将方法说明白我们看看这里要怎么做。
位图存储数据的原理
假设用哈希表来存储出现过的数如果是40亿个数都不相同那么哈希表的记录数为40亿条存一个32为的整数需要4B所以最差的情况需要40亿*4B 160亿字节大约需要16GB的空间这很不符合要求。
40亿*4B 160亿字节大约需要16GB的空间
40亿/8字节 5亿字节大约需要0.5GB的空间就可以存储了。
1 字节 8 位 1 B字节 8 bit位 1 GB千兆字节 1024 MB 1024 * 1024 KB 1024 * 1024 * 1024 B
数据量很大采用位的方式俗称位图存储数据是常用的思路那位图如何存储元素呢我们可以使用BitMap的方式来表示数出现的情况具体来说是申请一个长度位 4295967295 的类型的数组bitArr就是boolean类型bitArr上的每一个位置只可以表示0或者1状态8个bit为1B所以长度就是 4295967295 的bit数组占用空间为500MB这样就满足题目要求了。
4294967295 是一个能容纳 40亿个不同数的最小 2 的幂次减 1的值。也就是说2的32次方4294967296可以表示的不同数的个数是40亿再减去1就得到了4294967295。
那么使用bitArr需要注意什么就是遍历这40一个数遇到所有的数时就把bitArr相对应得位置设置为1.例如遇到1024就将bitArr[1024] 1。
遍历完成后再次遍历bitArr,看看哪个位置上没有被设置为1这个数就是不存在40亿个数中。当然如果bitArr[5243] 0就可以将这个数输出出来。
位存储得核心是我们存储得并不是这40亿个数据本身而是其对应得位置。这一点明白就很简单了不是。
使用10MB来存储
如果只有10MB得内存使用位图就不行了就需要另辟蹊径了。这里我们采用分块得思想拿时间换空间通过两次遍历来搞定。
40亿个数需要500MB得空间如果只有10MB得空间至少需要50块才可以。
一般来说我们划分得是使用2得整数倍因此分成64块最合理。
首先就是将0~42949672952^32 -1)这个范围平均分成64个区间每个区间是67108864个数例如
第0区间0~67108863第1区间67108864~134217728…第i区间67108864*i~67108864I 1 - 1第63区间4227858432~4294967295
因为一共40亿个数所以如果统计罗在每个区间上得数有多少肯定有至少一个区间上得计数是小于67108864。利用这一点就可以找出其中一个没有出现过得数具体过程是通过两次遍历来搞定。
第一次遍历先申请长度为64得整数数组countArr[0…63],countArr[i]用来统计区间i上得有多少个遍历40亿个数根据当前数是多少决定哪个区间上得计数增加。例如6710886567108865/67108864 1所以第1区间上得计数增加countArr[1]遍历完这40亿个数之后遍历countArr,必然会有某个位置上得值countArr[i]小于67108864表示第i区间上至少有一个数没有出现过。我们肯定会找到至少一个这样得区间。
此时使用得内存就是countArr的大小64*4B是一个非常小的数。
假设找到第37区间上的计数小于67108864那么我们对这40亿个数据进行第二次遍历
申请长度为67108864的BitMap这占用的空间大约是8M记为bitArr[0…67108863].遍历这40亿个数此时只需要关注落在第37区间上的数即为num(num 满足 num/67108864 37)其他区间的数全部忽略。如果步骤2的num在第37区间将bitArr[num - 67108864*37]的值设置为1也就是只做第37区间上的数的bitArr映射。遍历完40亿个数之后在bitArr上必然存在没有被设置1的位置假设第i个位置上面的值没有被设置成1那么对应的67108864*37 i这个数就是没有出现过的数。
总结一下进阶解法
根据10MB 的内存限制确定统计区间的大小就是第二次遍历时bitArr大小利用区间计数的方式找到那个计数不去的区间这个区间上肯定有没有出现的数对这个区间上的数做bitmap映射在遍历一遍bitmap找到一个没有出现的数即可
如何确定分块的区间
上面的例子中我们可以采用连词遍历第一次将数据分成64块刚好解决问题。那么我们为什么不是128、3216或者其他类型呢
这里主要是保证第二次遍历每块都能放进去10MB的空间中
2^23 10MB 2 ^ 24,而2^23 8388608大约是8MB也就是说我们依次分块的大小只能为8MB左右在上面我们也看到了第二次遍历如果分块是64刚好满足要求。
所以这里我们最少要分64块当然如果分成128块256块也是可以的。
用2GB内存在20亿的整数中找到出现次数最多的数
题目要求有一个包含20亿个全是32位整数的大文件在其中找出出现次数最多的数。
要求内存限制为2GB
想要在很多整数中找出现次数最多的数通常的做法是使用哈希表出现的每一个数做词频统计哈希表的key是某个整数value是这个整数出现的次数。就本题目来说一共20亿个数哪怕只有一个数出现20依次用32为的整数也是可以便是出现依次而不会产生溢出所以哈希表的key需要占用4Bvalue也是4B。那么哈希表中的一条数据就要占用8B当哈希表中的记录数有20亿时需要至少1.6GB的内存。
如果20亿个数中不同数超过2亿中最极端的情况时20亿个数都不同那么在哈希变种可能要产生20亿条数据显然这样的内存时不够用的所以一次性用哈希表统计20亿个数的办法行不通的。
解决办法是把包含20亿个数的大文件用哈希函数分成16个小文件根基哈希函数的性质同一种数不能能被散列到不同的小文件上同时每个小文件中不同的数一定不会找过2亿中假设哈希函数足够优秀。然后对每一个小文件用哈希表来统计其中每种出现的次数我们就能得到16个小文件中各自出现最多的数还有各自的统计次数。接下来就是在个16个小文件各自的第一名相互比较找到次数最多的那个。
把一个大的集合通过哈希函数分配到多台机器中或者分配到多个文件中这种技巧也是处理大数据面试时最常见的方法之一。但是到底分配多少台机器分配到多少个文件中在解题一定要先确定下来。可能在与面试官沟通的过程中面试官指定也可能时根据具体的限制来确定比如本体确定分成16个文件就是根据内存限制2GB的条件来确定的。
从100亿个URL中查找的问题
题目有一个包含100亿URL的大文件假设每个URL占用时64B请找出其中重复的URL。
补充题目某搜索公司一天的用户搜索词汇时海量的百亿数据量请设计出一种可以求出每天热门top100词汇的可行办法。
解答原问题的加法使用解决大数据问题的一种常规套路把大文件通过哈希函数分配到机器或者通过哈希函数把大文件拆成小文件。一直进行这种划分直到满足结果要求的资源限制。首先需要确认面试官时候存在资源上限时间等。在明确限制要求之后可以将每条URL通过哈希函数分配到若干台机器中或者拆分成小文件。这里的“若干”是由具体的资源限制计算出来的数量。
例如将100亿字节的大文件通过哈希函数分配到100台机器上面然后每一台机器分别统计分给自己的URL中是否有重复的URL同时哈希函数的性质决定了同一条URL不可能分给不同的机器或者将单机上的大文件通过哈希函数拆分成1000个小文件对每个小文件再利用哈希表遍历找出重复的URL还可以在非给机器差分完后对进行排序排序后再看看是否有重复的URL出现总之牢记一点很多大数据问题都离不开分流要么是使用哈希函数将大文件的内容分配给不同的机器要么是用哈希函数将大文件拆分成小文件然后处理每个小文件的集合。
补充问题
最开始还是用哈希分流的思想来处理把包含百亿数量的词汇文件分流到不同的机器上面具体多少机器由面试官规定的资源或者给出的限制来决定对每一台机器来说如果分到的数据量依然很大的话比如出现内存不够或者其他问题可以继续使用哈希函数把每台机器的分流文件再次拆分成小文件处理。处理小文件的时候通过哈希表统计每种词及其频率哈希表记录建立完成后在遍历哈希表遍历哈希表的过程中使用大小为100的小根堆来选出每个小文件的top100整体未排序的top100。每一个文件都有自己词频的小根堆将小根堆的的词按照词频排序就得到了每个小文件排序后的top100.然后把各个小文件排序后的top100进行外排序或者继续使用小根堆就可以挑选出每台机器上的top100.不同机器之间的top100在进行外排序或者使用小根堆。最终求出整个百亿数据量中top100**.对于TopK问题除了使用哈希函数分流和用哈希表做词频统计外还经常使用堆结构和外排序的手段进行处理。**
40亿个非负整数中找出两次的数。
题目要求32位无符号整数的范围是0~4294967295现在又10亿个无符号整数可以使用最多1GB的内存找出所有出现了两次的数。
本体可以看看第一题的进阶这里出现了限制在两次。
首先可以使用bitmap的方式来表示出现的情况具体来说是申请一个长度为4294967295 * 2的bit类型数组bitArr用2个位置来表示一个数出现的词频1B占用8bit所以长度为4294967295 * 2的bit类型的数组占用1GB的空间那么怎么使用这个bitArr数组呢遍历这40亿个无符号数如果初次遇到就把bitArr[num*2]和bitArr[num * 2 ]设置成01第二次遇到设置成10第三次遇到设置11.当然以后在遇到就不关系了。遍历完成之后再次遍历bitArr如果发现bitArr[i * 21]和bitArr[i * 2]设置为10那么i就是出现两次的数。 总结
提示大数据的处理方式海量数据问题大数据压缩大数据分块数据流处理 如果有帮助到你请给题解点个赞和收藏让更多的人看到 ~ (▔□▔)/
如有不理解的地方欢迎你在评论区给我留言我都会逐一回复 ~
也欢迎你 关注我 喜欢交朋友喜欢一起探讨问题。
