借力数据结构

做实时公交查询服务时,最重要的能够实时跟踪每一辆车的时空信息,并结合静态数据,准确刻画出一个城市每一时刻所有公交线路的状态。由于基础数据只有线路,站点这样的信息,做时间预测,位置计算便只能依赖这些信息。比较关键的思路大致如下:

位置计算

S1         S2        S3             S4                 S5            S6            S7 
                               P

为了得到P的位置,需要利用一个评价公式: 假设P到前一站距离Pre, 到后一站距离Next,两站之间距离Between,有如下公式:

   Cost =  Pre + Next - Between

我们认为使Cost取值最小的两个站即为P所在位置的前后站。

时间预测

比如我们要估算P到S7站点的到站时间,可以取该车次所有车最近5趟S3到S7的时间 T_AVG,所以预估时间公式为:

T_ESTIMATE = Distance(P->S4-> ... ->S7) / Distance(S3->S4-> .... -> S7)   *  T_AVG

BUT,现在通过历史数据分析,提取出了线路的轨迹信息,就是除了站点以外,还有很多有序的轨迹点可以代表线路。这些点带来的好处是: 两个站之间的轨迹是曲线(甚至环形都是很常见的)的话,如果只有站点,连出的轨迹就是一条直线段,模拟效果很差;而点多了以后,几乎就可以还原出真实的线路轨迹。

在考虑如何利用这些点的时候,就碰到一个设计权衡的问题:

1. 不把站点插入轨迹点集里面

得到的轨迹点集合已经可以很好模拟真实情况了,而站点信息(主要是经纬度)由于是人工采集的,会存在一些偏差,把站点插入轨迹点集之后的模拟效果反而会变差(抽样发现会出现迂回的情况)。但是仍然需要记录每个轨迹点的位置信息(位于哪两站),设计轨迹点数据结构如下:

type GeoPoint  struct {
	lat	float
	lng	float
}

type TrackPoint struct {
	GeoPoint
	preStationIndex	int  //前一站
	nextStationIndex	int  //后一站
	index	int   //在点集中的次序
}

这时进行位置计算,就需要用轨迹点去计算: 先算出在哪两个点之间,然后根据前后点的关系,计算出在哪两个站点之间,这时计算比较复杂,可以分成如下情况:

  • 前后点没有跨站

      /**
        *    S1  p1 . . .   pre  cur  next   . .  p2  S2 . . . S3
        *  
        *  Path(S1, cur) =  Dis(cur, pre) + Σ PointDis(p1-pre) + Dis(S1, p1)
        *  Path(S2, cur) =  Dis(cur, next) + Σ PointDis(next-p2) + Dis(p2, S2)
        */
    
  • 前后点跨站

    //    case1:  S1  . . .   pre   cur  S2   next  . . . . S3
    

    // case2: S1 … pre S2 cur next … . S3

为了区分这两种情况,还要利用上面的Cost函数,计算cur到底在pre-S2,还是S2-next,计算过程十分繁琐。 时间预测的计算有过之而无不及。

2. 把站点插入轨迹集合里面

如果把站点插入轨迹集合里面,计算位置以及预测时间的过程就会简化许多,这时就需要给TrackPoint增加类型信息进行区分(将来可能会加入红绿灯,拐点等类型) :

const ( 
    Ordinary =  iota
    TurnPoint
    Station
    TrafficLight 
)

type Kind int

type TrackPoint struct {
	GeoPoint
	preStationIndex	int  //前一站
	nextStationIndex	int  //后一站
	index	int   //在点集中的次序
	kind	Kind //点类型
}

由于站点也是轨迹集合的一员,位置计算时就不存在是否跨站问题了, 时间预测时到两站的距离也只需要计算两部分。

本来为了使轨迹信息不致于受到站点的干扰,采用了第一种设计。但实现位置计算以及时间预测时,明显感觉各种计算都要围绕站点来进行,即使轨迹序列里不加站点,在其他地方还是会受到钳制。改用第二种设计之后,很多计算就变得自然许多,简洁许多,省了很多不必要的弯路。 借用《The Design of Design》的一句话就是:



The viewpoint is that of an engineer, focused on utility and effctiveness
but also efficiency and elegance.

Tags// ,