大数据排序

BichonCode 等级 579 0 0

一、 如何给100亿个数字进行排序?

1.1 解答:

1.把这个37GB的大文件,用哈希分成1000个小文件,每个小文件平均38MB左右(理想情况),把100亿个数字对1000取模,模出来的结果在0到999之间,每个结果对应一个文件,所以我这里取的哈希函数是 h = x % 1000,哈希函数取得"好",能使冲突减小,结果分布均匀。 2.拆分完了之后,得到一些几十MB的小文件,那么就可以放进内存里排序了,可以用快速排序,归并排序,堆排序等等。 3.1000个小文件内部排好序之后,就要把这些内部有序的小文件,合并成一个大的文件,可以用二叉堆来做1000路合并的操作,每个小文件是一路,合并后的大文件仍然有序。

  • 首先遍历1000个文件,每个文件里面取第一个数字,组成 (数字, 文件号) 这样的组合加入到堆里(假设是从小到大排序,用小顶堆),遍历完后堆里有1000个 (数字,文件号) 这样的元素
  • 然后不断从堆顶拿元素出来,每拿出一个元素,把它的文件号读取出来,然后去对应的文件里,加一个元素进入堆,直到那个文件被读取完。拿出来的元素当然追加到最终结果的文件里。
  • 按照上面的操作,直到堆被取空了,此时最终结果文件里的全部数字就是有序的了。
1.2 附加:如何拆分大文件?
  • 一个32G的大文件,用fopen()打开不会全部加载到内存的,然后for循环遍历啊,把每个数字对1000取模,会得到0到999种结果,然后每种结果在写入到新的文件中,就拆分了
1.3 思维拓展
  • 类似的100亿个数字求和,求中位数,求平均数,套路就是一样的了。
  • 求和:统计每个小文件的和,返回给master再求和就可以了。
  • 求平均数:上面能求和了,再除以100亿就是平均数了
  • 求中位数:在排序的基础上,遍历到中间的那个数就是中位数了。

二、常见的排序算法的复杂度

大数据排序

收藏
评论区

相关推荐

【夜读】能成大事的人,都有大格局
1    前段时间,我下楼买烧饼。到了烧饼店门口才发现,前面已经排了很长的队。    轮到我时,面前的烧饼筐里刚好有四个,我撑起袋子准备装,老板娘却说:“这个我们先不卖。”我有些不解地问她:“为什么呀?”她解释道:“这是最开始烙的,现在已经凉了。”说话间,新烙的饼已经出炉,老板娘给我挑了四个外焦里嫩的烧饼。之前那四个,被她放到了一边。    这让我想起
同学,你这简历上没项目啊!
大家好,我是小五 同学,刚毕业或者转行去求职数据分析师的时候,你遭遇过这样的尴尬怪圈吗? (https://imghelloworld.osscnbei
MySql 查询重复数大于1的数据(HAVING的使用)
在数据增加的过程中,因为某些原因,会产生重复数据,此时我们要看哪些数据重复了。 举栗: 要操作的表为test 主键id 需要排重的字段为field1,field2,field3,field4 SQL语句为 SELECT , count(id) FROM sysuser_user_pointlog_online_bak GROUP B
同学,你这简历上没项目啊!
作者:朱小五 大家好,我是小五 同学,刚毕业或者转行去求职数据分析师的时候,你遭遇过这样的尴尬怪圈吗?比方说下面的jd就很真实:今天小五就跟大家聊聊,面试数据分析师时,如何彻底摆脱拿着单薄的简历与面试官尬聊的场景,关键词就是——工作经验!别慌,不是让你瞎编。没有相关工作经验的确是一个弱势,那么哪些项目经历可以弥补这项弱势呢?例如你以前做过一个完整的分析项
天猫双11数据过于完美?我们用python来看看
↑关注+置顶 有趣的不像个技术号 是否真的完美? 双11结束了,大家已经无手可剁 。 天猫官方公布了今年的双11成交额为2684亿元,成功刷新了自己创下的商业纪录。按理说大家已经习惯了逐年增长,没想到 由于过于完美,引发网友提出质疑。 滑动图片浏览 or 点击查看大图▼ 该微博在天猫公布2019年销售额后,引发大量讨论,成功登上热搜。 一
一篇长文带你在python里玩转Json数据
↑一个宝藏公众号,长的好看的人都关注了 Json简介 Json(JavaScript Object Notation) 很多网站都会用到Json格式来进行数据的传输和交换,就像上篇我提到的,它们返回的数据都是Json格式的。这因为Json是一种轻量级的数据交换格式,具有数据格式简单,读写方便易懂等很多优点。用它来进行前后端的数据传输,大
那些为学校刷屏的人,刷的是什么?|无用但有趣
校门外店铺招牌总是换了又换,就像时间的年轮转了一圈又一圈。——《HD city》 经我们不负责任的观察,能看到朋友圈为学校集体刷屏的场面如下:一是吐槽学校又出了什么奇葩事。二是夸夸学校又得了什么奖。三是校庆时牛掰校友做了什么纪念,比如,出了首歌。 如《HD city》,这首歌是华北电力大学60周年校庆时,几位学生为华电制作的一首hiphop风格歌
什么,3行Python代码就能获取海量数据?
本文转载自公众号【法纳斯特】,详情可以点击上方卡片,关注该公众号,获取更多好文推荐。 一谈起数据分析,首先想到的就是数据,没有数据,谈何分析。 毕竟好的菜肴,没有好的原材料,是很难做的~ 所以本期小F就给大家分享一个获取数据的方法,只需三行代码就能搞定。 「GoPUP」,大佬造的轮子,大概有100+的免费数据接口。 GitHub:htt
手把手教你用pandas处理缺失值
导读:在进行数据分析和建模的过程中,大量的时间花在数据准备上:加载、清理、转换和重新排列。本文将讨论用于缺失值处理的工具。 缺失数据会在很多数据分析应用中出现。pandas的目标之一就是尽可能无痛地处理缺失值。 作者:韦斯·麦金尼(Wes McKinney)译者:徐敬一来源:大数据DT(ID:hzdashuju) pandas对象的所有描述
基于Maven工程下的MyBatis基本使用之数据插入【回填】、修改与删除
MyBatis基本使用声明:基于《基于Maven工程下的MyBatis框架+MySQL+连接池的数据查询操作》与《基于Maven工程下的MyBatis基本使用之SQL传单/多参、多表关联查询》进一步拓展,相关配置文件、数据文件可阅以上两篇。 数据插入<insert,使用<selectKey进行回填自动生成主键值 <!需要明确编写获取最新主键的SQL语句<in
手把手教你用pandas处理缺失值
导读:在进行数据分析和建模的过程中,大量的时间花在数据准备上:加载、清理、转换和重新排列。本文将讨论用于缺失值处理的工具。 缺失数据会在很多数据分析应用中出现。pandas的目标之一就是尽可能无痛地处理缺失值。 作者:韦斯·麦金尼(Wes McKinney)译者:徐敬一来源:大数据DT(ID:hzdashuju) pandas对象的所有描述
报考指南:这所大学值得拥有
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 今天给我的母校【延安大学】打一波广告,985高校全国只有39所,分数也要求非常高,如果你的成绩没有达到985/211高校的要求,还想体验一下985/211高校的生活,那么报考延安大学,绝对没错。这不是阿都随便忽悠你,因为延安大学与北京理工大学、中国人民大学两个学校具有联合培养项目,每个专业都会有名
干货|利用Python自动根据数据生成降雨量统计分析报告
作者:小小明 简介:Pandas数据处理专家,10余年编码经验,至今已帮助过成千上万名数据从业者解决工作实际遇到的问题,其中数据处理和办公自动化问题涉及的行业包括会计、HR、气象、金融等等,现为菜J学Python核心技术团队成员之一。 点击上方“Python爬虫与数据挖掘”,进行关注回复“书籍”即可获赠Python从入门到进阶共10本电子书今日鸡汤今夜偏
什么是标签?跟数据中台有什么关系?终于有人讲明白了
作者:任寅姿 季乐乐 来源:大数据DT(ID:hzdashuju) 01 什么是标签 标签指从原数据加工而来,能够直接为业务所用并产生业务价值的数据载体。 从本质上讲,标签本身也是一种数据(或映射指向数据),它是对物理层数据信息项的业务化封装,是数据资产的一种良好组织形式,是一种概念、逻辑定义,因此标签必须是可阅读、易理解的。 从粒度上来讲,标
爬取 20W 猫猫数据,来了解一下喵喵~
前言最近知道身边有许多朋友都养了猫,于是对猫猫有点兴趣了,于是找到了一个专门交易猫猫的网站猫猫交易网: http://www.maomijiaoyi.com/从此网站上爬取 20W 条猫猫交易数据,以及爬取了猫猫品种介绍的数据,以此来了解一下猫猫。 获取数据后小编从以下维度进行探索性分析:1、猫猫都有哪些品种,词云图2、原产地,世界地图3、体型占比,

热门文章

ConcurrentHashMap计算机网络操作系统数据库系统概论Java的其他Map

最新文章

数据库系统概论List集合ConcurrentHashMap计算机网络Java的其他Map