哈希表的使用场景--大数据中的前k大

标签: 哈希表 大数据 | 发表时间:2013-10-20 18:27 | 作者:yusiguyuan
出处:http://blog.csdn.net

    今年看到学长面试的时候,还是会问到一下基本的算法问题,在这之前对于这些还是有一定的理解,只是不能很透彻的清楚其中的原理、奥妙,在这之前也转载过关于hash表使用的文章,成这个星期天,想从头到尾把一个问题搞清楚,现在觉得这个越来越重要了,抓住一段时间,搞清楚一个问题,比泛泛的知道很多更加实在,尤其是在读书的时候更是这样,在这段时间里,自己也看了不少书,但是回头一想,还是什么都没明白,到不如在某一块上非常清楚,逐个击破!!!下面就以一个网上很常见的面试题作为分析对象:

    一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右

    分析:

    本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词。

1)词频统计

    词频统计,我们很自然的会想到使用hash。但是直接hash内存是放不下的啊…怎么办?其实对于有限内存下的大文件处理,都可总结为归并的思想,不过要注意归并时的分段亦是有学问的。请比较归并a与归并b方法

  • 归并a:将数据分为5段,分别对每段在内存中hash统计并将统计结果写入文件,然后合并分段的hash。

    问题:表面看来不错的主意,实则有很大问题,稍微想一下,a方法存在一个主要的困难就是,hash合并的时候相当于同时在5个文件中判断是否有相同的词,要这样做会非常繁琐。

    怎么解决呢?我当时是受编程珠玑中第一题(排序一千万个32位整数)启发的,它在归并分段的时候,不是直接的简单分段,而是每段取一个范围比如第一段取0~249000之间的数,这样有什么好处?将来的各段数彼此间是没有交集(重复)的。所以我们的思想就是要让这10G的关键词分段后各小段没有交集,这样hash合并就没有问题了。请看归并b

  • 归并b:将数据分为5段,分段时 对每个词hash,hash值在一个范围中的词语分到一个段中,然后对于每个分段统计的hash结果直接都写入一个文件即可。

    分析:使用hash分段,保证各小段没有重复的词。我当时想的方法是将词语的首字拼音打头一样的分在一段中,例如“五谷丰登”、“万箭齐发”分到一起,都是w打头的拼音,其实这仅仅只是hash的一种。


作者:yusiguyuan 发表于2013-10-20 10:27:19 原文链接
阅读:0 评论:0 查看评论

相关 [哈希表 大数据] 推荐:

哈希表的使用场景--大数据中的前k大

- - CSDN博客推荐文章
下面就以一个网上很常见的面试题作为分析对象:.     一个10G的关键词的log,找出词频最高的前K个词,设可用内存为2G左右.     本题的难点主要有两处,一是如何在有限内存下对大文件进行词频统计;二是如何在有限内存的下找出词频的前K大个词.     词频统计,我们很自然的会想到使用hash.

谈大数据(2)

- - 人月神话的BLOG
对于大数据,后面会作为一个系列来谈,大数据涉及的方面特别多,包括主数据,数据中心和ODS,SOA,云计算,业务BI等很多方面的内容. 前面看到一个提法,即大数据会让我们更加关注业务方面的内容,而云平台则更多是技术层面的内容. 对于大数据会先把各个理解的关键点谈完了,再系统来看大数据的完整解决方案和体系化.

大数据之惑

- - 互联网分析
算起来,接触大数据、和互联网之外的客户谈大数据也有快2年了. 也该是时候整理下一些感受,和大家分享下我看到的国内大数据应用的一些困惑了. 云和大数据,应该是近几年IT炒的最热的两个话题了. 在我看来,这两者之间的不同就是: 云是做新的瓶,装旧的酒; 大数据是找合适的瓶,酿新的酒. 云说到底是一种基础架构的革命.

白话大数据

- - 互联网分析
这个时代,你在外面混,无论是技术还是产品还是运营还是商务,如果嘴里说不出“大数据”“云存储”“云计算”,真不好意思在同行面前抬头. 是千万级别的用户信息还是动辄XXXTB的数据量. 其实,大数据在我的眼里,不是一门技术,而是一种技能,从数据中去发现价值挖掘价值的技能. ”当我掷地有声用这句话开场时,正好一个妹子推门而入,听到这句话,微微一怔,低头坐下.

交通大数据

- - 人月神话的BLOG
本文简单谈下智慧交通场景下可能出现的大数据需求和具体应用价值. 对于公交线路规划和设计是一个大数据潜在的应用场景,传统的公交线路规划往往需要在前期投入大量的人力进行OD调查和数据收集. 特别是在公交卡普及后可以看到,对于OD流量数据完全可以从公交一卡通中采集到相关的交通流量和流向数据,包括同一张卡每天的行走路线和换乘次数等详细信息.

全球10大数据库

- - 译言-电脑/网络/数码科技
原文: Fiorenttini   译者: julie20098. [非商业性转载必须注明译者julie20098和相关链接. ,否则视为侵权,追究转载责任. 世界气候数据中心:气候全球数据中心, 220TB 的网络数据, 6PB 的其它数据. 国家能源研究科学计算中心,有 2.8PB 容量.

谈大数据分析

- - 人月神话的BLOG
对于数据分析层,我们可以看到,其核心重点是针对海量数据形成一个分布式可弹性伸缩的,高查询性能的,支持标准sql语法的一个ODS库. 我们看到对于Hive,impala,InfoBright更多的都是解决这个层面的问题,即解决数据采集问题,解决采集后数据行列混合存储和压缩的问题,然后形成一个支撑标准sql预防的数据分析库.

大数据的一致性

- - 阳振坤的博客
看到了一篇关于数据一致性的文章:下一代NoSQL:最终一致性的末日. (  http://www.csdn.net/article/2013-11-07/2817420 ),其中说到: 相比关系型数据库,NoSQL解决方案提供了shared-nothing、容错和可扩展的分布式架构等特性,同时也放弃了关系型数据库的强数据一致性和隔离性,美其名曰:“最终一致性”.

大数据Lambda架构

- - CSDN博客云计算推荐文章
1 Lambda架构介绍.          Lambda架构划分为三层,分别是批处理层,服务层,和加速层. 最终实现的效果,可以使用下面的表达式来说明. 1.1 批处理层(Batch Layer, Apache Hadoop).          批处理层主用由Hadoop来实现,负责数据的存储和产生任意的视图数据.

大数据公司Amazon

- - 36氪 | 关注互联网创业
说到 Amazon,它通常给人的印象是一家典型的电商公司——创办于1995年,靠在线书籍销售业务起家,发展至今也已颇具规模. 近日,TechCrunch作者Alex Williams撰文称,Amazon其实并非一家贸易公司,而是一家大数据公司. 联想到Amazon CEO Jeff Bezos曾说过的一句话:“企业家应该愿意在很长一段时间内承受误解的目光.