桶外排序算法的抽样分点分发策略  

The Sample-Seperators Based Distributing Scheme of the External Bucket Sort Algorithm

作　　者：杨磊[1] 黄辉 宋涛[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084 [2]中联绿盟信息技术(北京)有限公司开发部,北京100089

出　　处：《软件学报》2005年第5期643-651,共9页Journal of Software

基　　金：国家自然科学基金~~

摘　　要：计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.Two ways to sort externally are Multi-Line Merging Sort and Bucket Sort, both with two passes. The Bucket Sort burdens the CPU less and is more efficient, while its usage is restricted heavily by the High-Bit scheme that distributes records into subfiles: the keys have to be integers; the sizes of subfiles may vary too much; the number of subfiles cannot be chosen freely. Based on statistical theory, this paper presents a sample-seperators scheme to broaden the ussage of bucket sort algorithm. A brief discussion on the convergance of sample-seperator estimation is given and the probability to avoid memory overflow is calculated. This scheme enables the bucket sort algorithm to be applied in the SheenkSort system to win the 2003 PennySort (the Indy category) competition.

关 键 词：外排序 桶排序 多路归并 分发策略 抽样分点 PennySort 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]