专栏首页王亚昌的专栏路由查找算法优化心得

路由查找算法优化心得

    项目代码中有一个基础类库,用于解析client到server的路由配置文件,同时管理长连接。路由配置文件格式大致如下所示:

<info mod="1000"> <routetable> <route begin=0 end=499 ip="192.168.1.100" port="1800" /> <route begin=500 end=999 ip="192.168.1.101" port="1800" /> <routetable/>

    大概含义表示,路由算法是使用用户id%1000,然后看落到[begin, end]的对应区间,找到对应的ip和port即是对应的server信息。

   【当前方案】

    类库把路由信息和长连接对象保存在vector中,每一条route记录对应vector中一个结点,那上面的配置在vector共保存两条记录。

记录对应的结构体如下所示:

struct stRouteNode{ int modid; int begin; int end; string ip; int port; CServer obj; };

   类库初始化时,每读到一条route记录,就初始化一个stRouteNode对象,建立长连接并push_back到vector中。

   当上层请求一个uin对应的server时,首先根据uin%1000得到modid,再逐个和vector中的对象进行比较,看是否在对应的区间中。

   【改进方案】

   优化前的方案缺点十分明显,那就是顺序查找,并且每次查找要进行2次比较,最坏的效率是2o(n),改进方案有很多,我这里采用的方案是使用空间换时间的方式,底层存储仍然使用vector,但是查找使用下标直接索引的方法,以上面的路由配置方案为例,vector中保存1000条记录,其中0-499指向同一个server对象,这样即不会建立重复的长连接,又可以保证查找时o(1)的效率。这样记录对象的结构体调整如下:

struct stRouteNode{ string ip; int port; CServer *obj; };

    【总结】

    改进后效率提升了很多,性能测试,在vector中记录数到3000个的情况下,优化后方案的耗时约为优化前的1%,性能提升十分明显,由此可见算法优化对应系统性能提升的巨大影响,同时也给大家一点建议,一定要注意避免顺序查找,尽可能使用下标索引的方案,现阶段机器在的内存与cpu相比而言,cpu资源更加宝贵,而内存一般不太容易成为瓶颈(缓存或文件系统类除外),对于大的配置还可以使用文件映射的方式,因此,建议大家对于配置文件可以采用下标直接索引的方式,即使是使用map也不太推荐。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 对数据操作封装的一点心得

    在对数据进行操作时,可能需要读写name,于是我们写了一个接口,这个接口会实时更新缓存

    王亚昌
  • WinPcap在无线局域网下的使用

        最近在做网关方面的项目,用到了WinPcap开发库去获得数据帧,这个开发库功能很强大,但是在无线局域网环境下使用时有一些不同,下面就WinPcap的使用...

    王亚昌
  • 分布式消息队列浅析

    队列作为一种比较抽象的数据结构,在程序世界中被广泛的应用,而实现方式和形态也各式各样,有使用进程内堆栈实现的,如stl库中的queue;有基于管道、Shmem实...

    王亚昌
  • leetcode 27 Remove Element

    @坤的
  • Leetcode 152 Maximum Product Subarray

    Find the contiguous subarray within an array (containing at least one number) w...

    triplebee
  • Android事件处理

    为了实现回调机制的事件处理,Android为所有GUI组件提供了一些事件处理方法,以View为例,该类包含如下方法

    提莫队长
  • 华为2018年校园招聘机试题

    yesr
  • 算法原理系列:并查集

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Android性能优化实战之界面卡顿

    作者:红橙Darren https://www.jianshu.com/p/18bb507d6e62

    用户1269200
  • 「CF838B」 Diverging Directions

    给出一个n个点2n-2条边的有向图。n-1条指向远离根方向的边形成一棵树,还有n-1条从非根节点指向根节点的边。 q次操作,1修改第x条边权值为y,2询问,求...

    饶文津

扫码关注云+社区

领取腾讯云代金券