主题:【原创】身为码农,为12306说两句公道话 -- 代码狗
余票查询,分配,前面有人提到了硬件加速,这是可行的,算法其实更简单。
核心,还是位表。
其样子大概如下:
0 表示空闲,1 表示占用
座位号 | A 区间 | B 区间 | C 区间 | D 区间 | E 区间 | F 区间 | G 区间 | H 区间
-------+----------+----------+----------+----------+----------+----------+----------+----------
1 | 0 0 0 0 0 0 0 0
2 | 0 0 0 0 0 0 0 0
3 | 0 0 0 0 1 1 1 1
4 | 0 1 0 0 0 0 0 0
5 | 0 0 0 0 0 0 0 0
6 | 1 1 1 1 0 0 0 0
7 | 0 0 0 0 0 0 0 0
8 | 1 1 1 1 1 1 1 1
9 | 0 0 0 0 0 0 0 0
...................
求区间余票,比如 B 到 G,只要把这个位表的相关区间按列取出,进行 “或” 操作就行了,最后得出的位表,就是查询结果。
考虑到一个车次的总车位在数百到数千,那么这个位表的总数据量大小不会超过数百 KB。
这个算法完全可以用 FPGA 或者专用的 ASIC ,位表操作和结果判定可以用硬件并行进行。
基本上来说,查询速度有多快,只取决于芯片能跑多快的频率。如果芯片工作在 1G 的频率,10个Cycle 处理一次查询或者订票请求,做到每秒一亿次是没什么问题的。
世界级难题? 我就笑笑 ...................
如果真如某篇不要脸的吹牛B 文章所说的。
12306 曾扬言 “钱管够”。
那无论是华为或者是思科,都能把订票功能内置到骨干网的路由器里面去。
唯一就看中国电信的骨干网有多快了。
- 相关回复 上下关系8
🙂不上水木不行啊 悠悠又见西山 字67 2014-01-20 06:44:21
😄写的很好 迎风迫降 字42 2014-01-14 14:10:45
🙂数据模型设计 8 jzzzzz 字622 2014-01-14 14:10:21
🙂我同意你的算法,而且这个算法可以硬件加速
🙂那这样做成硬件完全没有扩展性啊 okcgb 字46 2014-02-08 19:43:23
🙂可以设计车厢标准件 天天跑路 字123 2015-04-14 04:02:29
🙂这个设计只适合1个座位吧 1 汉服骑射 字54 2014-01-14 20:43:59
🙂感觉在文中,以G71为例这个简化的的408个商品的模型, 2 王谢 字316 2014-01-14 09:38:17