大数据中找上中位数的方法

题目:

40亿 大整数,组成了一个大文件。
想找到其中的 上中位数该怎么办?
内存:10MB,怎么办?
内存:20K,怎么办?
内存:有限几个字符,怎么办?
条件:按行读取文件,读取操作不占用内存。

应该具备的能力:
2^k = ? 应该都能够熟记,达到反射性反应的程度。
字节数 对应计算机中的 容量(T, G, M, K)

内存只有 10MB 的情况
接下来我们来解题:
看到大数据容量限制的,首先想到的是从范围入手。
1. 数据是 有符号? / 无符号?
2. 我们知道一个 4字节的无符号整数 范围为:0~42亿
那么我们可以用一个 unsigned int 来表示一个数出现的次数
(一个数最多出现 40亿 次,故能够表示,不会溢出)
3. 我们来计算 10MB 内存可以存几个 unsigned int 的数。 => 250万
因此我们知道 10MB 内存足够我们在 250W 范围内进行 精细的词频统计(每个数出现几次)
4. 0~42亿 内总共有 1680个 250W 范围的段。因此我们将 42亿 的范围按照 250W 进行分段。([0, 250w), [250w,500w)...)
建立一个 1680 的数组,遍历大文件一次,来统计每个段中出现数的个数。
count[i] 就表示在第 i 段的 连续的250W 的范围内,出现了多少个数。
比如:一个数字值为10亿,那么它应该就在 count[400] 这个段中,那么进行操作 count[400]++ 即可。
5. 对 count 进行累加,直到 sum >= 20亿。这样我们就能确定第 20亿 个数是来自哪个范围的。
6. 释放该数组,再次遍历大文件,利用 10MB 的空间对该范围内的数进行 精细的词频统计。这样便能够找到中位数了。
由此可见,以上做法是借用了 桶排序 的思想。

总结:
1. 利用限制的范围计算出我们能够在多大的范围内进行 精细的词频统计。
2. 利用 精细的范围 对整体范围进行划分,建立一个粗略的统计数组。
3. 遍历大文件,找出中位数粗略的范围。
4. 对该粗略的范围进行精细的统计。

内存只有 20K 的情况:
我们依然用上面的方法来分析:
20K 的内存可以支持 5000范围大小 的精细词频统计。
然后我们用 40亿 / 5000 => 发现该数值已经怨愿你大于 5000 了,我们根本无法进行粗略范围的统计。
于是,我们不妨逆过来思考。
直接从 粗略的范围 出发进行统计。将其分成 5000 份。
我们依然能够得知 中位数 是在哪个部分。然后看该范围能否被精细统计。
若不能一直循环下去。

内存只有 有限几个字符 的情况(比如就8个字节,两个变量):
采用二分的方法。最多二分 32 次,即需要读 32 次文件。
1. 首先对 0~42 亿二分(注意是对整个范围进行二分),用一个变量 k 记下当前的值是多少。
遍历文件一边遍,计算当前小于当前值得数据个数 n。
2. 若 n < 21亿,该数在小半部分。若 n > 21亿,该数在大部分。
以此循环下去。

时间: 09-14

大数据中找上中位数的方法的相关文章

数据挖掘在大数据中的应用综述

*** (上海海事大学 上海 201306) 摘 要: 面对大规模多源异构的数据,数据挖掘的方法不断的得到改善与发展,同时对于数据挖掘体系的完善也提出了新的挑战.针对当前数据挖掘在大数据方面的应用,本文从数据挖掘的各个阶段进行了方法论的总结及应用,主要包括数据准备的方法.数据探索的方法.关联规则方法.数据回归方法.数据分类方法.数据聚类方法.数据预测方法和数据诊断方法.最后还指出类数据挖掘在鲁棒性表达方面的进一步研究. 关键词: 数据挖掘;方法论;大数据;鲁棒性 Application of D

因素空间理论在大数据中的应用——汪培庄

因素空间理论在大数据中的应用 汪培庄 辽宁工程技术大学 (在大数据与数据科学进展主题论坛上的发言稿,经过整理) 我国数据与机器智能科学工作者肩负着引领大数据时代浪潮的重任,这是关乎我们能否顺利实现中国梦的大事.无论多困难,我们一定要争取走向前列.作为在信息革命领域里头曾经撕杀过的一名老兵,我曾经打造一个理论,就等这一天来接受新的考验,这个理论就是因素空间.       一.因素空间的历史贡献   87年7月,日本学者山川烈在东京召开的国际模糊系统大会展厅里摆着一台机器,明确写着FUZZY COM

亚马逊大数据云会议上遗漏的一件事

每当亚马逊云计算AWS有重大的媒体或者客户事件的时候,公司通常会宣布一个重要内容:降价. 但是实际情况似乎并不是这样的,在本月初洛杉矶举办的公司第三届大数据云会议上,会发生什么事情呢?云计算市场的价格会保持稳定吗?亚马逊云计算AWS试图掀起与其他云服务提供商在价格上的竞争吗? 我们曾经询问过亚马逊云计算AWS, 并没有得到回应.但据分析人士说,虽然价格很重要,但是它并不能完全决定人们是否选择使用云. 大约一年前, 在IaaS云计算市场的价格之争期间.亚马逊云计算AWS似乎每周都会有降价.谷歌也跟

大数据量的话可以有以下方法

大数据量的话可以有以下方法: 1.数据库分表 2.数据库分区 3.是用缓存 4.用lucene处理 5.分时处理 不关EF什么事情,当然这是基本的处理方法,高级的处理方法就复杂点,不过百万级的数据,上面那些方法就够了

错误: 在类 com.zs.container.CollectionData 中找不到主方法, 请将主方法定义为: public static void main(String[] args)

错误: 在类 com.zs.container.CollectionData 中找不到主方法, 请将主方法定义为: public static void main(String[] args) package com.zs.container; import java.util.ArrayList; import com.java.array.generator.CountingGenerator.String; import com.java.array.generator.CountingG

Spark2.0从入门到精通:Scala编程、大数据开发、上百个实战案例、内核源码深度剖析视频教程

38套大数据,云计算,架构,数据分析师,Hadoop,Spark,Storm,Kafka,人工智能,机器学习,深度学习,项目实战视频教程 视频课程包含: 38套大数据和人工智能精品高级课包含:大数据,云计算,架构,数据挖掘实战,实时推荐系统实战,电视收视率项目实战,实时流统计项目实战,离线电商分析项目实战,Spark大型项目实战用户分析,智能客户系统项目实战,Linux基础,Hadoop,Spark,Storm,Docker,Mapreduce,Kafka,Flume,OpenStack,Hiv

迈向大数据架构师 - 架构师转型方法与架构设计理论

迈向大数据架构师 - 架构师转型方法与架构设计理论课程学习地址:http://www.xuetuwuyou.com/course/233课程出自学途无忧网:http://www.xuetuwuyou.com课程摘自<大数据系统架构分析师成长之路>:http://www.xuetuwuyou.com/course/200 1.课程目标通过本课程的学习,让学员了解到什么是系统架构师,什么大数据系统架构师,两者的区别与联系,程序员与架构师的不同,程序员如何向架构师转型,一个架构师工作日常及必须修炼的

错误: 在类 Main 中找不到 main 方法, 请将 main 方法定义为: public static void main(String[] args) 否则 JavaFX 应用程序类必须扩展javafx.application.Application

错误: 在类 Main 中找不到 main 方法, 请将 main 方法定义为: public static void main(String[] args)否则 JavaFX 应用程序类必须扩展javafx.application.Application 出现这种错误的原因其中一种就是 导包时错把其他的String包导入,以至于找不到main(String[ ]  args) 原文地址:https://www.cnblogs.com/mibloom/p/9497357.html

从大数据菜鸟走上大师的历程

大数据是用scala语言,和java有些不同又比java强大,省去了很多繁琐的东西,scala中的的接口用trait来定义,不同于java的接口,trait中可以有抽象方法也可以有不抽象方法.scala中的方法中还可以定义方法,这在java中是从来没有的. 大数据未来几年发展的重点方向,大数据战略已经在十八届五中全会上作为重点战略方向,中国在大数据方面才刚刚起步,但是在美国已经产生了上千亿的市场价值.举个例子,美国通用公司是一个生产飞机发动机的一个公司,这家公司在飞机发动机的每一个零部件上都安装