文档章节

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

一贱书生
 一贱书生
发布于 2016/11/24 08:43
字数 687
阅读 15
收藏 1

设想有一个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
博文 724
码字总数 600123
作品 0
私信 提问
文件操作和过滤

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

范堡
2009/05/11
402
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
linux常用的文本处理命令

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

小呀小蜗牛
2016/05/24
97
0
Linux Shell 文本处理工具集锦

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

平凡之路
2014/10/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mariadb二进制包安装,Apache安装

安装mariadb 下载二进制包并解压 [root@test-a src]# wget https://downloads.mariadb.com/MariaDB/mariadb-10.2.6/bintar-linux-glibc_214-x86_64/mariadb-10.2.6-linux-glibc_214-x86_64.t......

野雪球
今天
3
0
ConcurrentHashMap 高并发性的实现机制

ConcurrentHashMap 的结构分析 为了更好的理解 ConcurrentHashMap 高并发的具体实现,让我们先探索它的结构模型。 ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEnt...

TonyStarkSir
今天
3
0
大数据教程(7.4)HDFS的java客户端API(流处理方式)

博主上一篇博客分享了namenode和datanode的工作原理,本章节将继前面的HDFS的java客户端简单API后深度讲述HDFS流处理API。 场景:博主前面的文章介绍过HDFS上存的大文件会成不同的块存储在不...

em_aaron
昨天
4
0
聊聊storm的window trigger

序 本文主要研究一下storm的window trigger WindowTridentProcessor.prepare storm-core-1.2.2-sources.jar!/org/apache/storm/trident/windowing/WindowTridentProcessor.java public v......

go4it
昨天
7
0
CentOS 生产环境配置

初始配置 对于一般配置来说,不需要安装 epel-release 仓库,本文主要在于希望跟随 RHEL 的配置流程,紧跟红帽公司对于服务器的配置说明。 # yum update 安装 centos-release-scl # yum ins...

clin003
昨天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部