路由查找算法优化心得

    项目代码中有一个基础类库,用于解析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 条评论
登录 后参与评论

相关文章

来自专栏python3

python3--基础综合练习题

允许用户最多尝试3次,3次都没猜对的话,就直接退出,如果猜对了,打印恭喜信息并退出

1803
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-01总结概述,dos,功能键,path

1:计算机概述(了解) (1)计算机 (2)计算机硬件 (3)计算机软件 系统软件:window,linux,mac 应用软件:qq,yy,飞秋 (...

36413
来自专栏三木的博客

mysql数据库及django用户名启用中文的方法

mysql数据库启用中文 在mysql的配置文件/etc/my.cnf的[mysqld]下加入 character_set_server=utf8 Django...

2648
来自专栏小狼的世界

CoffeeScript学习笔记

CoffeeScript编程语言构建于Javascript之上,它可编译成高效JavaScript。可以在Web浏览器上,或者结合Node.js一类的技术构建服...

1161
来自专栏专注数据中心高性能网络技术研发

[Effective Modern C++(11&14)]Chapter 7: The Concurrency API

2065
来自专栏阮一峰的网络日志

PHP最佳实践

虽然名字叫《PHP最佳实践》,但是它主要谈的不是编程规则,而是PHP应用程序的合理架构。

2161
来自专栏林冠宏的技术文章

Golang, 以17个简短代码片段,切底弄懂 channel 基础

(原创出处:https://cloud.tencent.com/developer/user/1148436/activities) 前序:   因为打算自己搞...

3805
来自专栏Charlie's Road

<Solidity学习系列二>深入理解Solidity之二---Solidity源代码文件结构

版本Pragma 源文件可以(也应该)用所谓的版本注释来注释,以拒绝被编译为未来可能引入不兼容更改的编译器版本。 我们试图将这种变化保持在绝对最低限度,特别是引...

781
来自专栏依乐祝

.NET Core实战项目之CMS 第三章 入门篇-源码解析配置文件及依赖注入

上篇文章我给大家讲解了ASP.NET Core的概念及为什么使用它,接着带着你一步一步的配置了.NET Core的开发环境并创建了一个ASP.NET Core的...

892
来自专栏向治洪

MIDlet工作原理

题记 :  现在的J2ME用户已经是日益减少 , 开发也在转型! 无奈之下也不得不写下这系列文章来别了j2me ,也是对过去的一些总结吧!         ...

18310

扫码关注云+社区