文档章节

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

一贱书生
 一贱书生
发布于 2016/11/24 08:43
字数 687
阅读 12
收藏 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
Linux Shell处理文本最常用的工具大盘点

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

linuxprobe16
2016/12/21
25
0
文件操作和过滤

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

范堡
2009/05/11
402
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
一个巨大文件的操作问题

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

ldl123292
2013/09/11
1K
29
Linux Shell文本处理工具集锦

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

孟飞阳
2016/07/08
38
0

没有更多内容

加载失败,请刷新页面

加载更多

70.shell的函数 数组 告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析 20.16/20.17 shell中的函数: ~1. 函数就是把一段代码整理到了一个小单元中,并给这个小单元起一个名字,当用到这段...

王鑫linux
33分钟前
0
0
分布式框架spring-session实现session一致性使用问题

前言:项目中使用到spring-session来缓存用户信息,保证服务之间session一致性,但是获取session信息为什么不能再服务层获取? 一、spring-session实现session一致性方式 用户每一次请求都会...

WALK_MAN
56分钟前
3
0
C++ yield()与sleep_for()

C++11 标准库提供了yield()和sleep_for()两个方法。 (1)std::this_thread::yield(): 线程调用该方法时,主动让出CPU,并且不参与CPU的本次调度,从而让其他线程有机会运行。在后续的调度周...

yepanl
今天
3
0
Java并发编程实战(chapter_3)(线程池ThreadPoolExecutor源码分析)

这个系列一直没再写,很多原因,中间经历了换工作,熟悉项目,熟悉新团队等等一系列的事情。并发课题对于Java来说是一个又重要又难的一大块,除非气定神闲、精力满满,否则我本身是不敢随便写...

心中的理想乡
今天
23
0
shell学习之获取用户的输入命令read

在运行脚本的时候,命令行参数是可以传入参数,还有就是在脚本运行过程中需要用户输入参数,比如你想要在脚本运行时问个问题,并等待运行脚本的人来回答。bash shell为此提 供了read命令。 ...

woshixin
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部