基于Bucket Sort的快速属性约简算法 被引量：10

1

作者 蒋瑜 刘胤田 李超 《控制与决策》 EI CSCD 北大核心 2011年第2期207-212,共6页

利用桶排序思想设计了一个求解U/C的算法,其时间复杂度降为O(∣C∣∣U∣).由此,给出一种无需求解正域便能判断正域是否变化的方法.基于以上方法,提出一种快速属性约简算法.该算法的求解策略是在每次迭代过程中求解决策表相对核,如果在... 利用桶排序思想设计了一个求解U/C的算法,其时间复杂度降为O(∣C∣∣U∣).由此,给出一种无需求解正域便能判断正域是否变化的方法.基于以上方法,提出一种快速属性约简算法.该算法的求解策略是在每次迭代过程中求解决策表相对核,如果在某次迭代过程中找不到这样的核属性,则任意排除一个条件属性.最后通过实验分析了该算法在最坏情况下的时间复杂性,其复杂性降为O(∣C∣2∣U/C∣). 展开更多

关键词 粗糙集 正区域 属性约简 桶排序

原文传递

一种最短路径射线追踪的快速算法 被引量：65

2

作者 张美根 程冰洁 +1 位作者 李小凡 王妙月 《地球物理学报》 SCIE EI CAS CSCD 北大核心 2006年第5期1467-1474,共8页

为提高最短路径射线追踪的精度,需要增加模型的剖分网格和离散节点,并增加子波传播方向,或者采用其他方法改善计算结果,这些处理会带来大量的额外计算.本文的快速算法改进了波前点的管理和子波传播的计算这两项耗时的工作,较大幅度地提... 为提高最短路径射线追踪的精度,需要增加模型的剖分网格和离散节点,并增加子波传播方向,或者采用其他方法改善计算结果,这些处理会带来大量的额外计算.本文的快速算法改进了波前点的管理和子波传播的计算这两项耗时的工作,较大幅度地提高了传统算法的效率.在波前点的管理上,采用按时间步划分区间的方法,实现了波前点的桶排序管理,其效率高于传统方法中常用的堆排序算法.在子波传播的计算上,利用斯奈尔定律,同时参考来自邻近节点的波的走时,来限定当前子波传播的有效区域,排除大量不需要计算的子波传播方向.模型实算表明,本文快速算法的计算速度是传统方法的几倍至十多倍. 展开更多

关键词 最短路径射线追踪 全局最小走时 斯奈尔定律 桶排序

在线阅读 下载PDF 职称材料

按字节桶分配链接排序法 被引量：15

3

作者 杨大顺 陶明华 +1 位作者 顾芸瑛 薛峰 《计算机研究与发展》 EI CSCD 北大核心 1996年第2期132-139,共8页

本文准备提出一种谓之按字节桶分配链接的新排序方法。给出排序算法、流程图和用Ｃ语言编写程序进行实验的结果。算法分析和实验结果都表明，该排序方法的时间复杂性为Ｏ（Ｎ）且与数据的分布情况无关，附加存储开销为（Ｎ＋５１２）ε... 本文准备提出一种谓之按字节桶分配链接的新排序方法。给出排序算法、流程图和用Ｃ语言编写程序进行实验的结果。算法分析和实验结果都表明，该排序方法的时间复杂性为Ｏ（Ｎ）且与数据的分布情况无关，附加存储开销为（Ｎ＋５１２）ε（其中ε是一个键接场所需空间的大小）［１］。该排序方法不仅在速度上明显快于快速排序法，而且在非均匀分布数据的情况下也明显快于桶排序法。 展开更多

关键词 排序 桶排序 链接排序 字节

在线阅读 下载PDF 职称材料

基于数组的桶排序算法 被引量：13

4

作者 杨磊 宋涛 《计算机研究与发展》 EI CSCD 北大核心 2007年第2期341-347,共7页

经典桶排序算法以链表形式实现“桶”,处理均匀数据效率很高,是O(N)算法.但对极不均匀数据则退化成低效的O(N2)插入排序.讨论了记录携带附加数据的计数排序算法,将“桶”实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许... 经典桶排序算法以链表形式实现“桶”,处理均匀数据效率很高,是O(N)算法.但对极不均匀数据则退化成低效的O(N2)插入排序.讨论了记录携带附加数据的计数排序算法,将“桶”实现为顺序数组,避免链表的动态内存分配直接提高算法效率,并允许快排等O(NlogN)算法处理桶内数据.对均匀数据仍然保持O(N)时间复杂度,对极端不均匀数据则只退化为O(NlogN)的原算法.对一般非均匀数据,证明数组桶排序算法总体性能高于经典算法.均匀数据实验表明,桶排序算法明显优于Lin-ux下标准qsort系统调用,且数组桶排序算法效率更高.而在非均匀的正态数据实验中数组桶算法性能下降明显小于经典桶排序,总体效率仍然优于qsort的直接应用. 展开更多

关键词 复杂度 排序算法 计数排序 桶排序 快速排序 Pennysort

在线阅读 下载PDF 职称材料

基于桶内动态融合的透明现象的高效绘制 被引量：4

5

作者 刘芳 黄梦成 +1 位作者 刘学慧 吴恩华 《计算机辅助设计与图形学学报》 EI CSCD 北大核心 2010年第3期382-387,共6页

基于桶排序的顺序独立透明现象绘制算法,采用桶排序原理将投影收集到同一个像素上的多个片元并排序,当发生桶内片元冲突时会产生错误的绘制结果.为此,提出一种基于桶内动态融合的透明现象的高效绘制算法.此算法采用桶内动态融合和并发读... 基于桶排序的顺序独立透明现象绘制算法,采用桶排序原理将投影收集到同一个像素上的多个片元并排序,当发生桶内片元冲突时会产生错误的绘制结果.为此,提出一种基于桶内动态融合的透明现象的高效绘制算法.此算法采用桶内动态融合和并发读/写的方法逐一融合落入同一个桶内的所有片元,并在后处理中按从前向后的顺序融合各个桶内的颜色值.由于同时发生桶内片元冲突和读/写冲突的概率非常小,因而可以大大提高绘制结果的准确性.实验结果表明,与基于桶排序的绘制算法相比,采用文中算法可以更准确地绘制场景,生成与真实结果非常相近的绘制效果,同时算法的效率基本保持不变. 展开更多

关键词 GPU 多渲染目标缓存 最大/最小融合 顺序独立的透明现象 深度剥离 桶排序

在线阅读 下载PDF 职称材料

二次链接桶排序法 被引量：6

6

作者 杨大顺 陶明华 +1 位作者 丁青 顾芸瑛 《计算机研究与发展》 EI CSCD 北大核心 1996年第12期881-886,共6页

本文进一步研究了桶排序法［１］，提出了适用于非均匀分布数据的高效率的二次链接桶排序法。本文是文献［１］中桶排序的推广。

关键词 排序 桶排序 二次链拉桶排序

在线阅读 下载PDF 职称材料

基于排序预处理的等高线提取算法 被引量：7

7

作者 王涛 刘纪平 毋河海 《测绘学报》 EI CSCD 北大核心 2006年第4期390-394,共5页

从规则高程格网中自动提取等高线是地理信息系统以及计算机制图的基本功能。针对当前高程格网数据的海量性,在以往工作的基础上提出了基于常规顺序索引和桶式索引的等高线提取算法。在具体实现中与以往工作提出的基于区间树的算法进行... 从规则高程格网中自动提取等高线是地理信息系统以及计算机制图的基本功能。针对当前高程格网数据的海量性,在以往工作的基础上提出了基于常规顺序索引和桶式索引的等高线提取算法。在具体实现中与以往工作提出的基于区间树的算法进行了详细的效率比较,认为桶式索引在预处理效率、查询效率和占用空间等各方面具有较大优势。最后给出了进一步工作的内容。 展开更多

关键词 规则高程格网 等高线 顺序索引 桶式索引 算法

在线阅读 下载PDF 职称材料

桶外排序算法的抽样分点分发策略 被引量：5

8

作者 杨磊 黄辉 宋涛 《软件学报》 EI CSCD 北大核心 2005年第5期643-651,共9页

计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以... 计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军. 展开更多

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

在线阅读 下载PDF 职称材料

直线优化A^＊算法在最短路径问题中的改进与实现 被引量：7

9

作者 王海梅 周献中 《工程图学学报》 CSCD 北大核心 2009年第6期121-126,共6页

最短路径算法的效率是汽车实时导航、动态路径规划等应用领域普遍关注和迫切需要解决的问题。在深入分析经典Dijkstra最短路径算法的基础上,从数据结构和搜索策略两方面对算法进行了改进,采用存储桶排序方式,提出了带启发因子的直线优... 最短路径算法的效率是汽车实时导航、动态路径规划等应用领域普遍关注和迫切需要解决的问题。在深入分析经典Dijkstra最短路径算法的基础上,从数据结构和搜索策略两方面对算法进行了改进,采用存储桶排序方式,提出了带启发因子的直线优化A*算法。实验结果表明改进的算法具有较高的稳定性和效率。 展开更多

关键词 计算机应用 最短路径 直线优化A*算法 存储桶排序

在线阅读 下载PDF 职称材料

基于桶排序和电压离散度阈值的MMC子模块电压均衡算法 被引量：7

10

作者 周登波 宋述波 +1 位作者 周勇 陆启凡 《电网与清洁能源》 北大核心 2022年第9期105-111,共7页

传统的MMC-HVDC子模块电压均衡冒泡排序算法存在时间复杂度高、子模块投切频繁的缺点。该文提出了一种结合桶排序算法与子模块电容电压离散度阈值的MMCHVDC子模块电容电压平衡算法。引入电压离散度阈值,将当前周期的电容电压序列与阈值... 传统的MMC-HVDC子模块电压均衡冒泡排序算法存在时间复杂度高、子模块投切频繁的缺点。该文提出了一种结合桶排序算法与子模块电容电压离散度阈值的MMCHVDC子模块电容电压平衡算法。引入电压离散度阈值,将当前周期的电容电压序列与阈值进行对比,形成高压、中压、低压3组;根据桶排序的思路对3组电压序列进行区间分割;依据桥臂电流方向确定不同区间子模块的投切次序。最后通过MATLAB和PSCAD/EMTDC进行仿真,验证了所提算法在降低时间复杂度和功率模块开关频率上的有效性。 展开更多

关键词 模块化多电平换流器 电压均衡算法 桶排序 电压离散度阈值 开关频率

在线阅读 下载PDF 职称材料

一种快速属性核求解算法 被引量：3

11

作者 蒋瑜 王嘉昀 《计算机工程与应用》 CSCD 北大核心 2011年第26期53-54,61,共3页

在RoughSet理论中,计算属性核是最重要的计算之一。以桶排序的思想设计了一个新的求解U/C的算法,其时间复杂度被降为O(|C||U|)。基于此,提出了一个新的求核算法,其时间复杂度被降为O(|C|2|U|)。通过实验证明了求核算法的高效性。

关键词 粗糙集 正区域 属性核 桶排序

在线阅读 下载PDF 职称材料

从规则高程格网中提取等高线的优化算法研究 被引量：5

12

作者 王涛 雷蓉 《地理信息世界》 2006年第1期39-44,48,共7页

从规则高程格网中提取等高线的算法是机助制图和GIS中非常重要的组成部分。本文针对当前高程格网数据的海量性,以提高效率为目的,对该算法进行了优化。将等高线提取算法分为起点确定和内插穿行两个阶段,对于第一个阶段的处理,提出基于... 从规则高程格网中提取等高线的算法是机助制图和GIS中非常重要的组成部分。本文针对当前高程格网数据的海量性,以提高效率为目的,对该算法进行了优化。将等高线提取算法分为起点确定和内插穿行两个阶段,对于第一个阶段的处理,提出基于区间树和顺序索引查找等高线起始点的算法,较大地改善了整体效率;同时,在顾及数字环境下等高线表达特性的基础上,设计的相关策略能够保证提取的等高线具有一致的方向信息。 展开更多

关键词 规则高程格网 等高线 区间树 桶式索引 算法

在线阅读 下载PDF 职称材料

城市交通最优路径规划仿真研究 被引量：3

13

作者 刘智琦 李春贵 《计算机仿真》 CSCD 北大核心 2011年第7期349-352,共4页

研究城市交通最优路径规划问题,由于城市交通网复杂,增加了规划的难度,传统的最优路径规划算法没有考虑城市道路网络中的交通限制问题,更忽略了车辆在道路交叉口转向延误的时间,不符合城市交通的实际情况。为了解决上述问题,首先建立了... 研究城市交通最优路径规划问题,由于城市交通网复杂,增加了规划的难度,传统的最优路径规划算法没有考虑城市道路网络中的交通限制问题,更忽略了车辆在道路交叉口转向延误的时间,不符合城市交通的实际情况。为了解决上述问题,首先建立了一个城市路网交通模型。然后运用线性规划方法建立最优路径规划问题的线性规划模型。最后采用桶排序算法对狄杰斯特拉算法进行优化,得到一个新的最优路径规划算法,对线性规划模型进行求解。仿真结果证明,利用算法搜索得到的最优路径更加符合实际的路网情况,为设计提供了理论依据。 展开更多

关键词 最优路径规划 路网交通模型 线性规划 狄杰斯特拉算法 桶排序算法

在线阅读 下载PDF 职称材料

显式有限元中的一种并行接触算法 被引量：1

14

作者 白小勇 何颖波 陈成军 《计算物理》 CSCD 北大核心 2011年第3期341-346,共6页

开发一种显式非线性有限元分析中的并行接触算法.基于区域分割技术将桶排序全局搜索方法并行化,各处理器通过桶编号向量检测相互交叠及潜在的点-面接触对.根据数据通信的特点将接触对分为三类,对各类接触对分别设计通信策略.数值算例表... 开发一种显式非线性有限元分析中的并行接触算法.基于区域分割技术将桶排序全局搜索方法并行化,各处理器通过桶编号向量检测相互交叠及潜在的点-面接触对.根据数据通信的特点将接触对分为三类,对各类接触对分别设计通信策略.数值算例表明,并行算法具有较高的加速比、并行效率及良好的可扩展性. 展开更多

关键词 显式有限元 区域分割 并行接触 桶排序

在线阅读 下载PDF 职称材料

多核计算环境下的桶排序算法优化 被引量：1

15

作者 康志辉 《长春师范大学学报》 2015年第8期39-43,共5页

经典并行桶排序算法的时间复杂度为O((n/p)*log(n/p)),其前提要求原始数据是在一个已知的间隔内均匀分布时,才有良好的效果。对非均匀分布的数据进行排序,最坏排序时间为O(n*logn),即退化成为串行的快速排序算法。为了解决该算法对原始... 经典并行桶排序算法的时间复杂度为O((n/p)*log(n/p)),其前提要求原始数据是在一个已知的间隔内均匀分布时,才有良好的效果。对非均匀分布的数据进行排序,最坏排序时间为O(n*logn),即退化成为串行的快速排序算法。为了解决该算法对原始数据的约束,本文提出一种改进的并行桶排序算法,对原始数据的划分不是根据数据在已知间隔中的位置,而是根据数据在序列上的位置划分数据。引入一种新的2-路归并算法,并且运用了流水线思想,设置任意分布数据排序的时间复杂度为O((n/p)*log(n/p))。 展开更多

关键词 桶排序 归并排序 流水线技术 并行算法

在线阅读 下载PDF 职称材料

线对象邻接关系快速重构算法

16

作者 廖名学 范植华 何晓新 《计算机应用》 CSCD 北大核心 2008年第1期245-247,共3页

给定向量化坐标，计算n个线对象两两邻接关系，普通算法时间复杂度为O（n＊n）；理论最好时间复杂度为O（C），其中C是邻接关系的基数。基于散列桶，给出了建立线对象邻接关系的快速算法，其平均时间复杂度为O（n（1＋1／r）），r为算... 给定向量化坐标，计算n个线对象两两邻接关系，普通算法时间复杂度为O（n＊n）；理论最好时间复杂度为O（C），其中C是邻接关系的基数。基于散列桶，给出了建立线对象邻接关系的快速算法，其平均时间复杂度为O（n（1＋1／r）），r为算法分配的桶数量与n的比，空间复杂度为O（n）。证明了若不允许使用额外空间，则不可能使用排序算法解决该问题；给出了允许使用额外空间条件下的两遍排序算法，时间复杂度为O（n（1bn＋1＋2／r））。应用表明快速算法比普通算法速度提高1—3个数量级。 展开更多

关键词 线对象 邻接关系 桶排序 算法分析

在线阅读 下载PDF 职称材料

电磁环境多层等值面融合绘制研究

17

作者 胡华全 杨超 吴玲达 《计算机工程与应用》 CSCD 北大核心 2011年第35期206-209,共4页

针对电磁环境三维体数据中提取出的多层等值面,根据交互绘制速率与绘制质量的不同要求,提出分层伪排序融合绘制方法和改进Depth Peeling融合绘制方法。前者实现了多层等值面的近似排序,采用逐像素着色增强边界轮廓,绘制速率快,适合需要... 针对电磁环境三维体数据中提取出的多层等值面,根据交互绘制速率与绘制质量的不同要求,提出分层伪排序融合绘制方法和改进Depth Peeling融合绘制方法。前者实现了多层等值面的近似排序,采用逐像素着色增强边界轮廓,绘制速率快,适合需要快速绘制而质量要求不高的场合;后者通过引入Slicemap技术,解决了多层等值面片元分布不均匀的问题,并利用多遍绘制融合方法,提高了绘制复杂等值面的能力,从可视化效果看,提高了绘制质量,绘制效率也得到了保证。 展开更多

关键词 图形处理器 多目标渲染目标缓存 深度剥离 桶排序

在线阅读 下载PDF 职称材料

线性时间复杂度排序算法研究及应用 被引量：1

18

作者 郭威 《软件导刊》 2013年第6期35-37,共3页

算法在程序设计中起着至关重要的作用,一个好的算法可以让程序变得高效。排序作为数据处理最基本的工作之一,在程序中需要大量使用。常见的几种排序算法的平均时间复杂度最优为O(nlog2n),为从根本上提高程序的运行效率,对能够在线性时... 算法在程序设计中起着至关重要的作用,一个好的算法可以让程序变得高效。排序作为数据处理最基本的工作之一,在程序中需要大量使用。常见的几种排序算法的平均时间复杂度最优为O(nlog2n),为从根本上提高程序的运行效率,对能够在线性时间解决数据排序的算法进行了研究,并在实际问题中对桶排序算法加以了应用。 展开更多

关键词 排序算法 线性时间复杂度 基数排序 桶排序

在线阅读 下载PDF 职称材料

结合数据概率分布的桶算法

19

作者 周建钦 赵志远 《曲阜师范大学学报（自然科学版）》 CAS 1992年第1期26-28,74,共4页

本文应用数据的概率分布,提出并分析了分布桶算法.

关键词 排序 查找 桶算法 数据 分布桶算法 概率分布

在线阅读 下载PDF 职称材料

面向大规模场景的多片元效果高效绘制 被引量：3

20

作者 周果 朱登明 王兆其 《计算机学报》 EI CSCD 北大核心 2017年第11期2606-2618,共13页

多片元效果具有实时透明等重要应用,它需要每个像素按深度顺序遍历对应的所有片元.深度剥离法将场景重复绘制多次来满足这个需求,故对显存带宽提出了很高的要求.该文针对大规模场景图元分布稀疏的特点,使用类体素八叉树在物体空间将场... 多片元效果具有实时透明等重要应用,它需要每个像素按深度顺序遍历对应的所有片元.深度剥离法将场景重复绘制多次来满足这个需求,故对显存带宽提出了很高的要求.该文针对大规模场景图元分布稀疏的特点,使用类体素八叉树在物体空间将场景近似剖分以减少图元读取总量.这允许场景能够按可见性顺序被分块加载、精确剖分和逐个绘制:通过光栅化对应的八叉树网格构造深度桶列表,在屏幕空间将场景块与网格布尔求交;通过为整个场景构造块的深度直方图,在剥取时利用它来避免硬件遮挡查询操作.由于为每块采取了不同的迭代次数,该文的两阶段剖分方法能够适应物体空间变化的深度复杂度.由于不依赖于面片的邻接信息,该文方法能够支持非流形网格和外存绘制.相比已有工作,该文方法在每次剥取一层时绘制效率有30%以上的提升. 展开更多

关键词 八叉树 体素化 深度剥离 桶排序 构造实体几何

在线阅读 下载PDF 职称材料