| 本文已被：浏览 4446次 下载 6342次 |
码上扫一扫！ |
|
|
| 桶外排序算法的抽样分点分发策略 |
|
杨磊1, 黄辉2, 宋涛1
|
|
1.清华大学,计算机科学与技术系,北京,100084;2.中联绿盟信息技术(北京)有限公司,开发部,北京,100089
|
|
| 摘要: |
| 计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军. |
| 关键词: 外排序 桶排序 多路归并 分发策略 抽样分点 PennySort |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60223004,60321002,60303005(国家自然科学基金) |
|
| The Sample-Seperators Based Distributing Scheme of the External Bucket Sort Algorithm |
|
YANG Lei,HUANG Hui,SONG Tao
|
| Abstract: |
| 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. |
| Key words: external sort bucket sort multi-line merging distributing scheme sample-separators PennySort |
