专栏首页蛮三刀的后端开发专栏海量数据处理问题知识点复习手册

海量数据处理问题知识点复习手册

前言

本文快速回顾了常考的知识点,用作面试复习,事半功倍。

面试知识点复习手册

通过以下两种途径查看全复习手册文章导航

本文参考

十道海量数据处理面试题与十个方法大总结

https://blog.csdn.net/v_july_v/article/details/6279498

重点:十七道海量数据处理面试题与Bit-map详解

https://blog.csdn.net/v_july_v/article/details/6685962

有删减,修改,补充额外增加内容

本作品采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。

-----正文开始-----

预备知识点

Bitmap和布隆过滤器(Bloom Filter)

https://blog.csdn.net/zdxiq000/article/details/57626464

Bitmap

我们只想知道某个元素出现过没有。如果为每个所有可能的值分配1个bit,32bit的int所有可能取值需要内存空间为:

232bit=229Byte=512MB

但对于海量的、取值分布很均匀的集合进行去重,Bitmap极大地压缩了所需要的内存空间。于此同时,还额外地完成了对原始数组的排序工作。缺点是,Bitmap对于每个元素只能记录1bit信息,如果还想完成额外的功能,恐怕只能靠牺牲更多的空间、时间来完成了。

Bloom Filter

如果说Bitmap对于每一个可能的整型值,通过直接寻址的方式进行映射,相当于使用了一个哈希函数,那布隆过滤器就是引入了k(k>1)个相互独立的哈希函数,保证在给定的空间、误判率下,完成元素判重的过程。下图中是k=3时的布隆过滤器。

那么布隆过滤器的误差有多少?我们假设所有哈希函数散列足够均匀,散列后落到Bitmap每个位置的概率均等。

若以m=16nm=16n计算,Bitmap集合的大小为238bit=235Byte=32GB238bit=235Byte=32GB,此时的ε≈0.0005。并且要知道,以上计算的都是误差的上限。

布隆过滤器通过引入一定错误率,使得海量数据判重在可以接受的内存代价中得以实现。从上面的公式可以看出,随着集合中的元素不断输入过滤器中(nn增大),误差将越来越大。但是,当Bitmap的大小mm(指bit数)足够大时,比如比所有可能出现的不重复元素个数还要大10倍以上时,错误概率是可以接受的。

这里有一个google实现的布隆过滤器,我们来看看它的误判率:

在这个实现中,Bitmap的集合m、输入的原始数集合n、哈希函数k的取值都是按照上面最优的方案选取的,默认情况下保证误判率ε=0.5k<0.03≈0.55,因而此时k=5。

而还有一个很有趣的地方是,实际使用的却并不是5个哈希函数。实际进行映射时,而是分别使用了一个64bit哈希函数的高、低32bit进行循环移位。注释中包含着这个算法的论文“Less Hashing, Same Performance: Building a Better Bloom Filter”,论文中指明其对过滤器性能没有明显影响。很明显这个实现对于m>232时的支持并不好,因为当大于231−1的下标在算法中并不能被映射到。

海量数据问题解题思路

参考:https://blog.csdn.net/luochoudan/article/details/53736752

个人将这些题分成了两类:一类是容易写代码实现的;另一类侧重考察思路的。毫无疑问,后一种比较简单,你只要记住它的应用场景、解决思路,并能在面试的过程中将它顺利地表达出来,便能以不变应万变。前一种,需要手写代码,就必须要掌握一定的技巧,常见的解法有两种,就是前面说过的堆排和快排的变形。

  • 堆排序:我认为不用变形,会原始堆排序就行。
  • 快排变形(找到最大的TopK): 当len(ary) - K == key or len(ary) - K == key + 1时就得到了最大的K个数。

注意点:

  • 分小文件:hash后直接存储原来的值,而不是将hash值分到各个文件中。
  • 单位换算:一字节8bit

经典题目:

序号对应于参考网页:

https://blog.csdn.net/v_july_v/article/details/6685962

hash后将海量数据分到另外的小文件中,分别处理,最后再归并

1.2.3.4.7.8.11.13

经典例题: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出现的次数,然后按出现次数做快速/堆/归并排序就可以了

bitmap直接映射

经典例题:5

在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。 方案1:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32*2bit=1GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。 方案2:也可采用上题类似的方法,进行划分小文件的方法。然后在小文件中找出不重复的整数,并排序。然后再进行归并,注意去除重复的元素。

最大最小堆

经典例题:6

海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。 在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆)。比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现,然后扫描后面的数据,并与堆顶元素比较,如果比堆顶元素大,那么用该元素替换堆顶,然后再调整为最小堆。最后堆中的元素就是TOP10大。

桶排序

经典例题:15

给定n个实数,求着n个实数在实轴上向量2个数之间的最大差值,要求线性的时间算法。 方案1:最先想到的方法就是先对这n个数据进行排序,然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法:

  1. 找到n个数据中最大和最小数据max和min。
  2. 用n-2个点等分区间[min, max],即将[min, max]等分为n-1个区间(前闭后开区间),将这些区间看作桶,编号为,且桶i 的上界和桶i+1的下届相同,即每个桶的大小相同。每个桶的大小为:。实际上,这些桶的边界构成了一个等差数列(首项为min,公差为),且认为将min放入第一个桶,将max放入第n-1个桶。
  3. 将n个数放入n-1个桶中:将每个元素x[i] 分配到某个桶(编号为index),其中(这括号里多了个“+”),并求出分到每个桶的最大最小数据。
  4. 最大间隙:除最大最小数据max和min以外的n-2个数据放入n-1个桶中,由抽屉原理可知至少有一个桶是空的,又因为每个桶的大小相同,所以最大间隙不会在同一桶中出现,一定是某个桶的上界和气候某个桶的下界之间隙,且该量筒之间的桶(即便好在该连个便好之间的桶)一定是空桶。也就是说,最大间隙在桶i的上界和桶j的下界之间产生j>=i+1。一遍扫描即可完成。

并查集

经典例题:16

TopK问题(注重代码实现)

经典例题:12

100w个数中找出最大的100个数。

方案1:采用局部淘汰法。选取前100个元素,并排序,记为序列L。然后一次扫描剩余的元素x,与排好序的100个元素中最小的元素比,如果比这个最小的要大,那么把这个最小的元素删除,并把x利用插入排序的思想,插入到序列L中。依次循环,知道扫描了所有的元素。复杂度为O(100w*100)。 方案2:采用快速排序的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。复杂度为O(100w100)。 方案3:在前面的题中,我们已经提到了,用一个含100个元素的最小堆完成。复杂度为O(100wlg100)。

字典树Tire树

经典例题:3.9.10

有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。 方案1:顺序读文件中,对于每个词x,取,然后按照该值存到5000个小文件(记为)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。

求中位数

经典例题:14

一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数中的中数? 方案1:先大体估计一下这些数的范围,比如这里假设这些数都是32位无符号整数(共有232个)。我们把0到232-1的整数划分为N个范围段,每个段包含(232)/N个整数。比如,第一个段位0到232/N-1,第二段为(232)/N到(232)/N-1,…,第N个段为(232)(N-1)/N到232-1。然后,扫描每个机器上的N个数,把属于第一个区段的数放到第一个机器上,属于第二个区段的数放到第二个机器上,…,属于第N个区段的数放到第N个机器上。注意这个过程每个机器上存储的数应该是O(N)的。下面我们依次统计每个机器上数的个数,一次累加,直到找到第k个机器,在该机器上累加的数大于或等于(N2)/2,而在第k-1个机器上的累加数小于(N2)/2,并把这个数记为x。那么我们要找的中位数在第k个机器中,排在第(N2)/2-x位。然后我们对第k个机器的数排序,并找出第(N2)/2-x个数,即为所求的中位数的复杂度是O(N^2)的。 方案2:先对每台机器上的数进行排序。排好序后,我们采用归并排序的思想,将这N个机器上的数归并起来得到最终的排序。找到第(N2)/2个便是所求。复杂度是O(N2*lgN^2)的。

补充题目:在10G的数据中找出中位数

不妨假设10G个整数是64bit的。 2G内存可以存放256M个64bit整数。 我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后,我们便知道中数在那个范围内出现,以及这个范围内总共出现了多少个整数。 如果中数所在范围出现的整数比较少,我们就可以对这个范围内的整数进行排序,找到中数。如果这个范围内出现的整数比较多,我们还可以采用同样的方法将此范围再次分成多个更小的范围(256M=2^28,所以最多需要3次就可以将此范围缩小到1,也就找到了中数)。

补充的知识:

AVL树 最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了avl树。

红黑树 平衡二叉树,广泛用在c++的stl中。如map和set都是用红黑树实现的。

b/b+树 用在磁盘文件组织 数据索引和数据库索引。

trie树(字典树): 用在统计和排序大量字符串,如自动机。

参考:

http://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html

https://blog.csdn.net/hihozoo/article/details/51248823 (里面Trie树的应用写的很好)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【JAVA】java字符串拼接

    后端技术漫谈
  • [Leetcode][python]Integer to Roman

    I = 1; V = 5; X = 10; L = 50; C = 100; D = 500; M = 1000;

    后端技术漫谈
  • [Leetcode][python]Valid Palindrome/验证回文串

    判断一个字符串是否是回文字符串,只考虑字母和数字,并且忽略大小写。 注意点: 空字符串在这里也定义为回文串

    后端技术漫谈
  • gps卫星信号模拟器如何gps信号

    SYN5203型GPS模拟器能够精确、无误的模拟出GPS卫星导航授时信息,通过自身可发出定位授时信息,支持实时星历和外部星历参数输入,能满足各类GPS导航仪终端...

    时频专家
  • 摩托被谷歌榨干遭抛弃 烂脑娃(联想lenovo)花29亿拣到了宝石还是垃圾

    联想一周内花费52亿美金,收购IBM和摩托罗拉,为了巩固其移动业务的市场地位,以29亿美金收购摩托残渣,有网友说联想真的可以跟陈光标划等号了,每一次收购都是别人...

    人称T客
  • linux的简单介绍以及常用简单命令

    例如:需要让张三同学帮忙去楼下小卖铺买一瓶农夫山泉水和清风餐巾纸,在这个指令中“买东西”是指令的主体,买的水和餐巾纸是操作的对象,农夫山泉、清风是操作的选项。|

    踏浪
  • 在 P2P 文件分享应用以文件或文件段为单位的优缺

    在我用了好几个 P2P 文件分享应用之后,我对比了多个应用对资源的处理,可以看到基本上可以分为文件夹级的、文件级的和文件里面的一段段级的。本文将会告诉大家使用不...

    林德熙
  • 天天酷跑破解版制作教程

    用户1127987
  • Linux实战--删除符合要求的文件

    因为从一些源码网站下载了一些源码,很好用,但就是广告太多,很烦人,但是人家网站生存也不容易,都要养家啊,况且让免费用源码已经很不错了!

    浩Coding
  • 厉害了!Python+matplotlib制作8个排序算法的动画

    深刻研究排序算法是入门算法较为好的一种方法,现在还记得4年前手动实现常见8种排序算法,通过随机生成一些数据,逐个校验代码实现的排序过程是否与预期的一致,越做越有...

    double

扫码关注云+社区

领取腾讯云代金券