UDN-企业互联网技术人气社区

板块导航

浏览  : 1496
回复  : 0

[面试相关] 处理海量数据的主要过程是什么?

[复制链接]
很黄很暴力的头像 楼主
发表于 2015-6-1 11:46:53 | 显示全部楼层 |阅读模式
1. 分而治之/hash映射 + hash统计 + 堆/快速/归并排序;就是先映射,而后统计,最后排序:
  • 分而治之/hash映射:针对数据太大,内存受限,只能是:把大文件化成(取模映射)小文件,即16字方针:大而化小,各个击破,缩小规模,逐个解决
  • hash_map统计:当大文件转化了小文件,那么我们便可以采用常规的hash_map(ip,value)来进行频率统计。
  • 堆/快速排序:统计完了之后,便进行排序(可采取堆排序),得到次数最多的IP。

    2. 双层桶划分
    双层桶划分—-其实本质上还是分而治之的思想,重在“分”的技巧上!
    适用范围:第k大,中位数,不重复或重复的数字
    基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接受的范围内进行。可以通过多次缩小,双层只是一个例子。
    3. Bloom filter/Bitmap;
    适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集
    基本原理及要点:
    对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。
    还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
    4. Trie树/数据库/倒排索引;
    适用范围:数据量大,重复多,但是数据种类小可以放入内存
    基本原理及要点:实现方式,节点孩子的表示方式
    扩展:压缩实现。
    5. 外排序;
    适用范围:大数据的排序,去重
    基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树
    6. 分布式处理之Hadoop/Mapreduce。
    MapReduce是一种计算模型,简单的说就是将大批量的工作(数据)分解(MAP)执行,然后再将结果合并成最终结果(REDUCE)。这样做的好处是可以在任务被分解后,可以通过大量机器进行并行计算,减少整个操作的时间。但如果你要我再通俗点介绍,那么,说白了,Mapreduce的原理就是一个归并排序。
    适用范围:数据量大,但是数据种类小可以放入内存
    基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。
  • 您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    关于我们
    联系我们
    • 电话:010-86393388
    • 邮件:udn@yonyou.com
    • 地址:北京市海淀区北清路68号
    移动客户端下载
    关注我们
    • 微信公众号:yonyouudn
    • 扫描右侧二维码关注我们
    • 专注企业互联网的技术社区
    版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
    快速回复 返回列表 返回顶部