大数据排序

BichonCode 等级 810 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亿就是平均数了
  • 求中位数:在排序的基础上,遍历到中间的那个数就是中位数了。

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

大数据排序

收藏
评论区

相关推荐

同学,你这简历上没项目啊!
大家好,我是小五 同学,刚毕业或者转行去求职数据分析师的时候,你遭遇过这样的尴尬怪圈吗? (https://imghelloworld.osscnbei
天猫双11数据过于完美?我们用python来看看
↑关注置顶 有趣的不像个技术号 是否真的完美? 双11结束了,大家已经无手可剁 。 天猫官方公布了今年的双11成交额为2684亿元,成
MySql 查询重复数大于1的数据(HAVING的使用)
在数据增加的过程中,因为某些原因,会产生重复数据,此时我们要看哪些数据重复了。 举栗: 要操作的表为test 主键id 需要排重的字段为field1,field2,field3,field4 SQL语句为 SELECT , count(id) FROM sysuser_user_pointlog_online_bak GROUP B
后台更新数据方案
当你遇到一些让你大吃一惊的解决方案的时候你不要惊讶,要学会低头去面试它,解决它。最近公司项目要做个人脸识别,类似于门禁卡之类的。本来这也没什么,因为我接到任务后第一反应是这样的逻辑:设备采集图片 设备识别图片是否是人脸 是人脸 提交服务器进行身份识别 服务器返回人物身份信息我觉得这样的逻辑就是有点耗时。然后根据公司需求是要做百度人脸的
同学,你这简历上没项目啊!
作者:朱小五 大家好,我是小五 同学,刚毕业或者转行去求职数据分析师的时候,你遭遇过这样的尴尬怪圈吗?比方说下面的jd就很真实:今天小五就跟大家聊聊,面试数据分析师时,如何彻底摆脱拿着单薄的简历与面试官尬聊的场景,关键词就是——工作经验!别慌,不是让你瞎编。没有相关工作经验的确是一个弱势,那么哪些项目经历可以弥补这项弱势呢?例如你以前做过一个完整的分析项
昨晚试试 数据行转列,差点翻了车
作者:朱小五来源:凹凸数据 大家好,我是小五昨晚遇到一道数据行转列问题,差点翻了车,跟大家分享一下。先跟大家讲一下,常见的行转列一般是这种形式:通常用来考察“如何用SQL、或者Python实现?”昨天群里有个朋友问了一道类似的题,我张嘴就来。结果拿来测试表一看,翻车了啊!这并不是常见的那种行转列啊!相当于分组筛选,然后横向拼接到一起?这思路也不对啊不过既然
天猫双11数据过于完美?我们用python来看看
↑关注+置顶 有趣的不像个技术号 是否真的完美? 双11结束了,大家已经无手可剁 。 天猫官方公布了今年的双11成交额为2684亿元,成功刷新了自己创下的商业纪录。按理说大家已经习惯了逐年增长,没想到 由于过于完美,引发网友提出质疑。 滑动图片浏览 or 点击查看大图▼ 该微博在天猫公布2019年销售额后,引发大量讨论,成功登上热搜。 一
那些为学校刷屏的人,刷的是什么?|无用但有趣
校门外店铺招牌总是换了又换,就像时间的年轮转了一圈又一圈。——《HD city》 经我们不负责任的观察,能看到朋友圈为学校集体刷屏的场面如下:一是吐槽学校又出了什么奇葩事。二是夸夸学校又得了什么奖。三是校庆时牛掰校友做了什么纪念,比如,出了首歌。 如《HD city》,这首歌是华北电力大学60周年校庆时,几位学生为华电制作的一首hiphop风格歌
手把手教你用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、体型占比,

热门文章

ConcurrentHashMapList集合数据库系统概论计算机网络操作系统

最新文章

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