主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
杨磊,黄辉,宋涛.桶外排序算法的抽样分点分发策略.软件学报,2005,16(5):643-651
桶外排序算法的抽样分点分发策略
The Sample-Seperators Based Distributing Scheme of the External Bucket Sort Algorithm
投稿时间:2004-03-23  修订日期:2004-06-11
DOI:
中文关键词:  外排序  桶排序  多路归并  分发策略  抽样分点  PennySort
英文关键词:external sort  bucket sort  multi-line merging  distributing scheme  sample-separators  PennySort
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60223004,60321002,60303005(国家自然科学基金)
作者单位
杨磊 清华大学,计算机科学与技术系,北京,100084 
黄辉 中联绿盟信息技术(北京)有限公司,开发部,北京,100089 
宋涛 清华大学,计算机科学与技术系,北京,100084 
摘要点击次数: 2654
全文下载次数: 2979
中文摘要:
      计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利