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

1

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

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

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

下载PDF 职称材料

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

2

作者 杨磊 宋涛 《计算机研究与发展》 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 职称材料

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

3

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

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

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

原文传递

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

4

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

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

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

下载PDF 职称材料

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

5

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

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

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

下载PDF 职称材料

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

6

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

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

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

下载PDF 职称材料

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

7

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

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

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

下载PDF 职称材料

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

8

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

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

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

下载PDF 职称材料

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

9

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

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

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

下载PDF 职称材料

基于桶排序的EDF调度算法优化 被引量：2

10

作者 于国龙 张明富 《兰州理工大学学报》 CAS 北大核心 2013年第4期110-113,共4页

EDF调度算法在系统过载的情况下,就不能有效地实时调度系统中的所有任务,使任务的截止期错失率非常高.利用桶排序算法,将实时系统中任务按不同优先级等级分组排序,使得高优先级等级任务组中的任务优先被调度执行;对于其他低优先级等级... EDF调度算法在系统过载的情况下,就不能有效地实时调度系统中的所有任务,使任务的截止期错失率非常高.利用桶排序算法,将实时系统中任务按不同优先级等级分组排序,使得高优先级等级任务组中的任务优先被调度执行;对于其他低优先级等级任务组中的任务,根据资源利用率动态调整它们的优先级等级,从而降低实时系统的任务截止期错失率.仿真实验表明,优化后的EDF调度算法的截止期错失率,明显比优化前低,说明基于桶排序的EDF调度算法的实时任务截止期错失率比EDF调度算法低. 展开更多

关键词 嵌入式系统 桶排序 调度算法 优先级 错失率

下载PDF 职称材料

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

11

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

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

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

下载PDF 职称材料

基于切比雪夫有理逼近方法的蒙特卡罗燃耗计算研究与验证 被引量：1

12

作者 范文玎 孙光耀 +2 位作者 张彬航 陈锐 郝丽娟 《核技术》 CAS CSCD 北大核心 2016年第4期45-50,共6页

燃耗计算在反应堆设计、分析研究中起着重要作用。相比于传统点燃耗算法,切比雪夫有理逼近方法(Chebyshev rational approximation method,CRAM)具有计算速度快、精度高的优点。基于超级蒙特卡罗核计算仿真软件系统Super MC(Super Monte... 燃耗计算在反应堆设计、分析研究中起着重要作用。相比于传统点燃耗算法,切比雪夫有理逼近方法(Chebyshev rational approximation method,CRAM)具有计算速度快、精度高的优点。基于超级蒙特卡罗核计算仿真软件系统Super MC(Super Monte Carlo Simulation Program for Nuclear and Radiation Process),采用切比雪夫有理逼近方法和桶排序能量查找方法,进行了蒙特卡罗燃耗计算的初步研究与验证。通过燃料棒燃耗例题以及IAEA-ADS(International Atomic Energy Agency-Accelerator Driven Systems)国际基准题,初步验证了该燃耗计算方法的正确性,且IAEA-ADS基准题测试表明,与统一能量网格方法相比,桶排序能量查找方法在保证了计算效率的同时减少了内存开销。 展开更多

关键词 燃耗 蒙特卡罗 切比雪夫有理逼近方法 桶排序

原文传递

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

13

作者 康志辉 《长春师范大学学报》 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 职称材料

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

14

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

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

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

下载PDF 职称材料

并行多层快速多极子算法最细层数据的建立 被引量：1

15

作者 郭海林 胡悦 +1 位作者 童维勤 支小莉 《上海大学学报（自然科学版）》 CAS CSCD 北大核心 2009年第4期421-425,共5页

分布树最细层数据的建立是并行多层快速多极子算法(MLFMA)的基础.最细层数据分布均匀与否,会影响到后续整个算法的负载平衡及其并行效率.研究了最细层数据的建立方法,提出采用并行正则采样排序算法来代替众多文献所推荐的并行桶排序算法... 分布树最细层数据的建立是并行多层快速多极子算法(MLFMA)的基础.最细层数据分布均匀与否,会影响到后续整个算法的负载平衡及其并行效率.研究了最细层数据的建立方法,提出采用并行正则采样排序算法来代替众多文献所推荐的并行桶排序算法,以此来建立分布树的最细层数据.针对多种常见的散射体在不同处理器数下的实验结果表明,在大多数情况下,改进后的算法较原算法性能有较为明显的提高. 展开更多

关键词 多层快速多极子算法 分布树 并行正则采样排序 并行桶排序 消息传递接口

下载PDF 职称材料

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

16

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

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

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

下载PDF 职称材料