基于二分搜索Trie的IPv4/IPv6路由快速查找算法

提出了一种独特的基于前缀长度二分搜索Trie的IP路由查找算法,融合了基于前缀长度的二分查找算法和基于Trie的查找算法的优点,采用部分IP地址作为索引,避免了使用Hash函数,提高了路由查找速度和表项更新速度;支持路由表的动态更新;算法扩展性好,可满足IPv4和IPv6两种协议栈的OC-48(2.5Gbps)、OC-192(10Gbps)接口的线速路由查找。

一种查找算法的改进方法

折半查找算法是数据结构中有序序列查找中的一个重要算法,此算法在含有n个元素的有序序列中查找某一个元素时,最大循环比较次数为└log2n」+1.但是在很多情况下,查找之前有序序列分布的很多信息为已知,如当知道了有序序列中每相邻2个元素之差最大值的一个上界,就可以有比折半法更加有效的查找算法.以此改进的折半法查找性能明显优于原算法的查找.受序列分布的影响,其在最坏情况下查找一个元素的最大比较次数在1和└log2n」+1之间,明显优于折半查找.此方法在实际应用中可极大提高查找效率.

基于折半查找算法的研究与改进

折半查找算法是数据结构中有序序列查找中的一个重要算法,可以用比折半法改进的折半法查找性能,明显优于折半查找,在实际应用中可极大提高查找效率。

凸多边形窗口线裁剪的折半查找算法

在Skala算法基础上,提出了一个更加快速的线裁剪算法该算法将裁剪窗口分割成4条折线,依据折线的两个端点与被裁剪直线的位置关系,确定折线是否与直线相交;采用折半查找方法,快速确定与直线相交的窗口边界线,并求出交点位置与Cyrus Beck算法相比,该算法在乘除法次数和计算速度方面具有非常明显的优势。

一种计算航空发动机试车性能的算法

某型涡喷发动机试车需要根据试车测试数据利用标准性能曲线板绘制性能曲线,以确定发动机性能是否合格,这种方法往往具有较大的作图和读数误差。为此利用平面图形二维几何变换的模型,通过对标准性能曲线的平移和旋转来搜索满足条件的性能曲线,并自动计算出发动机的性能。采用枚举搜索法具有方法简单、编程容易的优点,但计算量非常大、搜索效率非常低。为此设计了一种枚举-二分混合搜索的算法,采用在Y方向上枚举、X方向直接平移,旋转过程采用二分搜索的方法,极大地提高了搜索效率,实现了性能曲线的计算。

快速更新IPv4/IPv6双栈路由查找算法与实现

IPv4/IPv6双栈核心路由器需要一体化高效路由查找.但常用的单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,这种与地址关联的排序操作影响表项的更新速度和路由查找流程的连续性.提出并实现了一种独特的对前缀范围对分搜索的IPv4/IPv6双栈一体化多步TCAM流水查找方法.突出特点是转发表不需排序、查找速率高、表项更新快、查表连续性好.可满足IPv4/IPv6双协议栈核心路由器OC-768(40Gbps)端口、48B包的线速转发.

足球竞猜选票问题的研究

研究了足球选票问题中选票的不同得分种数 ,得出结论为 86种 .提出了统计某一得分选票数量的两种算法 :折半查找统计算法、直接归类统计算法 ,并对这两种算法的运算效率进行了分析比较 .研究了选票得分的分布情况 .

CRL的一种改进方案

提出了一种改进的CRL方案,通过对CRL结构的改进,大大减少了证书用户查找撤销证书的时间。方案使用的基于排序的折半查找算法比较成熟,整体方案易于实现。