wordpress 网站打开速度慢,js网站变灰色代码,360ssp里的网站建设,如何建自己网站做淘宝客目录
大数据题目的技巧总括
实例精析 实例一 实例二 实例三 大数据题目的技巧总括
#xff08;1#xff09;哈希函数可以把数据按照种类均匀分流#xff1b;
#xff08;2#xff09;布隆过滤器用于集合的建立与查询#xff0c;并可以节省大量空间#xff1b;
1哈希函数可以把数据按照种类均匀分流
2布隆过滤器用于集合的建立与查询并可以节省大量空间
3一致性哈希解决数据服务器的负载管理问题
前面这三个内容在《与哈希函数有关的结构》这篇文章中已经进行详细介绍。
与哈希函数有关的结构-CSDN博客
4利用并查集结构做岛问题的并行计算
这个内容在《并查集的详解》这篇文章中已经进行详细介绍。
并查集的详解-CSDN博客
5位图解决某一范围上数字的出现情况并可以节省大量空间
关于位图的内容在《与哈希函数有关的结构》这篇文章中有所介绍这篇文章也有相关介绍
与哈希函数有关的结构-CSDN博客
6利用分段统计思想、并进一步节省大量空间
7利用堆、外排序来做多个处理单元的结果合并 这篇文章主要介绍后面三个。
实例精析 实例一 32位无符号整数的范围是0~4,294,967,295现在有一个正好包含40亿个无符号整数的文件所以在整个范围中必然存在没出现过的数。可以使用最多1GB的内存怎么找到所有未出现过的数 这个题目的求解可以采用位图的思想把32位无符号整数的范围做位图对应位图用一个比特表示一个数出现过还是没有出现过准备一个的比特类型的数组那么需要的字节空间也就是512MB然后出现过的记录一次很容易统计出来没有出现过的。 [进阶]只给你3KB的内存怎么找到一个没有出现过的数字 题目给了3KB的内存先计算得出如果把3KB的内存全部变成无符号整型数组的话可以生成长度为768的整型数组在这里我们找到比768小的2的次方的大小选择512长度此时生成一个长度为512的整型数组。然后将0~这个范围内的数平均分成512份接着将题目所给的40亿个数字除以512得到的值为多少就放到哪一份所在的数组中进入一个数组中对应位置的词频加1统计所有的数字最终在统计完毕以后分析哪一份中存在空缺继续在这一份中按照同样的方式进行统计最终一定可以找到亿个没有出现过的数字。 进而我们就找到了思路如果题目只给了1KB内存同样的用1KB*1024/4然后找到不超过它的2的次方的某个数值定义出来整型数组然后将氛围划分进行求解。 [进阶]只给了有限几个变量怎么找到一个没有出现过的数字 将0~这个范围进行二分然后在每一块分析那一块存在空缺继续二分按照这种方式最多二分32次一定可以找到一个没有出现过的数字。 对于后面进阶部分的分析采用的是分段统计的思想在每一段进行题目的求解进而节省空间 实例二 有一个包含100亿个URL的大文件假设每个URL占用64B请找出其中所有重复的URL. 这个题目的解决可以根据哈希函数可以把数据按照种类均匀分流的性质可以准备多台机器然后将100亿个大文件分到各台机器上或者放到多个文件中处理然后对于每一个文件使用哈希函数求对应的哈希值取模得到对应的值然后根据对应的值依次放到各个用来统计的文件中统计完毕以后对每一个统计文件进行处理在统计文件中就可以中就可以找到重复的URL。 也可以使用布隆过滤器进行操作根据能够容许的错误率和100亿个样本量进行布隆过滤器的构建使用布隆过滤器的位图依次开始统计每一个文件进来过的位置描黑后面进来的文件如果通过哈希函数求出哈希值取模以后得到的对应的位置已经描黑那么代表是重复值采用这种方法统计所有的重复值。 [补充]某搜索公司一天的用户搜索词汇是海量的(百亿数据量)请设计一种求出每天热门Top100词汇的可行办法。 这个问题的解决采用的是堆的思想先将全部的搜索词汇按照哈希分流的思想求出哈希值取模放到对应的文件中每一个文件的搜索词汇放到一个大根堆中然后将每一个大根堆的堆顶弹出放到一个总大根堆中将大根堆的堆顶元素弹出为TOP1然后将堆顶元素原来所在的堆的堆顶元素弹出压入总大根堆然后弹出总大根堆的堆顶元素按照这种方式依次打印出TOP100词汇。 实例三 32位无符号整数的范围是0~4294967295现在有40亿个无符号整数可以使用最多1GB的 内存找出所有出现了两次的数。 这个题目依然可以采用哈希函数分流的思想解决假设我们使用1GB的内存哈希表一条记录8字节经过计算1GB内存可以装条记录那么我们就把内存分成个小文件然后对于每一个整数计算出它的哈希值和m取模m的值为这样就可以把每个整数放到对应的小文件中。接着再对每一个小文件进行同样的操作哈希函数文件的划分不断重复上述操作就可以最终找出所有出现两次的数。 这个题目同样可以使用位图的方法去解决题目要求找出所有出现两次的数字那么我们可以用两位信息表示一个数也就是两个比特用00表示没有出现过的数字01表示出现过一次的数字10表示出现过两次的数字11表示出现两次以上的数字。这时对于整个范围的数字需要比特相当于1GB的内存实际只有40亿个整数内存是完全够用的然后对所有的数字使用位图进行统计最后找出所有为10的数组即可找到所有出现两次的数。 [补充]可以使用最多10MB的内存怎么找到这40亿个整数的中位数 这个题目采用分段统计的思想也就是将总的范围根据内存的大小分成几份在每一份上进行分析。题目给了10MB内存计算出10MB内存下最多可以产生的无符号整型数组的长度数组长度最长为选择比它小的2的次方的某个数值选择长度的无符号整型数组然后将0~的范围分成份每一份的整型数组用来统计该数组中出现数字的词频将题目中的40亿个数字每一个除以根据得到的商选择对应的整型数组进入数组的词频加1按照这种操作对所有的数字进行统计。需要找到中位数一共是40个数字中位数也就是第20亿个数字从整型数组的0位置开始统计找到第20个数字所在的位置在它出现的数组位置中根据前面位置出现的词频数找到20亿的数字所在的位置进而找到40亿个整数的中位数。 当然对于这个题目所用的空间仍然可以更小使用分段统计的思想根据题目所给的内存大小决定划分范围的份数是题目的核心。 实例四 有10GB内存的文件每一个文件中存放着一个有符号的整数怎么样利用5GB内存所有的文件中的数字排好序输出。 这个题目可以按照堆的知识进行求解根据题目所给的内存确定堆中可以存放的记录的数量使用小根堆进行记录的统计一个记录占用内存8字节4字节统计key4字节统计value。小根堆建立过程中可能还会有一些内存的消耗假设给每一条记录16字节那么5GB内存可以存放条记录我们取记录为也就是将整个范围分成份然后将无符号整数的范围~一共个数字除以得到每一份就是个数字。此时我们从最小的范围开始统计先将最小的范围的数字从10GB文件中进行弹出放入小根堆进行统计得到每一个数字和它出现的词频。然后将得到的小根堆的数字从头开始弹出此时得到的数字是排好序的接着对后面的范围进行同样的操作此时只使用了5GB内存将所有的数字进行了排序。 对于这个题目还可以采用更小的内存进行操作使用更小的内存求出可以存放的最多的记录数量根据给定的记录的数量使用大根堆进行操作对给定的文件从头开始进行扫描根据大根堆可以存放的记录的大小放入数字当达到给定的记录以后继续扫描的过程中出现的数字和大根堆里面的数字进行比较如果发现更小的数字那么弹出大根堆的堆顶元素然后将更小的数字放进来按照这种操作依次进行下去依次操作完毕以后就可以将一些数字这些数字是较小的一些数字按照大根堆维持了次序排好序接着对剩余的数字按照同样的操作进行。
