12306 出票逻辑没那么难吧

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1784 天前的主题，其中的信息可能已经有所发展或是发生改变。

一辆车算 3000 张票
将每个站点都设置个标志位
0 为未出售 1 为已卖出
出 A-B 的票逻辑:
1.搜索有没有 A-B 标志位都为 0 的行 2.将该行 A-B 所有标志位设为 1

完全没难度啊，多一张票=多插入一行，大家看看这想法对不对
python 测试代码:

zhandian=['南通','如皋','泰州','江都','扬州','滁州北','蚌埠','合肥','庐江','桐城','安庆西','天柱山','太湖','南昌','吉安','信丰','龙川','河源','惠州','东莞东','深圳东']

#三千张票
tickets=[[0 for i in range(len(zhandian))] for x in range(3000)]
def by_ticket(start,end):
    start_index=zhandian.index(start)
    end_index=zhandian.index(end)
    if end_index<=start_index:
        # 站点输入错误
        return -3

    for t in tickets:
        if t[start_index:end_index+1]==[0 for i in range(end_index-start_index+1)]:
            t[start_index:end_index+1]=[1 for i in range(end_index-start_index+1)]
            print('买到座位号{}的票 位置详情:{}'.format(t[0],t))
            return t
    print('无票')
    return -1

第 1 条附言 · 2020-01-22 17:52:47 +08:00

其中标志位不一定只是 0 和 1
比如
设置为 2 就是预留票，另外的接口才能买
设置 3 线下接口才能购买。。。。。。

这是个出票逻辑，其他方面没考虑那么多，讨论逻辑方面，不是要做个 12306

第 2 条附言 · 2020-01-23 09:45:33 +08:00

我发现好多大佬内容都没看就在那里回复，希望大佬们看完下面这些再回复
1.时间复杂度 O(n)，不懂的多看几遍代码
2.票改标志位可以设预留，票数可插入
3.并发可以用队列处理，这里不讨论
4.希望各位看清楚内容，有问题欢迎提问，拒绝无脑喷

62 条回复 • 2021-05-31 00:56:53 +08:00

ifxo

2020-01-22 17:25:50 +08:00

本来就没什么难度，说难的基本上都是菜鸟吧

zaima

2020-01-22 17:30:34 +08:00

一辆车 3000 个座位把

daboq

2020-01-22 17:33:40 +08:00

@zaima 假设一辆车出 3000 张票实际应该不到

aurthur

2020-01-22 17:35:26 +08:00 via Android

没毕业吧？

kindjeff

2020-01-22 17:37:34 +08:00 via Android

收藏了

daboq

2020-01-22 17:37:43 +08:00

@aurthur 那你说下逻辑哪里错了？

ayase252

2020-01-22 17:38:47 +08:00 via iPhone

空间复杂度 mn，时间复杂度 nm^2，m 是站数，n 是车票数。最 naive 的解法，想想还有没有可以优化的地方（面试感）

更别提还有区间锁票，每站预留这种操作了

zaima

2020-01-22 17:39:57 +08:00

@daboq 那按你的逻辑，极限不就可以出 3000 张起点到终点的票了？座位是确定的，票是不确定的，怎么可能用票来判断

daboq

2020-01-22 17:40:46 +08:00

@ayase252 预留可以改标志位，比如改成 2，不固定 0 才能买的，这只是个示例，锁票也一样

daboq

2020-01-22 17:41:33 +08:00

@zaima 可以添加的仔细看题插入一行就行

kkkkkrua

2020-01-22 17:43:07 +08:00 via iPhone

线下售票，电话售票，要更新

Flobit

2020-01-22 17:44:02 +08:00

你这只是线上购票，线下购票的呢？

virusdefender

2020-01-22 17:45:22 +08:00

你说淘宝为啥这么复杂，想想不也就一个库存减 1 然后订单表插入一行么，放在实际的环境中，需要考虑的太多了，比如用户认证、风控、优惠券、缓存、锁表、持久化，消息队列、分布式事务等等等等。

zaima

2020-01-22 17:49:30 +08:00

@daboq 车能载多少是根据座位来决定的啊。我座位只有 2000 个，你怎么可以出 3000 张起点到终点的票呢？我座位有 4000 个，你根据什么情况来插入新行啊？

zaima

2020-01-22 17:52:16 +08:00

@daboq 你的逻辑里没有出现座位这个常量

daboq

2020-01-22 17:54:39 +08:00

@zaima 站点和票数是可以变的，比如加个插入票什么的，而且实际肯定是在数据库中，这只是个测试代码

Qlccks2

2020-01-22 17:54:50 +08:00 via iPhone

也许很复杂，但是出票都是提前计算好的吧，并不是实时计算出票。

zaima

2020-01-22 18:06:25 +08:00

@daboq 你好好琢磨下把……为什么你的逻辑里，唯一确定的两个变量之一的 “座位” 这个变量没出现？另外，你只要假设是 3000 个座位而不是票的话，那么逻辑上并没有什么问题

newtype0092

2020-01-22 18:11:11 +08:00

确实简单，三流小电商站的水平，钱都被层层剥削贪污了。
建议你自己开发一套，卖给铁老大，要价 5 亿不接受还价，后半辈子吃穿不愁了。

Torpedo

2020-01-22 18:12:22 +08:00

你这只是单一的逻辑。当大量用户买票的时候，同步你这个票务信息、决定谁买到票复杂度会上升。

narfnas

2020-01-22 18:21:40 +08:00

难在开票时间点要接收大量用户的抢票，还有抢票软件的。

Raynard

2020-01-22 18:24:27 +08:00 via Android

推倒重建，会简单很多吧，相比当年

okjb

2020-01-22 18:28:24 +08:00 via Android

你这逻辑，上万辆车都不够你用🤣

shiran3f

2020-01-22 18:43:03 +08:00 via iPhone

唉，程序员不懂业务就是这么来的，脱离实际一个人在那边瞎猜，我手下的小弟不知道被我打脸多少次了，不要自己猜猜猜！这本质和键盘侠没区别。

andylsr

2020-01-22 19:16:34 +08:00 via Android

开一万个客户端跑下你的代码试试？

lance6716

2020-01-22 19:19:20 +08:00

宁这个没法并发？

xujinkai

2020-01-22 21:10:07 +08:00

看来 12306 后台也就百来行代码（滑稽

Helsing

2020-01-22 23:20:47 +08:00 via iPhone

优秀

Eleutherios

2020-01-23 00:06:43 +08:00 via iPad

“这是个出票逻辑，其他方面没考虑那么多，讨论逻辑方面，不是要做个 12306”

这句话笑死我了。

litmxs

2020-01-23 01:23:56 +08:00 via Android

讨论就好好讨论，上面一些阴阳怪气的，自己也说不出个所以然，就在那嘲讽

daimubai

2020-01-23 01:35:27 +08:00 via iPhone

单就最后一句只考虑出票逻辑，这玩意还用单独开个贴？会加减法都知道，只考虑出票逻辑有讨论的意义吗？最次也得有个并发吧，有个实时同步检测吧

ThirdFlame

2020-01-23 08:53:08 +08:00

假设此车起点为'南通' 终点为'深圳东'。没有任何限售限制。全列 1000 个座位（暂不考虑卧铺，全部为普通座位。）
如果有人买了 '南通' -'深圳东' 那么南通之后所有车站的可售车票-1。
如果有人买了 '东莞东'-'深圳东'，东莞东之前的所有车站到深圳东的车票-1。

如果有人买了 '南通' -'天柱山'，那么天柱山之前车站到天柱山的车票-1，天柱山到天柱山之后的车站车票+1。
如果有人买了 '合肥'-‘天柱山’，那么合肥之前车站到 ‘合肥’、‘天柱山’区间车票-1. 天柱山到天柱山之后车票+1.

复杂度请考虑一下。
所以要有专门的客票组织部门，指定合理的车票限售和预留。还要计算上座位复用。

daboq

2020-01-23 09:24:36 +08:00

@ThirdFlame 大佬你看明白了没？复杂度 O(N)，预留前面说了改标志位就行，卧铺无座加个字段

gamexg

2020-01-23 10:32:08 +08:00

这个方案并不方便，

感觉目前应该使用的这种方案：

a-e 的线路，预先分配好 a-e、a-b、a-c、a-d、b-c、b-d、b-e 等的票数，kv 数据库都够了，查询余票直接 get 对应的 key 就行，买票直接-1，然后后台再去分配座位号。

可以预先给 a-e 多分配票，卖票时后台根据售票信息动态拆分。

daboq

2020-01-23 10:45:40 +08:00

@gamexg 如果买了 a-e，那 a-b、a-c、a-d、b-c、b-d、b-e 都要减少一，如果是 30 个站点需要几百次修改，比这个方案复杂多了吧。
现在只需要查询 like ____00000__ 一步到位

gamexg

2020-01-23 10:53:51 +08:00

@daboq #35

根据业务经验及需求来预先分配，这样操作的：
比如共 3000 张票，多给 a-e 分配些，分配 a-e 1000 张，
另外 2000 张拆分配到详细区间，例如一张票可以拆分为 a-c、c-e 两个区间，放票时就固定拆分好。
查余票和买票时就比较简单了。

可以后台检查区间票，发现那个区间票低于预期值，可以决定是否后台拆分 a-e 的补区间票。

大体是这个意思，这个比较符合目前的区间无票，始发到终点的票却能够买到的情况。

gamexg

2020-01-23 11:03:35 +08:00

票池数据库大概这样：

key 是线路-日期-车次-上车站点-下车站点-座位类型，value 就是座位数量。

买票操作就是直接对这行记录 -1，然后后台再分配座位号。

座位号可以用一个表保存，和票池对应，票池填充票时就生成座位表，每张票池的票对应一个座位记录。
大概这些字段：线路、日期、车次、上车站点、下车站点、座位类型、是否已使用、座位号

分配座位号时直接查找未使用的作为即可。

across

2020-01-23 11:23:27 +08:00 via iPhone

点开果然是新注册的 s b 小号，故意带节奏的

SjwNo1

2020-01-23 11:29:25 +08:00

别理了你们理不明白的

est

2020-01-23 11:31:12 +08:00

反对 LZ 的也没提出反对的理由，就一个劲的喷。。。支持 LZ。我也觉得没多难。实际上 12306 最大的瓶颈就是查询。阿里云的解决办法就是上大内存机器。可以搜一下 zhihu 问答。

silencht

2020-01-23 12:47:41 +08:00

震惊！ V 站出现大量图灵奖得主！

hyy1995

2020-01-23 13:28:40 +08:00

不愧是 V 站。我虽然说不出个所以然，但我不敢自大到“没觉得多难”，楼上几位要觉得自己有本事，可以去当 12306 CTO，我相信你们可以解决“12306 每次一到春节就抢不到票”的 bug。

另外，讨论就讨论，特意注册个小号，还憋了几天再发帖，至于吗。。。

firefox12

2020-01-23 13:28:45 +08:00

代码没问题，但是就是结果未必是最优解。但是我也觉得可能就没有最优解。现在的规则也不是最优解。

但是业务不是 O(n)

以 n 4000 个位子 m 30 站为例子，你每次分票是需要扫描全数组的。
当然可以优化
但是扫描必须全表。

1 你需要扫描每个 n 的每个 m, 得出这个位子能不能出票
比如有人要买 a-z,
n=0 a...z 都是空的符合买的条件
n=1 a...m 是空的但是 l 不是空的，其实是不符合条件

得出一个符合要求的还不行

其次你还需要做最优解
1, 3, 4, 6 , 7 符合要求，谁是里面最优的？
a...z 是不用考虑的
如果是 m...t 的出票，出在哪个位子上更好？上中下铺需求？所以高速的分票其实比这个复杂。

所以你描述的 O(n) 是不对的。

wangyzj

2020-01-23 13:59:49 +08:00

插眼收藏等撕逼

SlipStupig

2020-01-23 14:12:08 +08:00

你的代码确实可以完成简单售票，但是还是不能满足 12306 的变态需求，先说你这个代码一些问题吧：
1. 你这个设计车次是单向车次，实际情况一趟车会在起点<->终点反复开
2. 你从始发站开始卖票就一次性给卖完了，非始发站的用户上车怎么办？这样不是不能卖票而是成本比较高。
3. 还有一些情况是退改补，这个会影响整个票仓，结合你问题 2 的设计，就会出现火车上出现空座，但是别人也无法购买
4.团体票，团体票相当于批量确认且具有排他性，申请过后，会一次性占多个座位。
5. 票务类型座位不一致，不同等级的票务，座位数量是不一样的，你目前系统假设大家都是平等数量，谁优先抢占谁就有座位，实际情况并不是这样

目前只从票务角度上说，我觉得问题有这些，其它的风控和系统性能不再讨论范围内

wangxiaoaer

2020-01-23 14:45:06 +08:00 via Android

@ThirdFlame 楼主的意思每卖一张新增一条记录，不存在修改库存，但考虑到座位数有限，应该要限制这些记录的总条数不超。

iugo

2020-01-23 16:18:41 +08:00

难的不应该是最大收入吗?

说个简单的例子.

设有 3 个站点(A, B, C), 那么一个座位可能的收入是:

A-C, 3 元
A-B, 2 元
B-C, 1.5 元

然后现在有人买 B-C 的票, 如果立刻卖了, 将来没人买 A-B 但有人买 A-C 就亏了 1.5 元, 如果不卖等 A-C, 将来有人买 A-B 就亏了 0.5 元.

排队是最好的办法, 先收钱, 符合最大利益就出票, 不符合就等着. 直到开车前不能等了, 就按照目前的最大利益出票.

ThirdFlame

2020-01-23 16:27:52 +08:00

只考虑买组织好的一个座位一条记录的票，这当然时间复杂度很低。只需要遍历或者查询即可。
那这和库存减少或者说电影院的售票有何区别，没区别，静态的售票而已。

12306 难不难在售出一个组织好的票。而是一张票售出后带来的其他票的调整和变化。

wysnylc

2020-01-23 17:41:19 +08:00 via Android

淘宝也不过就是个订单系统

whypool

2020-01-23 17:52:18 +08:00 via iPhone

大佬:不就是 crud 么，有啥难度？

hellov22ex

2020-01-23 18:08:32 +08:00

你是不是从来没有写过真正用于干活的代码？
12306 难的不是这个出票逻辑，而是让全国各地的代理、车站、个人准确的获取票，这个是最难的，出票逻辑是它的衍生。
假设北京到上海，票 3000 张，最高峰同时有 300 人退票、买票、刷新界面，这时候要保证他们如果下单买了，票是正确的，买到的票能上火车。

但是实际情况是，普通日子负载压力是 300，特殊日子负载压力是 500000。

hellov22ex

2020-01-23 18:09:36 +08:00

对了，我记得某一年有过负载数据的公布，你自己去看看，这种数据需要多少什么配置的硬件才能搞定。