THSort(2002年版)算法设计思想.doc

THSort(2002年版)算法设计思想摘要：注:应一些网友的要求,将算法思想公开,希望大家多提意见和建议.联系人:刘鹏 . 由以上算法可知:设共有M个临时文件待归并,总数据量为N条,则归并算法的复杂度.关键词：算法设计,算法类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！THSort(2002年版)算法设计思想注：应一些网友的要求，将算法思想公开，希望大家多提意见和建议。联系人：刘鹏施遥 算法分为两部分。第一部分将所要排序文件读入后分块，每一小块进行排序后写作一个临时文件。第二部分将第一部分所写的所有临时文件进行归并排序。一、分块排序由于总数据量远远大于内存所能容纳的数据量。因此对于单个进程来说，只能将数据分成若干大小不超过内存容量的块，每次只能读入一块数据（Read Block），进行排序（Sort Block），然后将结果保存到文件之中（Write Block），如Figure A所示（不同的颜色表示对不同数据块的处理）。我们用表示Read Block的耗时，表示Sort Block的耗时，表示Write Block的耗时，n表示数据块的个数。其中、（）为读（写）全部数据一次的时间，是恒定的。Read SortWriteReadSortWrite ReadSortWriteFigure A：没有Overlapped I/O的情况则单进程排序的总耗时为如果我们把源数据和排序后保存的数据放置在两个不同的硬盘上，那么Read Block和Write Block是可以同时进行并且不争夺I/O资源的。同时，这两个模块占用CPU资源很少，可以和Sort Block并行运行的。因此，我们可以采用多进程并行的方法来提高效率。我们采用三个进程并行运行的方法来对源数据进行排序（如Figure B所示），使得CPU和I/O资源得到充分的利用。Thread AThread BThread CRead WaitSortReadWaitWriteSortReadRead WaitWaitWriteSortSortRead WaitWriteWriteSortRead WaitWriteSortWriteFigure B：使用Overlapped I/O的多线程在通常情况下，Tr、Ts和Tw并不相等。例如，Sort Block的耗时大于Read Block和Write Block的耗时的时候，总耗时为仍然比单进程的效率要高得多。在理想情况下，Read Block，Write Block，Sort Block消耗的时间近似相等()。在三个进程都开始运行之后，任何一个时刻都恰有一个Read Block、一个Write Block，一个Sort Block在并行运行，系统的资源得到最大可能的利用（如Figure C所示）。Thread AThread BThread CRead SortReadWriteSortReadReadWriteSortSortReadWriteWriteSortReadWrite SortWriteFigure C：理想的多线程情况理想情况下，三进程排序的总耗时因此我们的程序采用三进程并行的算法来对全部数据分块排序，并尽可能通过调整数据块的大小让Tr、Ts和Tw尽量相等。每个进程最多使用1/3的内存容量，并行处理n/3块数据块的排序工作，并将排序的结果保存到n个临时文件中。由于实际运行过程是在非理想情况下的，因此为了防止进程之间对资源的争夺，我们在程序中规定：i. B进程的第k个Read Block必须在A进程的第k个Read Block结束之后开始；ii. C进程的第k个Read Block必须在B进程的第k个Read Block结束后开始；iii. A进程的第k个Read Block必须在C进程的第k1个Read Block结束后开始。以此来保证三进程的并行运行与理想情况下近似一致。对于每个数据块，我们采用的排序算法是快速排序算法。在源数据随机排列的情况下，这一算法的平均时间复杂度为O(nlogn)，是以交换为基础的排序的事件复杂度下限。二、归并算法归并算法分这两个同时并行的进程，读进程与写进程同时进行。读写进程共享同一块内存，如下图所示Memory block M(File M)Memory block M-1(File M-1).Memory block 3(File 3)Memory block 2(File 2)Memory block 1(File 1)Signal读进程：一、初始化：1、若有M个有序临时文件，则将内存等分为M块。2、第i块对应第i个临时文件，如果文件长度小于等于对应内存块，则将文件全部读入；否则读取文件直至占满内存。若某文件被读完，则置该文件读完标记。3、设置头指针headi与每块内存块中的数据量sizei。二、读取数据：1、比较各块内存中数据量的多少，选择数据量最少的内存块j。2、读取文件j，直至文件j被读完或占满内存块j。若读完文件j，置文件j读完标记。3、若所有文件读完，退出；否则转1。写进程：1、等待，直至读进程的初始化完成2、用所有内存块的第一条数据的关键字，组成一个堆。该堆为一棵二叉树，每个父结点的值均小于子结点的值。3、输出堆的根结点，该结点对应内存块的头指针headI后移一条数据，长度sizeI减去单条数据长度4、设被输出的结点属于内存块i（文件i），有以下四种情况（1）、若文件i已经全部读完，且内存块i为空，则标记文件i为完成。若堆此时为空，则退出写进程；否则，将二叉树任一叶结点取代原被输出的根结点，转5调整堆。（2）、若文件i已读完，但内存块i不为空，则将内存块i中的头指针所指关键字入堆，取代原被输出的根结点，转5调整堆。（3）、若文件i未读完，内存块i为空，则等待直到有新的数据读入。将该条数据的关键字放堆，取代原被输出的根标点，转5调整堆。（4）、若文件i未读完，且内存块i不为空，则将内存块i中的头指针所指关键字入堆，取代原被输出的根结点，转5调整堆。5、堆的递归调整（1）、i-根结点；（2）、若结点i无子结点，结束堆调整；若结点i有子结点，且其关键字均大于结点i，结束堆调整；（3）、比较i的子结点，选择关键字值较小的一个（结点j），结点i与结点j交换，转（2）。6、转3 由以上算法可知：设共有M个临时文件待归并，总数据量为N条，则归并算法的复杂度为O（N*Log2M）。算法分析： 设总数据量为N，分块排序时为M块（临时文件），每一块的大小即为N=N/M。 考虑第一部分的分块排序算法。一方面，随着每一个块数据规模N的扩大，读写时间基本呈线性增长（因为N=Tl+R*Tr，Tl为磁盘的定位时间，R为磁盘的数据传输率，故Tr=(N-T1)/R。），而快速排序时间Ts的复杂度为O（N*Log2N）。这两条曲线的交点（使得Tr与Ts相等的点），就是理想的N的大小。过了这个临界点后，Tr与Ts的值的差距将迅速拉大。故而如果每一块的数据越少（即N越小），则在分块排序中读写与排序时间越是接近，这样在分块排序中进程等待时间越短，效率越高。另一方面，整个读写与排序理论上的时间复杂度为O（N+N*Log2N），当N越小时，排序时间越少。综合以上两个方面，在分块排序中，块分得越多（即每一块越小）则排序时间越少。 对于第二部分归并排序。由于其复杂度为O（N*Log2M），