文档章节

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

fengsehng
 fengsehng
发布于 2016/11/09 09:07
字数 311
阅读 3
收藏 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
0
99%海量数据处理

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

tantexian
01/15
0
0
“NoHadoop”?——新一代海量数据架构分析

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

ddatsh
2011/09/22
1K
1
海量数据处理 - 教你如何迅速秒杀掉:99%的海量数据处理面试题

一般而言,标题含有“秒杀”,“99%”,“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌,但进一步来讲,如果读者读罢此文,却无任何收获,那么,我也甘愿背负这样的罪名 :-),同时,此文...

小王穷遊
09/02
0
0
机器学习笔记四:K-Means算法

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

xckkcxxck
04/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Range Sum Query - Immutable(leetcode303)

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example: Given nums = [-2, 0, 3, -5, 2, -1]sumRange(0, 2) -> 1sumRa......

woshixin
6分钟前
0
0
「阿里面试系列」面试加分项,从jvm层面了解线程的启动和停止

线程的启动的实现原理 线程停止的实现原理分析 为什么中断线程会抛出InterruptedException 线程的启动原理 前面我们简单分析过了线程的使用,通过调用线程的start方法来启动线程,线程启动后...

James-
13分钟前
0
0
转换 bytes 为 kb/mb/gb/tb/pb…

智能转换 bytes 为 kb/mb/gb/tb/pb… 用到了 math 模块中的一些函数 #!/usr/bin/env python# -*- coding: utf-8 -*-"""智能转换 bytes 为 kb/mb/gb/tb/pb..."""import mathdef conv...

郭恩洲_OSC博客
20分钟前
3
0
Mysql导出sql语句的方法及可能遇到的mysqldump: command not found

解决办法: 打开terminal    输入vi ~/.bash_profile    添加如下三行代码:    #mysql  PATH=$PATH:/usr/local/mysql/bin  export    保存并退出...

Liens
21分钟前
1
0
一文读懂,深入浅出 RPC框架

RPC 功能目标 RPC 的主要功能目标是让构建分布式计算(应用)更容易,在提供强大的远程调用能力时不损失本地调用的语义简洁性。为实现该目标,RPC 框架需提供一种透明调用机制让使用者不必显...

别打我会飞
22分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部