Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 面试 » 

面试中的大数据处理

海量数据处理是面试过程及实际工作经常遇到的一大类,特别是在如今大数据风起云涌的互联网时代。因为数据量太大,对CPU和内存等系统资源要求太高,时间花费太长,需要有特殊的算法和数据结构进行处理。
这里总结下学习过程中的笔记,主要参考自July博客

一 哈希+分治

如果数据量太大,不能全部导入内存,可以使用一个哈希算法,把大数据映射成若干个小数据,然后小数据可以全部导入内存进行处理,最后把每个小数据处理之后的结果进行合并,得到最终的结果。这个是处理这类问题的通用方法,具有很广泛的使用范围。

1. 两个文件各有50亿个url,每个url各64字节,内存限制是4G,找出其中共同的url。

一个文件占用内存大小为5G x 64B = 320GB,远大于实际内存4GB,不能一次性导入。

把每个文件中的url进行哈希hash(url)%1000,各得到1000个小文件,每个大约300MB。

哈希具有一个性质,哈希值相同的url不一定相同,但相同的url哈希之后的结果必定相同。

于是只需逐个分析两个文件的1000个小文件中对应小文件的的结果,然后合并结果即可。具体可以把一个小文件的url放进hash_set里,然后看另一个小文件的url在不在这个hash_set里。

2. 海量日志数据,提取出某日访问百度次数最多的那个IP。

IP只有32位,最多有2^32个,采用哈希hash(IP)%1000映射到1000个桶里,对每个桶里的找出次数最多的IP及其频率,具体可以使用hash_map进行统计再求最大,然后再把1000个结果合并找出最终次数最多的。

3. 有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

将所有查询进行哈希hash(query)%10,映射成新的10个文件,大约每个1GB。对每个文件使用hash_map统计频率,使用快速/归并排序进行排序。最后把10个排序结果归并得到最终排序结果。

二 布隆过滤器(Bloom Filter)/位图(Bit Map)

每个元素用1位(或k位)表示,首先把元素哈希成一个整数(本身是整数则不用哈希),然后把该整数对应的位置为1。查找时如果发现一个元素哈希之后的位置上为1,说明该元素已经存在,这个可以方便地判断数据是否重复或集合求交并。

但是这个实现不支持元素删除,因为可能多个元素可能映射到同一个整数,一个改进是用一个整数表示出现的次数,而不是只用01表示。

4. 两个文件各有50亿个url,每个url各64字节,内存限制是4G,找出其中共同的url。

一个url占一位,4G内存可以表示340亿位,把第一个文件的每个url哈希映射成这340亿中的某个并置为1,然后查找另一个文件的url哈希值对于的bit位是否为1即可。

5. 已有40亿个不重复且无序的unsigned int整数,快速判断一个给定数是否在这40亿个数当中。

无符号int整数共有2^32个,每个占一位,需要2^32b内存,申请512MB内存即可。把40亿个数对应的bit位置1,再判断待查数的bit位是否为1。

6. 2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。

不像上题,这里数字有重复,每个数字需要占两位,00表示不存在,01表示出现1次,10表示出现多次,申请1GB内存即可。逐个读入所有整数,设置对应的bit位,00变01,01变10,10不变,再扫描找出bit位为01的数字即可。

如果内存不够,可以先使用哈希+分治方法分成若干个小数据集,再使用位图方法统计。

三 堆

堆可以方便维护一堆数据的前n小(或大)的元素,使用大根堆,先把前n个直接入堆,后面的先跟堆顶的最大元素比较,如果比最大的还大,那肯定不是前n小的。否则就替换掉堆顶数字,再调整堆。最后得到的n个就是前n小的元素。求前n小用大根堆,前n大用小根堆。另外使用大根堆跟小根堆结合可以维护中位数。

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

维护一个100个元素的最小堆即可。

或者直接维护一个用来存储当前最大的100个数的数组,每次把新来的数丢弃或插入到合适的位置。

8. 海量数据分布在100台电脑中,统计出这批数据的TOP10。

在每台电脑上维护一个10个元素的小根堆求出每台电脑的TOP10,然后再综合起来得到最终的结果。

9. 上千万或上亿数据(有重复),统计其中出现次数最多的前N个数据。

先采用hash_map/搜索二叉树/红黑树等来进行统计次数,然后再利用N个元素的堆统计次数最多的前N个数据。

四 字典树(trie树)

字典树特别适合处理字符串相关的问题(整数也可以看出是特殊的字符串)。字典树就是把字符串的每个字符组成一个节点,然后不同字符串的相同的前缀部分可以共享相同的节点,方便后续的查找。其中根节点不包含字符,除根节点外每一个节点都只包含一个字符。从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。

10. 1000万字符串,把其中重复的去掉,保留没有重复的字符串。

对所有字符串建立字典树,记录字符串是否出现的信息,统计最终的所有字符串即可。

11. 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词。

对所有单词建立字典树(复杂度O(n*avgLen)),记录每个单词出现的次数,最后使用上述的堆方法统计出现次数最多的前10个单词(复杂度O(n*lg10))。

12. 一个文本文件,找出前10个经常出现的词,但这次文件比较长,说是上亿行或十亿行,总之无法一次读入内存。

使用哈希+分治方法把文件分成若干个小文件,对每个小文件可以使用上述方法统计出前10个最常出现的单词,然后归并所有的小文件结果得到最终结果。

13. 1000万个查询,每个查询串的长度为1-255字节,不重复的查询不超过3百万个,统计最热门的10个查询串,要求使用的内存不能超过1G。

对所有查询字符串建立字典树,记录该查询出现的次数,然后使用10个元素的最小堆统计出现次数最多的前10个。

五 其他

数据库查找

数据量太大时,如果时间允许,可以将其导入数据库,利用数据库建立的索引和SQL语句进行增删改查操作。

反向索引(Inverted index)

给大量的文本建立索引,对每个单词,记录它出现的文本的ID。查询是只需根据记录的索引的内容即可找到对应的文本。

分布式计算

如用Hadoop完成的MapReduce,将大量的工作使用map分解到不同的机器上,再将每个机器的结果使用reduce合并得到最终结果。充分利用多个机器的计算资源,提高程序的运行效率,比如经典的word count函数。

在一些复杂的程序中,可能需要使用多个mapreduce。

外部排序

外部排序指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

常见的是归并排序,将原文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行归并排序。

外排序使用磁盘辅助进行排序,使得能够支持大数据的排序,但需要进行大量的IO操作,影响效率。

上一篇: 下一篇:
  1. 哦,明白了。应该是这样的
    if(hash(url)%1000==1){
    写该url到小文件1
    }else if(hash(url)%1000==2){
    写该url到小文件2
    }…


    else{
    写该url到小文件1000
    }

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论