请教一下老魏pc12306中的算法。

http://www.mitbbs.com/article_t/Programming/31465155.html

发信人: nanxiang7 (zz), 信区: Programming
标  题: 请教一下老魏pc12306中的算法。
发信站: BBS 未名空间站 (Sun Dec 27 04:54:29 2015, 美东)

放假，终于有时间run GDB，才对老魏的程序有些理解了。仍然有些疑问。想向老魏和
大家请教。

先陈述一下基本的理解：

TrainTicketMap 是关键的数据库，表征对应车次当前所有空座.  它是一个二维数组，
两个indices分别是起始站和（站数 - 1).  它的值是一个stack（由单向链实现）。
stack上每一元素对应一个座位的站次间的空座范围，表示此座位从该起始站开始数该
站数范围内是空的。该元素的next指针指向stack上下一个对应不同座位的元素。

在初始状态，每个座位从起始站0开始10站都空，所以这个二维数组只在index［0，9］
有非空stack，里面压了对应所有座位的3000个元素，座位1在最上。假设第一个请求是
起始站3站数1，则座位1从站3到站4被出票，该座位空座范围［起始站，站数－1］从［
0，9］变为［0，2］和［4，5］。所以，对这个二维数组的操作（reserve函数里）是
：座位1在index［0，9］stack上的元素被free回TicketPool，从TicketPool重新
allocate两个元素给座位1，分别压进在index［0，2］和［4，5］的stacks。

整个操作分两步：allocate(); reserve().

allocate() 在TrainTicketMap找覆盖所请求站次的空座范围。搜索范围是顺着预先设
定的SearchOffsets，从小到大。所用时间较大而且不定，只读而不修改在
TrainTicketMap。是非transaction部分。

reserve() 是transaction部分，修改TrainTicketMap，用时很少并且固定。

请问，上述理解对吗？

我有几个问题：

1. 对站数能scale吗？如果站数从10变成100，TrainTicketMap与站数^2成正比，搜索
范围就增大100倍。allocate（）时间就增大100倍。当然可以用一个dedicated core
做reserve，把allocate分散到其它cores上。但如何同步就需要一些比较细碎的设计，
不如现在这样简洁了。另外，估计现有的core数很难消化得了100倍的计算量。所以，
对100站是不是就很难达到1M/s的指标了？

2. 如果朝实际方向再进一步，支持一个请求内多个座位连座，该怎么做？这应该是非
常贴近真实需要的。一家人一起走，座位应该是一起买，坐在一起的吧？如果顺着同样
的算法，TrainTicketMap是不是就该扩展成四维，多出的两维是起始座和座位数。那么
，搜索范围就扩大3000^2倍。这个算法是不是就不现实了？

3. 这个算法是源于成熟的理论，还是老魏或老姜的原创？无论如何，针对赌约的指标
要求，解决得非常精巧漂亮，令人佩服。这个问题，在逻辑上相当于在一个二维空间（
两轴分别是座位和站）不空的点上画叉叉，然后找可以容下长（连续座位数）宽（站数
）align在起始站的长方形的空域。这是不是另外还有更generic更好scale的理论和算
法？