西西河

主题:【原创】身为码农,为12306说两句公道话 -- 代码狗

共:💬137 🌺892 🌵3
全看分页树展 · 主题 跟帖
家园 我同意你的算法,而且这个算法可以硬件加速

余票查询,分配,前面有人提到了硬件加速,这是可行的,算法其实更简单。

核心,还是位表。

其样子大概如下:

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 曾扬言 “钱管够”。

那无论是华为或者是思科,都能把订票功能内置到骨干网的路由器里面去。

唯一就看中国电信的骨干网有多快了。

全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河