12306 出票逻辑没那么难吧

[daboq]

一辆车算 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

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

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

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

[ifxo]

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

[zaima]

一辆车 3000 个座位把

[daboq]

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

[aurthur]

没毕业吧？

[kindjeff]

收藏了

[daboq]

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

[ayase252]

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

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

[zaima]

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

[daboq]

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

[daboq]

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

[kkkkkrua]

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

[Flobit]

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

[virusdefender]

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

[zaima]

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

[zaima]

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

[daboq]

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

[Qlccks2]

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

[zaima]

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

[newtype0092]

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

[Torpedo]

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

[narfnas]

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

[Raynard]

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

[okjb]

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

[shiran3f]

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

[andylsr]

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

[lance6716]

宁这个没法并发？

[xujinkai]

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

[Helsing]

优秀

[Eleutherios]

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

这句话笑死我了。

[litmxs]

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

[daimubai]

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

[ThirdFlame]

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

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

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

[daboq]

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

[gamexg]

这个方案并不方便，

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

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

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

[daboq]

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

[gamexg]

@daboq #35

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

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

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

[gamexg]

票池数据库大概这样：

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

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


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

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

[across]

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

[SjwNo1]

别理了 你们理不明白的

[est]

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

[silencht]

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

[hyy1995]

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


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

[firefox12]

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

但是业务 不是 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]

插眼收藏等撕逼

[SlipStupig]

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

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

[wangxiaoaer]

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

[iugo]

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

说个简单的例子.

设有 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]

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

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

[wysnylc]

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

[whypool]

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

[hellov22ex]

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

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

[hellov22ex]

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

[yanheqi]

回形针做过这方面的节目 <iframe src="//player.bilibili.com/player.html?aid=42125169&cid=73947630&page=1" scrolling="no" border="0" frameborder="no" framespacing="0" allowfullscreen="true"> </iframe>

https://www.bilibili.com/video/av42125169/

[leokino]

没那么简单。必须要确保在最大程度上出票方案全程无空位，并不是单纯的抢占问题。假设 ABC 三个站点，BC 卖掉了，AC 就没法卖，而 AC 可能有 900 元的价值，BC 只有 50 元。12306 的出票方案必须是尽量达到每辆车的空置率都是最低的。

[ebony0319]

我比较赞同你的想法，我一直以为登月就三步骤 1 打开舱门，2 下去，3 拍照宣布自己登月成功。这个只要超过一岁小孩谁不会哇。

[petelin]

有什么好讨论的 连业务是什么都不清楚

所有人都是在臆想解决自己脑子里的问题

[mysunshinedreams]

坐井观天？

[AllenHua]

@ThirdFlame #32 居然看到了天柱山 阁下莫非潜山人

[AllenHua]

@ThirdFlame #32 不好意思 看错了 楼主的站点数组里 就有 天柱山

[ThirdFlame]

@AllenHua 天柱山爬过，在合肥出差的时候 租车去的。风景不错，不用缆车的话 一天行程刚刚好

[AllenHua]

@ThirdFlame #60 哈哈 谢谢谢谢

[ducks]

@iugo 贪婪算法，还有同一个作为，比如有 abcd 4 个站就有 ab,ac,ad,ae,bc,bd,cd 各种组合，这玩意儿记得念高中的时候排列组合阶乘挺烧脑的