文档章节

设想有一个20GB的文件,每一行一个字符串。说明如何将这个文件进行排序。

一贱书生
 一贱书生
发布于 2016/11/24 08:43
字数 687
阅读 10
收藏 1
点赞 0
评论 0

设想有一个20GB的文件,每一行一个字符串。说明如何将这个文件进行排序。

 

思路1:外部排序,将部分数据载入内存。

将整个文件划分成许多块,每个块xMB,其中x是可用的内存大小。每个块各自进行排序,然后存回文件系统。各个块一旦完成排序,便将这些块逐一合并在一起,最终就能得到全部排好序的文件。

 

思路2:

内存肯定没有20GB大,所以不可能采用传统排序法。但是可以将文件分成许多块,每块xMB,针对每个块各自进行排序,存回文件系统。

然后将这些块逐一合并,最终得到全部排好序的文件。

 

外排序的一个例子是外归并排序(External merge sort),它读入一些能放在内存内的数据量,在内存中排序后输出为一个顺串(即是内部数据有序的临时文件),处理完所有的数据后再进行归并。[1][2]比如,要对900MB的数据进行排序,但机器上只有100 MB的可用内存时,外归并排序按如下方法操作:

  1. 读入100 MB的数据至内存中,用某种常规方式(如快速排序堆排序归并排序等方法)在内存中完成排序。
  2. 将排序完成的数据写入磁盘。
  3. 重复步骤1和2直到所有的数据都存入了不同的100 MB的块(临时文件)中。在这个例子中,有900 MB数据,单个临时文件大小为100 MB,所以会产生9个临时文件。
  4. 读入每个临时文件(顺串)的前10 MB( = 100 MB / (9块 + 1))的数据放入内存中的输入缓冲区,最后的10 MB作为输出缓冲区。(实践中,将输入缓冲适当调小,而适当增大输出缓冲区能获得更好的效果。)
  5. 执行九路归并算法,将结果输出到输出缓冲区。一旦输出缓冲区满,将缓冲区中的数据写出至目标文件,清空缓冲区。一旦9个输入缓冲区中的一个变空,就从这个缓冲区关联的文件,读入下一个10M数据,除非这个文件已读完。这是“外归并排序”能在主存外完成排序的关键步骤 -- 因为“归并算法”(merge algorithm)对每一个大块只是顺序地做一轮访问(进行归并),每个大块不用完全载入主存。

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 723
码字总数 600072
作品 0
Linux Shell处理文本最常用的工具大盘点

导读 本文将介绍Linux下使用Shell处理文本时最常用的工具:find、grep、xargs、sort、uniq、tr、cut、paste、wc、sed、awk;提供的例子和参数都是最常用和最为实用的,我对shell脚本使用的原...

linuxprobe16
2016/12/21
25
0
linux常用的shell文本处理方法

find 文件查找 查找txt和pdf文件 find . ( -name ".txt" -o -name ".pdf" ) -print 正则方式查找.txt和pdf find . -regex ".(.txt|.pdf)$" -iregex: 忽略大小写的正则 否定参数查找所有非t...

stone_
2016/05/06
95
2
文件操作和过滤

文件操作和过滤 绝大多数命令行工作是针对文件的。我们会在本节中讨论如何观察及过滤文件内容,使用一条命令从文件中提取所需信息,以及对文件的内容进行排序。 cat、tail、head、tee:文件打...

范堡
2009/05/11
402
0
Linux Shell 文本处理工具集锦

Linux Shell 文本处理工具集锦 本文将介绍Linux下使用Shell处理文本时最常用的工具: find、grep、xargs、sort、uniq、tr、cut、paste、wc、sed、awk; 提供的例子和参数都是最常用和最为实用...

平凡之路
2014/10/13
0
0
Linux Shell 文本处理工具集锦

本文将介绍Linux下使用Shell处理文本时最常用的工具: find、grep、xargs、sort、uniq、tr、cut、paste、wc、sed、awk; 提供的例子和参数都是最常用和最为实用的; 我对shell脚本使用的原则...

小股儿
2014/01/06
29
0
Linux Shell文本处理工具集锦

本文将介绍Linux下使用Shell处理文本时最常用的工具: find、grep、xargs、sort、uniq、tr、cut、paste、wc、sed、awk; 提供的例子和参数都是最常用和最为实用的; 我对shell脚本使用的原则...

孟飞阳
2016/07/08
38
0
一个巨大文件的操作问题

有一个11G的文本文件,里边存放的格式是 11000222 11122211 11122211 11111111 类似这种格式,一行一行的,每一行看成是一个字符串,怎么操作去掉里边重复的字符串,并且对剩下的字符串进行排...

ldl123292
2013/09/11
1K
29
linux常用的文本处理命令

一、grep 命令 命令说明:按行处理,输出文件中包含搜索字符串的所有行。 格式:grep [options] ‘搜索字符串’ filename 参数说明: -a:在二进制文件中,以文本文件的方式搜索数据; -c:计...

小呀小蜗牛
2016/05/24
97
0
[MapReduce编程]用MapReduce大刀砍掉海量数据离线处理问题

这篇文章我之前是拜读过的,今天闲来没事,就想拿来当做MapReduce的练习。 MapReduce这把刀太大,刀大了问题就抵不住这刀锋了,事实上一开始我想着,这么多些题目,当是要花不少功夫的,但当...

Sandy_wu
2013/06/05
0
2
第十三章 对文本进行排序、单一和重复操作:sort命令、uniq命令

第十三章 对文本进行排序、单一和重复操作:sort命令、uniq命令 sort命令 名字解释 sort命令 它将文件进行排序,并将排序结果标准输出。sort命令即可以从特定的文件,也可以从stdin中获取输入...

506554897
06/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Webpack使用nodemon实时打包编译

业务场景: 1.编写一个npm组件包并且link到了项目文件中 2.需要不断的修改并run build编译npm包并且在项目run dev 查看效果 3.问题: 每次改完npm包都要手动run build编译十分的麻烦且低效,可不...

JamesView
17分钟前
0
0
电脑炸了,浪费我好几天时间,还是简要记下来吧

我的小本本一直在兢兢业业的干活,然而前几天说炸就炸了...... 爆炸现场: 软件: windows10 pro + EIS11+ 360卫士 BIOS:N1DET98W 2.24 硬件: Xeon E3 1505-V5 nv-M3000M thinkpadP70:20E...

Oh_really
21分钟前
0
0
Git之branch和checkout

1.branch是查看、创建、删除分支 #>git branch --helpNAME git-branch - List, create, or delete branchesSYNOPSIS git branch [--color[=<when>] | --no-color] [......

汉斯-冯-拉特
23分钟前
0
0
Mybatis拦截器之数据权限过滤与分页集成

需求场景 最近项目有个数据权限的业务需求,要求大致为每个单位只能查看本级单位及下属单位的数据,例如:一个集团军下属十二个旅,那么军级用户可以看到所有数据,而每个旅则只能看到本旅部...

佛系程序猿灬
32分钟前
9
0
SpringCloud 微服务 (十六) 服务追踪 Zipkin

问题 在服务中,有一个接口,该A接口中又调用了其他服务的B、C、D接口,出现一个请求耗时大的问题,这时候并不知道该B、C、D接口中哪个接口造成的耗时量,然后比如确定C服务接口出现的耗时量大,但...

___大侠
今天
0
0
Java面试基础篇——第八篇:抽象类与接口的区别

1.抽象类 抽象类:如果一个类中包含有抽象方法,或这个类使用abstract关键字修饰,则称这个类是抽象类。 抽象方法是什么呢?抽象方法就是指用abstract关键字修饰的方法。 需要注意的是:抽象...

developlee的潇洒人生
今天
2
0
jsoup 相关资料

1.jsoup 2.Jsoup概述 3.jsoup入门 4.jsoup Java HTML Parser 1.11.3 API

IT追寻者
今天
1
0
JPA @MappedSuperclass 注解说明

基于代码复用和模型分离的思想,在项目开发中使用JPA的@MappedSuperclass注解将实体类的多个属性分别封装到不同的非实体类中。 1.@MappedSuperclass注解只能标准在类上:@Target({java.lang....

海博1600
今天
0
0
【一】Scala Configuration 相关API

Play使用了 Typesafe config library,但是也提供了一个有着更多Scala高级特性的的 Configuration 封装。不熟悉Typesafe配置的开发者可以移步 configuration文件的语法和特性文档。 读取配置...

Landas
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部