文档章节

海量数据处理算法(top K问题)

fengsehng
 fengsehng
发布于 2016/11/09 09:07
字数 311
阅读 3
收藏 0
点赞 0
评论 0

举例

有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

思路

  • 首先把文件分开
  • 针对每个文件hash遍历,统计每个词语的频率
  • 使用堆进行遍历
  • 把堆归并起来

具体的方案

1.分治:
顺序读文件中,对于每个词c,取hash(c)%2000,然后按照该值存到2000个小文件中。这样每个文件大概是500k左右。

注意:

如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,直到分解得到的小文件的大小都不超过1M。

2.hash遍历:
对每个小文件,用hash的方式统计每个文件中出现的词以及相应的频率

3.堆遍历:
用 最小堆取出出现频率最大的100个词,并把100个词及相应的频率存入文件,这样又得到了5000个文件。

4.归并整合

下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。

本文转载自:http://blog.csdn.net/lpjishu/article/details/52626891

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
万变不离其宗之海量数据下的算法问题处理思路

本文介绍 万变不离其宗之海量数据下的算法问题处理思路 万变不离其宗之海量数据下的算法问题处理思路 本文由在当地较为英俊的男子金天大神原创,版权所有,欢迎转载,但请保留这段版权信息,...

Nicholas_Jela ⋅ 2017/09/06 ⋅ 0

机器学习笔记四:K-Means算法

一、无监督学习介绍: 在K均值算法是一种典型的无监督学习算法,在介绍K均值算法之前,我们先介绍什么是无监督学习,它着重于发现数据本身的特点。无监督学习不需要对数据进行标记,它的作用...

xckkcxxck ⋅ 04/13 ⋅ 0

99%海量数据处理

http://blog.csdn.net/vjulyv/article/details/7382693 前言 一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,...

tantexian ⋅ 01/15 ⋅ 0

“NoHadoop”?——新一代海量数据架构分析

在经历了长达25年的统治地位后,关系型数据库正面临越来越火的“NoSQL”挑战,而挑战者是以Hadoop为代表的分布式计算开源架构。可以看到, 越来越多的消息表明,不管NoSQL是被解释为“No SQ...

ddatsh ⋅ 2011/09/22 ⋅ 1

从海量数据中提取TopK过程模拟

在工作面试中,经常会出现考察海量数据处理的问题:给你若干个数,从其中找到出现次数最多的K个数据。 (百度面试题中,有N多IP地址,让你找访问量TopK的IP) 解决方法 1. 有大量重复数据 如...

西昆仑 ⋅ 2012/08/22 ⋅ 8

Bloom-Filter (布隆过滤器)

我们今天学习一种海量数据的查询过滤算法,就是判断一个元素是否在一个集合中,我们平常的算法,肯定就是遍历比较了,这样对小量数据可以,但对海量数据肯定是不适用的,就算是二叉树其时间复...

ttblack ⋅ 02/06 ⋅ 0

过亿海量数据处理分析

笔者在实际工作中,有幸接触到海量的数据处理问题,对其进行处理是一项艰巨而复杂的任务。原因有以下几个方面: 一、数据量过大,数据中什么情况都可能存在。如果说有10条数据,那么大不了每...

Zhao-Qian ⋅ 2012/08/20 ⋅ 0

寻找最大的K个数,Top K问题的堆实现

前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。 先拿100...

天天顺利 ⋅ 05/18 ⋅ 0

10亿个数中找出最大的10000个数(top K问题)

这个问题还是建立最小堆比较好一些。 先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,...

一贱书生 ⋅ 2016/11/28 ⋅ 0

海量数据处理算法

1. Bloom Filter 【Bloom Filter】 Bloom Filter(BF)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。它是一个判断元素是否存在...

cloves ⋅ 2017/04/21 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周日乱弹 —— 这么好的姑娘都不要了啊

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @TigaPile :分享曾惜的单曲《讲真的》 《讲真的》- 曾惜 手机党少年们想听歌,请使劲儿戳(这里) @首席搬砖工程师 :怎样约女孩子出来吃饭,...

小小编辑 ⋅ 14分钟前 ⋅ 1

Jenkins实践3 之脚本

#!/bin/sh# export PROJ_PATH=项目路径# export TOMCAT_PATH=tomcat路径killTomcat(){pid=`ps -ef | grep tomcat | grep java|awk '{print $2}'`echo "tom...

晨猫 ⋅ 今天 ⋅ 0

Spring Bean的生命周期

前言 Spring Bean 的生命周期在整个 Spring 中占有很重要的位置,掌握这些可以加深对 Spring 的理解。 首先看下生命周期图: 再谈生命周期之前有一点需要先明确: Spring 只帮我们管理单例模...

素雷 ⋅ 今天 ⋅ 0

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部