`
v_JULY_v
  • 浏览: 69151 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
文章分类
社区版块
存档分类
最新评论

程序员编程艺术(算法卷):第十章、如何给10^7个数据量的磁盘文件排序

阅读更多

第十章、如何给10^7个数据量的磁盘文件排序


作者:July,yansha,5,编程艺术室。
出处:http://blog.csdn.net/v_JULY_v

前奏

经过几天的痛苦沉思,最终决定,把原程序员面试题狂想曲系列正式更名为程序员编程艺术系列,同时,狂想曲创作组更名为编程艺术室。之所以要改名,我们考虑到三点:1、为面试服务不能成为我们最终或最主要的目的,2、我更愿把解答一道道面试题,ACM题等各类程序设计题目的过程,当做一种艺术来看待,3、艺术的提炼本身是一个非常非常艰难的过程,但我们乐意接受这个挑战。

同时,本系列程序编程艺术-算法卷,大致分为三个部分:第一部分--程序设计,大凡如面试题目/ACM题目/poj的题目等各类程序设计的题,只要是好的,值得设计或深究的题目,我们都不拒绝。同时,紧扣实际,不断寻找更高效的算法解决实际问题。第二部分--算法研究,主要以我个人此前写的原创作品-十三个经典算法研究系列为题材,力争通俗易懂,详略得当的剖析各类经典的算法,并予以编程实现。第三部分--编码素养,主要包括程序员编码过程中一些编码规范等各类及其需要注意的问题。

如果有可能的话,此TAOPP系列将采取TAOCP那样的形式,出第一卷、第二卷、...。编程艺术来自哪里?编程采取合适的数据结构?寻求更高效的算法?或者,好的编码规范?希望,本TAOPP系列最终能给你一个完整的答复。

ok,如果任何人对本编程艺术系列有任何意见,或发现了本编程艺术系列任何问题,漏洞,bug,欢迎随时提出,我们将虚心接受并感激不尽,以为他人创造更好的价值,更好的服务。

第一节、如何给磁盘文件排序
问题描述:
输入:一个最多含有n个不重复的正整数的文件,其中每个数都小于等于n,且n=10^7。
输出:得到按从小到大升序排列的包含所有输入的整数的列表。
条件:最多有大约1MB的内存空间可用,但磁盘空间足够。且要求运行时间在5分钟以下,10秒为最佳结果。

分析:下面咱们来一步一步的解决这个问题,
1、归并排序。你可能会想到把磁盘文件进行归并排序,但题目要求你只有1MB的内存空间可用,所以,归并排序这个方法不行。
2、位图方案。熟悉位图的朋友可能会想到用位图来表示这个文件集合。例如正如编程珠玑一书上所述,用一个20位长的字符串来表示一个所有元素都小于20的简单的非负整数集合,边框用如下字符串来表示集合{1,2,3,5,8,13}:

0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0

上述集合中各数对应的位置则置1,没有对应的数的位置则置0。

参考编程珠玑一书上的位图方案,针对我们的10^7个数据量的磁盘文件排序问题,我们可以这么考虑,由于每个7位十进制整数表示一个小于1000万的整数。我们可以使用一个具有1000万个位的字符串来表示这个文件,其中,当且仅当整数i在文件中存在时,第i位为1。采取这个位图的方案是因为我们面对的这个问题的特殊性:1、输入数据限制在相对较小的范围内,2、数据没有重复,3、其中的每条记录都是单一的整数,没有任何其它与之关联的数据。
所以,此问题用位图的方案分为以下三步进行解决:

  • 第一步,将所有的位都置为0,从而将集合初始化为空。
  • 第二步,通过读入文件中的每个整数来建立集合,将每个对应的位都置为1。
  • 第三步,检验每一位,如果该位为1,就输出对应的整数。

经过以上三步后,产生有序的输出文件。令n为位图向量中的位数(本例中为1000 0000),程序可以用伪代码表示如下:

上面只是为了简单介绍下位图算法的伪代码之抽象级描述。显然,咱们面对的问题,可不是这么简单。下面,我们试着针对这个要分两趟给磁盘文件排序的具体问题编写完整代码,如下。

而后测试了一下上述程序的运行时间,采取位图方案耗时14s,即14000ms:

本章中,生成大数据量(1000w)的程序如下,下文第二节的多路归并算法的c++实现和第三节的磁盘文件排序的编程实现中,生成的1000w数据量也是用本程序产生的,且本章内生成的1000w数据量的数据文件统一命名为“data.txt”。

不过很快,我们就将意识到,用此位图方法,严格说来还是不太行,空间消耗10^7/8还是大于1M(1M=1024*1024空间,小于10^7/8)。
既然如果用位图方案的话,我们需要约1.25MB(若每条记录是8位的正整数的话,则10000000/(1024*1024*8) ~= 1.2M)的空间,而现在只有1MB的可用存储空间,那么究竟该作何处理呢?

updated && correct:

@yansha: 上述的位图方案,共需要扫描输入数据两次,具体执行步骤如下:

  • 第一次,只处理1—4999999之间的数据,这些数都是小于5000000的,对这些数进行位图排序,只需要约5000000/8=625000Byte,也就是0.625M,排序后输出。
  • 第二次,扫描输入文件时,只处理4999999-10000000的数据项,也只需要0.625M(可以使用第一次处理申请的内存)。
    因此,总共也只需要0.625M

位图的的方法有必要强调一下,就是位图的适用范围为针对不重复的数据进行排序,若数据有重复,位图方案就不适用了。

3、多路归并。把这个文件分为若干大小的几块,然后分别对每一块进行排序,最后完成整个过程的排序。k趟算法可以在kn的时间开销内和n/k的空间开销内完成对最多n个小于n的无重复正整数的排序。比如可分为2块(k=2,1趟反正占用的内存只有1.25/2M),1~4999999,和5000000~9999999。先遍历一趟,首先排序处理1~4999999之间的整数(用5000000/8=625000个字的存储空间来排序0~4999999之间的整数),然后再第二趟,对5000001~1000000之间的整数进行排序处理。在稍后的第二节、第三节、第四节,我们将详细阐述并实现这种多路归并排序磁盘文件的方案。
4、读者思考。经过上述思路3的方案之后,现在有两个局部有序的数组了,那么要得到一个完整的排序的数组,接下来改怎么做呢?或者说,如果是K路归并,得到k个排序的子数组,把他们合并成一个完整的排序数组,如何优化?或者,我再问你一个问题,K路归并用败者树 和 胜者树 效率有什么差别?这些问题,请读者思考。

第二节、多路归并算法的c++实现

本节咱们暂抛开咱们的问题,阐述下有关多路归并算法的c++实现问题。在稍后的第三节,咱们再来具体针对咱们的磁盘文件排序问题阐述与实现。

在了解多路归并算法之前,你还得了解归并排序的过程,因为下面的多路归并算法就是基于这个流程的。其实归并排序就是2路归并,而多路归并算法就是把2换成了k,即多(k)路归并。下面,举个例子来说明下此归并排序算法,如下图所示,我们对数组8 3 2 6 7 1 5 4进行归并排序:

归并排序算法简要介绍:
一、思路描述:
设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中。

二路归并排序的过程是:
(1)把无序表中的每一个元素都看作是一个有序表,则有n个有序子表;
(2)把n个有序子表按相邻位置分成若干对(若n为奇数,则最后一个子表单独作为一组),每对中的两个子表进行归并,归并后子表数减少一半;
(3)反复进行这一过程,直到归并为一个有序表为止。

二路归并排序过程的核心操作是将一维数组中相邻的两个有序表归并为一个有序表。

二、分类:
归并排序可分为:多路归并排序、两路归并排序 。
若归并的有序表有两个,叫做二路归并。一般地,若归并的有序表有k个,则称为k路归并。二路归并最为简单和常用,既适用于内部排序,也适用于外部排序。本文着重讨论外部排序下的多(K)路归并算法。

三、算法分析:
1、稳定性:归并排序是一种稳定的排序。
2、存储结构要求:可用顺序存储结构。也易于在链表上实现。
3、时间复杂度: 对长度为n的文件,需进行lgn趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。。
4、空间复杂度:需要一个辅助向量来暂存两有序子文件归并的结果,故其辅助空间复杂度为O(n),显然它不是就地排序。
注意:若用单链表做存储结构,很容易给出就地的归并排序。

总结:与快速排序相比,归并排序的最大特点是,它是一种稳定的排序方法。归并排序一般多用于外排序。但它在内排方面也占有重要地位,因为它是基于比较的时间复杂度为O(N*Log(N))的排序算法中唯一稳定的排序,所以在需要稳定内排序时通常会选择归并排序。归并排序不要求对序列可以很快地进行随机访问,所以在链表排序的实现中很受欢迎。

好的,介绍完了归并排序后,回到咱们的问题。由第一节,我们已经知道,当数据量大到不适合在内存中排序时,可以利用多路归并算法对磁盘文件进行排序。

我们以一个包含很多个整数的大文件为例,来说明多路归并的外排序算法基本思想。假设文件中整数个数为N(N是亿级的),整数之间用空格分开。首先分多次从该文件中读取M(十万级)个整数,每次将M个整数在内存中使用快速排序之后存入临时文件,然后使用多路归并将各个临时文件中的数据再次整体排好序后存入输出文件。显然,该排序算法需要对每个整数做2次磁盘读和2次磁盘写。以下是本程序的流程图:

本程序是基于以上思想对包含大量整数文件的从小到大排序的一个简单实现,这里没有使用内存缓冲区,在归并时简单使用一个数组来存储每个临时文件的第一个元素。下面是多路归并排序算法的c++实现代码(在第四节,将给出多路归并算法的c实现):

程序测试:读者可以继续用小文件小数据量进一步测试。

第三节、磁盘文件排序的编程实现

ok,接下来,我们来编程实现上述磁盘文件排序的问题,本程序由两部分构成:
1、内存排序
由于要求的可用内存为1MB,那么每次可以在内存中对250K的数据进行排序,然后将有序的数写入硬盘。
那么10M的数据需要循环40次,最终产生40个有序的文件。
2、归并排序

  1. 将每个文件最开始的数读入(由于有序,所以为该文件最小数),存放在一个大小为40的first_data数组中;
  2. 选择first_data数组中最小的数min_data,及其对应的文件索引index;
  3. 将first_data数组中最小的数写入文件result,然后更新数组first_data(根据index读取该文件下一个数代替min_data);
  4. 判断是否所有数据都读取完毕,否则返回2。

所以,本程序按顺序分两步,第一步、Memory Sort,第二步、Merge Sort。程序的流程图,如下图所示(感谢F的绘制)。

然后,编写的完整代码如下:

其中,生成数据文件data.txt的代码在第一节已经给出。

程序测试

1、咱们对1000W数据进行测试,打开半天没看到数据,

2、编译运行上述程序后,data文件先被分成40个小文件data[1....40],然后程序再对这40个小文件进行归并排序,排序结果最终生成在result文件中,自此result文件中便是由data文件的数据经排序后得到的数据。

3、且,我们能看到,data[i],i=1...40的每个文件都是有序的,如下图:

4、最终的运行结果,如下,单位统一为ms:

由上观之,我们发现,第一节的位图方案的程序效率是最快的,约为14s,而采用上述的多路归并算法的程序运行时间约为25s。时间主要浪费在读写磁盘IO上,且程序中用的库函数qsort也耗费了不少时间。所以,总的来说,采取位图方案是最佳方案。

小数据量测试:

我们下面针对小数据量的文件再测试一次,针对20个小数据,每趟对4个数据进行排序,即5路归并,程序的排序结果如下图所示。

运行时间:

0ms,可以忽略不计了,毕竟是对20个数的小数据量进行排序:

沙海拾贝:

我们不在乎是否能把一个软件产品或一本书最终完成,我们更在乎的是,在完成这个产品或创作这本书的过程中,读者学到了什么,能学到什么?所以,不要一味的马上就想得到一道题目的正确答案,请跟着我们一起逐步走向山巅。

第四节、多路归并算法的c实现

本多路归并算法的c实现原理与上述c++实现一致,不同的地方体现在一些细节处理上,且对临时文件的排序,不再用系统提供的快排,即上面的qsort库函数,是采用的三数中值的快速排序(个数小于3用插入排序)的。而我们知道,纯正的归并排序其实就是比较排序,在归并过程中总是不断的比较,为了从两个数中挑小的归并到最终的序列中。ok,此程序的详情请看:

程序测试:

在此,我们先测试下对10000000个数据的文件进行40趟排序,然后再对100个数据的文件进行4趟排序(读者可进一步测试)。如弄几组小点的数据,输出ID和数据到屏幕,再看程序运行效果。

  1. 10个数, 4组
  2. 40个数, 5组
  3. 55个数, 6组
  4. 100个数, 7组

(备注:1、以上所有各节的程序运行环境为windows xp + vc6.0 + e5200 cpu 2.5g主频,2、感谢5为本文程序所作的大量测试工作)

全文总结:

1、关于本章中位图和多路归并两种方案的时间复杂度及空间复杂度的比较,如下:

时间复杂度 空间复杂度
位图 O(N) 0.625M
多位归并 O(Nlogn) 1M

(多路归并,时间复杂度为O(k*n/k*logn/k ),严格来说,还要加上读写磁盘的时间,而此算法绝大部分时间也是浪费在这上面)

2、bit-map

适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下
基本原理及要点:使用bit数组来表示某些元素是否存在,比如8位电话号码
扩展:bloom filter可以看做是对bit-map的扩展

问题实例:
1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。
8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。
2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map。

3、[外排序适用范围]大数据的排序,去重基本原理及要点:外排序的归并方法,置换选择败者树原理,最优归并树扩展。问题实例:1).有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词。这个数据具有很明显的特点,词的大小为16个字节,但是内存只有1m做hash有些不够,所以可以用来排序。内存可以当输入缓冲区使用。

4、海量数据处理

有关海量数据处理的方法或面试题可参考此文,十道海量数据处理面试题与十个方法大总结。日后,会逐步实现这十个处理海量数据的方法。同时,送给各位一句话,解决问题的关键在于熟悉一个算法,而不是某一个问题。熟悉了一个算法,便通了一片题目。

本章完。


版权所有,本人对本blog内所有任何内容享有版权及著作权。网络转载,请以链接形式注明出处。

分享到:
评论

相关推荐

    程序员编程艺术

    - 第十章提供了如何给大量数据量的磁盘文件进行排序的方法。 **8. 最长公共子序列** - 第十一章探讨了最长公共子序列(LCS)问题的解决策略。 **9. 复杂问题解决** - 第十二章至第二十二章覆盖了一系列复杂问题...

    程序员编程艺术第一 ~二十七章

    - **第十章:如何给10^7个数据量的磁盘文件排序** - 讨论了外部排序的技术,适用于大规模数据的排序问题。 - **第十一章:最长公共子序列(LCS)问题** - 使用动态规划方法解决了最长公共子序列问题。 - **第十二~...

    程序员编程艺术第一~二十七章集锦与总结(教你如何编程)(by_July)定稿版.pdf

    - **第十章**:如何给10^7个数据量的磁盘文件排序 - **第十一章**:最长公共子序列(LCS)问题 - **第十二至十五章**:中签概率、IP访问次数、回文等问题 - **第十六至第二十章**:全排列、跳台阶、奇偶排序等问题...

    程序员编程艺术第一~二十七章集锦与总结

    - **第十章:如何给10^7个数据量的磁盘文件排序** —— 提供了大规模数据排序的有效策略。 - **第十一章:最长公共子序列(LCS)问题** —— 探讨了LCS问题的经典解法和优化技巧。 - **第十二~十五章:中签概率,IP...

    程序员编程艺术第一~三十七章集锦by_July

    - **数据处理**:10^7个数据量的磁盘文件排序、中签概率、IP访问次数。 - **算法优化**:二分查找、倒排索引、不改变正负数之间相对顺序重新排列数组。 - **高级问题**:最大连续乘积子串、字符串编辑距离、字符串...

    程序员编程艺术--共二十七章-集锦与总结(教你如何编程)

    - **第十章:如何给10^7个数据量的磁盘文件排序** - 讨论大数据量排序的方法。 - 涵盖外部排序技术及其实现细节。 - **第十一章:最长公共子序列(LCS)问题** - 讲解最长公共子序列问题的定义和求解方法。 - 分析...

    程序员编程艺术第一~二十七章集锦与总结(教你如何编程)

    - **第十章:如何给10^7个数据量的磁盘文件排序** - **知识点**:外部排序算法、归并排序。 - **应用场景**:大数据处理、海量日志分析等。 - **第十一章:最长公共子序列(LCS)问题** - **知识点**:动态规划...

    程序员编程艺术第一~二十七章集锦与总结(教你如何编程)(by_July)定稿版

    ##### 第十章:如何给10^7个数据量的磁盘文件排序 介绍了大规模数据排序的技术,包括外部排序算法的应用。 ##### 第十一章:最长公共子序列(LCS)问题 LCS问题是字符串匹配中的一个典型问题,本章详细阐述了如何...

    程序员编程艺术 第一~二十七章集锦与总结

    10. **如何给10^7个数据量的磁盘文件排序** - **知识点**:外部排序算法、归并排序 - **内容概述**:探讨了如何对大规模数据进行排序的方法。主要介绍了外部排序的概念和归并排序在磁盘文件排序中的应用。 #### ...

    数据结构与算法之排序

    当数据量过大时,先将数据分割成小块进行内部排序,然后通过多次交互将这些已排序的小块合并成最终的有序序列。 在C++学习中,实现这些排序算法需要掌握基本的编程技巧和STL容器,如vector和list,以及算法库如...

    算法_三十七章集锦by_July

    8. 第八章到第十章讨论了面向对象编程中的虚函数、链表问题和大数据处理,例如如何对10^7个数据量的磁盘文件进行排序。 9. 第十一章到第二十二章内容丰富,涵盖了如最长公共子序列(LCS)、全排列、跳台阶、奇偶...

    经典查找排序算法(C++版)

    在IT领域,排序和查找是基础且至关重要的算法,它们被广泛应用于各种软件开发和数据处理中。这里我们将深入探讨标题和描述中提及的几种经典查找和排序算法,并结合C++编程语言进行讨论。 首先,我们来看查找算法。...

    _C语言高级程序员编程指南

    5. **文件操作**:C语言提供了标准I/O库,允许程序员读写磁盘文件。书中会介绍`fopen`、`fwrite`、`fread`、`fprintf`等函数的用法,以及文件的错误处理。 6. **递归与算法**:递归是C语言中解决问题的强大工具,书...

    利用汇编语言实现快速排序,汇编语言排序算法

    汇编语言实现快速排序虽然复杂,但其运行效率高,特别适合处理大数据量的情况。由于直接操作硬件,可以充分利用CPU的性能,减少不必要的数据移动和比较操作。然而,这也要求程序员有扎实的底层知识和细致的编程技巧...

    数据结构与算法(英文版) 数据结构与算法(英文版)

    - **第十章:2-3-4树和外部存储**(Chapter 10 - 2-3-4 Trees and External Storage):讨论了2-3-4树这种用于外部存储优化的数据结构,以及如何有效地在磁盘等外部存储设备上存储大量数据。 - **第十一章:哈希表**...

    磁盘文件操作模拟内存分配与回收 C++编写

    3. **文件映射机制**:建立内存地址和磁盘文件偏移量的映射关系,方便数据的读写。 4. **优化性能**:考虑文件访问速度,可能需要预读和缓存策略,减少磁盘I/O次数。 通过这种方式,我们不仅可以学习和实践C++的...

    数据结构和算法分析的PHP描述

    内部排序是指数据在整个排序过程中全部存在于内存中的排序算法,例如木桶排序。 **外部排序** 外部排序是指数据规模太大无法全部放入内存中,需要多次读写磁盘的排序方法。 #### 内存划分 内存划分是指如何合理地...

    数据结构_程序员考试.rar

    9. **文件与外部存储**:在大型数据处理中,数据不能全部存储在内存,需要了解磁盘文件和外部存储的组织方式,如顺序文件、索引文件、直接存取文件等。 10. **动态规划与贪心策略**:这些是解决问题的有效方法,...

    算法编程大赛题目(.zip)

    每个问题的解答通常会涉及数据结构(如队列、栈、图、树等)、算法设计(如排序、搜索、动态规划、贪心、回溯等)和编程技巧。通过解决这些问题,不仅可以深化对这些基础概念的理解,还能提升解决实际问题的能力,对...

    JAVA 排序复习

    主要有两种分类:内部排序(数据在内存中完成排序)和外部排序(数据量太大,需要借助磁盘等外部存储)。在内部排序中,常见的算法有: 1. 冒泡排序:通过不断地交换相邻元素来逐步调整序列,时间复杂度为O(n^2)。 ...

Global site tag (gtag.js) - Google Analytics