首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到17条相似文献,搜索用时 62 毫秒
1.
刘恒  李美安  苏萌 《计算机应用》2014,34(5):1263-1266
在分布式循环请求集长度最短时,针对请求集生成算法的时间复杂度和空间复杂度过高问题,提出了一种基于重复数的最短循环请求集生成算法。算法在基于循环松弛差集的思想上,以当前请求集差集允许的最大重复数作为判断条件,依次向请求集中添加元素。实验结果表明,系统节点数为70到90时,该算法在保证请求集长度最短,且空间复杂度为O(2N)的前提下,使得时间复杂度是穷搜方法的3.6E-03到6.8E-07,降低了最短循环请求集生成算法的时间复杂度。  相似文献   

2.
如何在保证请求集长度不显著增加的情况下使时间复杂度尽量减小,是对称分布式互斥请求集生成算法研究者必须解决的问题。通过动态增加初始化节点的方法,采用局部递归的方式设计了一种新的对称分布式互斥请求集生成算法。该算法能够保证请求集长度与其长度下限比较不会显著增加,而时间复杂度比WK算法及全局递归算法有显著下降。因此,通过对请求集本身特性的研究,能够部分解决请求集长度与请求集生成算法时间复杂度之间的矛盾。  相似文献   

3.
尹乾  罗运纶  胡小红  付新丽 《计算机学报》2005,28(11):1939-1942
研究有限域F(q)上任意给定长度的序列的最短线性递归长度的分布.对任意正整数n和0≤l≤n,计算出了长度为n、最短线性递归长度为l的序列个数,指出了对于固定长度为n的任意序列,其最短线性递归长度大部分情况下等于n/2或n/2+1,即其最短线性递归长度的分布一般都集中在长度的一半位置.  相似文献   

4.
在折半循环编码算法的基础上,提出了一种增加算法初始化节点数量和松弛正向差集的对称分布式互斥请求集生成算法,使算法的时间复杂度大幅度降低,而所生成的请求集长度仍然保持(2N)1/2~2N1/2之间。  相似文献   

5.
提出一种新的分布式互斥循环请求集生成算法。该算法采用折半加一与局部递归的方式,在不明显增加请求集长度的情况下,能至少降低WK算法50%的时间复杂度。在利用局部递归方式计算循环请求集时,如果系统节点数属于某分段的后半段,则设定其循环请求集长度下限为 +1。性能分析结果表明,该算法能够在规定时间内计算大规模分布式系统的循环请求集,具有较高的实用性。  相似文献   

6.
分析了在分布式高性能防火墙中两种常用的请求分配算法,在此基础上提出了最短响应时间优先调度算法。仿真表明,该算法具有很好的调度效果和很高的稳定性。  相似文献   

7.
一种新的分布式互斥请求集生成算法   总被引:4,自引:0,他引:4  
分布式互斥请求集的长度、对称性和生成的难易程度以及生成算法占用的空间及耗费的时间直接影响着基于该请求集的分布式互斥算法的消息复杂度、对称性和算法的应用规模。本文在基于循环编码的分布式互斥请求集生成算法的基础上,提出了一种增加算法初始化节点数量的对称分布式互斥请求集生成算法。其生成的请求集长度小于2N0.5,其时间复杂度也比基于循环编码的分布式互斥请求集生成算法小。因此,该算法较已有的分布式互斥请求集生成算法在性能上具有较大提高。  相似文献   

8.
在分布式系统中,各节点必须互斥地访问临界区.节点的请求集的长度决定了系统的效率、性能.虽然最优请求集的节点数最少(大约n),但已有的解决方案该类问题算法类似于穷举法,随着节点的增加,该方法变得不可计算.提出了一种快速的请求集生成算法,该算法以循环差集请求集生成算法的理论和贪心算法的基本思想为基础,在每次迭代的过程中,选出一个当前条件下最优的节点加入请求集.与其他的方法相比较,该方法能对任意给定的整数快速、有效地生成对称的请求集.本算法时间复杂度为O(n2),生成的请求集长度为n~2n.  相似文献   

9.
提出了一种基于递归最短生成树算法的H.264压缩域实时分割运动对象的算法.首先将从H.264编码端提取的运动矢量进行归一化、空间内插,得到稠密运动矢量场,再采用全局运动补偿技术抵消全局运动的影响,最后采用改进的"递归最短生成树"(RSST)算法对稠密运动矢量进行聚类,实现对运动对象的分割.实验结果表明,该算法对视频序列能实现较准确的分割.  相似文献   

10.
在折半循环编码算法的基础上,依据贪心策略对可纳入节点进行局部求最优的方式来生成请求集的算法,从而使算法的请求集长度下降了一个数量级,接近姨N。  相似文献   

11.
频繁项集挖掘算法   总被引:1,自引:0,他引:1  
在松弛循环差集的基础上,依据局部贪心策略对可纳入节点以局部求优的方式来生成请求集的算法,使算法的时间复杂度降低一个数量级,同时所生成的请求集长度仍然保持在2N2N,从而更有利于在通信中推广使用。  相似文献   

12.
基于分形递归算法的树木真实感绘制   总被引:8,自引:2,他引:8  
快速真实地模拟树在风中的摇曳一直是计算机图形学中的一个挑战性问题,作为自然场景的重要组成部分,树木的真实感模拟也得到人们的广泛重视.树木种类繁多,形态各异,复杂的结构使其无论在造形、存储还是在绘制上都存在着相当的困难.大多数园林设计软件很难构建模型参数可变的三维树.研究了一种简易的基于分形递归算法的建模方法,利用过程参数控制树的摇曳,使模型的真实感更强,变形计算更容易,得到了令人满意的实验效果.  相似文献   

13.
针对汇编语言程序非结构化的特点,提出了基于改进的Z路径覆盖策略的汇编语言程序结构测试方法和路径自动生成算法。该算法采用正则表达式来表示程序控制流结构,从控制流分段.正则表达式生成、路径片段生成和路径片段连接4个步骤完成了路径生成的过程,提出了矩阵递归算法MRA以解决路径片段连接问题。该算法能够生成覆盖在循环处执行循环体的0次、1次和2次循环的路径集,该路径集覆盖语句覆盖、判定覆盖和循环覆盖准则的同时,其路径数量又可以接受。  相似文献   

14.
武鹏  李美安 《计算机应用》2013,33(2):323-360
在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比,生成的请求集长度仍保持在2n^(1/2)的数量级。  相似文献   

15.
针对虚拟内窥镜中心路径提取算法时间效率不高的问题,通过改进边界距离变换,提出了中心路径的快速提取算法。首先建立最小距离场,在边界内推过程,仅扫描并处理与边界点面连接的点并对其设标记属性,每次向里剥离一层体素标记属性随之增加,直到对内部点集都置到边界的最小边界距离值(DFB);然后找到DFB值不小于其所有面邻接点DFB值的体素点,即3D局部最大值;最后用最短路径相连3D局部最大值,形成中心线。实验结果表明,改进的中心路径提取算法的时间效率较传统距离变换算法有很大提高。  相似文献   

16.
针对睡眠分期中样本不平衡问题,提出以最短路径为指标选取最优数据进行数据生成的思想,增加少数类样本的数量.基于Border-SMOTE算法,提出改进的iBorder-SMOTE睡眠数据生成算法.用密度峰值聚类算法确定待生成数据的簇类别区域,采用中心最短路径选取最优数据点进行数据生成,使用异变扰动方法对生成数据进行修正,保...  相似文献   

17.
We propose two new methods to label connected components based on iterative recursion: one directly labels an original binary image while the other labels the boundary voxels followed by one-pass labelling of non-boundary object voxels. The novelty of the proposed methods is a fast labelling of large datasets without stack overflow and a flexible trade-off between speed and memory. For each iterative recursion: (1) the original volume is scanned in the raster order and an initially unlabelled object voxel v is selected, (2) a sub-volume with a user-defined size is formed around the selected voxel v, (3) within this sub-volume all object voxels 26-connected to v are labelled using iterations; and (4) subsequent iterative recursions are initiated from those border object voxels of the sub-volume that are 26-connected to v. Our experiments show that the time-memory trade-off is that the decrease in the execution time by one-third requires the increase in memory size by 3 orders. This trade-off is controlled by the user by changing the size of the sub-volume. Experiments on large three-dimensional brain phantom datasets (362 × 432 × 362 voxels of 56 MB (megabytes)) show that the proposed methods are three times faster on the average (with the maximum speedup of 10) than the existing iterative methods based on label equivalences with less than 1 MB memory consumption. Moreover, our algorithms are applicable to any dimensional data and are less dependant on the geometric complexity of connected components.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号