最近在做基于Android的公交查询系统的过程中,遇到一个很棘手的问题:换乘算法效率低。在直达查询和一次换乘查询的时候,问题体现的还不是很明显,能够在1s之内查询出乘车方案,而当进行二次查询的时候,基本要等一两分钟才能查询出换乘方案,这对于公交查询系统是绝对无法容忍的。于是找了大量的关于公交换乘算法方面的论文和资料进行研究,发现大多治标不治本,没有从根本上解决公交换乘算法效率低下的问题。公交换乘算法主要有以下三种思路:
目前成都创新互联已为上千余家的企业提供了网站建设、域名、网站空间、网站托管、服务器托管、企业网站设计、怀远网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。1)基于数据库的查询;
2)采用Dijkstra或者Floyd算法或者改进的Dijkstra算法;
3)基于矩阵的运算;
由于在做这个系统之前就想过这个问题,是采用Dijkstra算法、矩阵运算还是基于数据库的查询。仔细分析之后还是选择了基于数据库的查询,因为对于大中型城市的公交网络,Dijkstra算法和矩阵运算根本不适用,尤其还是基于Android系统的公交查询系统(离线查询系统),举个例子,像成都市的公交网络系统有将近500条公交线路,5000个公交站点,如果采用矩阵运算或者Dijkstra算法的话,就只是直达矩阵就得有5000*5000=25000000个数据,若数据采用int类型保存,则该矩阵得占用25000000*4/(1024*1024*8)=12M的内存空间,这个数据对于移动设备来说想而知,是不可取的办法。因此最后采用了基于数据库查询的方案。
在我的数据库中有两张表:cnbusw(线路表),cnbus(站点线路表)
cnbusw的字段:
id:线路编号,busw:线路名称,shijian:起始站和起始时间描述;
cnbus的字段:
zhan:站点名,xid:对应的线路编号,pm:在该线路中的位置,kind:线路类型(去程or返程or环形路线)
后来发现在进行一次换乘查询的时候需要直达站点信息,因此添加了一个视图direct
direct的字段:
start:起始站,end:终点站,route:对应的线路编号,stopcount:两站之间的站点数
在数据库中进行测试了一下:
1)直达方案的话,直接在direct中进行查询:
比如下面一条sql查询语句:
select * from direct where start='磨子桥' and end='春熙路南口'
查询耗时:119.05ms
2)一次换乘查询方案,通过direct的自连接进行查询:
比如下面一条sql查询语句:
select s1.start as start,s1.route as route1,s1.end as zhuan,s2.route as route2, s2.end as end,s1.stopcount as count1,s2.stopcount as count2,(s1.stopcount+s2.stopcount) as stopcount from direct s1,direct s2 where s1.start='崔家店' and s2.end='磨子桥' and s1.end=s2.start and s1.route!=s2.route order by (s1.stopcount+s2.stopcount)
查询耗时:415.32ms
上述查询时间都在能够接受的范围之内,然后我很自然地按照上面的思路写出了三次换乘的sql查询语句,结果在查询时发现等了一分钟还没等出结果,并且sqlite可视化管理工具界面卡死了,这个很明显地告诉我二次换乘直接使用这样的sql语句是绝对不可行的,于是我想了一些办法,比如:两次换乘相当于是A->B->C->D,那么先查询经过站点D的线路中站点序号比D小的站点集合U,然后就相当于查询A到U集合中所有站点的一次换乘查询,这样就方便了,但是用sql语句查询了一下,一般U集合的大小都在400左右,然后要进行400次一次换乘查询,耗时400ms*400=160000ms=160s,怎么也得2分多钟,显然不可取。在陷入了这样的僵局之后,想了很久没想到办法,因为数据库里面的数据量很大,简单地对sql语句进行改进无法解决根本性问题。只有从数据库本身着手,于是想到了索引,以前上数据库课程的时候,老师提到过索引对于大量数据查询的时候效率提升的很明显,于是就尝试了一下,发现查询耗时一下减少了很多。在建立索引的过程中,原本想在视图上建立索引,发现似乎sqlite不支持在视图上创建索引,于是删除了direct视图,建立了direct直达表,在建立索引的时候,考虑是建立多列索引还是单列索引,分析一次换乘查询发现要将start,end,route这三列同时作为查询条件,并且要对stopcount进行排序,因此选择创建多列索引:
create index directindex on direct(start,end,route,stopcount)
在创建索引之后,重新将上面的一次换乘查询语句执行了一次,耗时:5.59ms,查询速度提升了将近80倍,然后又将直达查询语句执行了一次,耗时0.49ms,也明显提升了不少。然后按照一次换乘的思路写出了二次换乘的sql语句进行执行,
select s1.start as start,s1.xid as route1,s1.end as zhuan1,s2.xid as route2 , s2.end as zhuan2,s3.xid as route3,s3.end as end,s1.stopcount,s2.stopcount,s3.stopcount, (s1.stopcount+s2.stopcount+s3.stopcount) from direct s1,direct s2,direct s3 where s1.start='川大路黄河路口' and s3.end='春熙路南口' and s1.end=s2.start and s2.end=s3.start and s1.xid!=s2.xid and s2.xid!=s3.xid order by s1.stopcount+s2.stopcount+s3.stopcount
耗时411.15ms,很好地解决查询效率低下的问题,从这里可以看出,在数据量很大的情况,建立索引和没有索引的区别简直是天壤之别,适当地建立索引能够使查询速度提升很大,关于索引的相关问题准备在后面进行进一步学习和研究。
创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。
网页题目:数据库查询性能优化之利器—索引(一)-创新互联
当前链接:http://lswzjz.com/article/ddcceg.html