首页 > Redis > 位图在 12306 中的应用

位图在 12306 中的应用

记得 12306 刚上线的时候,就在想 12306 是如何卖票,一趟车从北京到上海,中间经过了 N 个站,大家可以买其中的任意两站,而因为卖出了一个一张票,从北京到上海很多站的车票都会变动,当时就感觉这个算法太复杂了,一般人还真写不出来,由此虽然很多人都在吐槽 12306,但是我却一直任务 12306 特别牛,很多人吐槽的大学生水平肯定是做不出来的,前一段时间,听马士兵教育的周志磊老师讲课,提出 redis 中的位图解决,设计的很巧妙,突然感觉豁然开朗,如果你也有这个问题,不妨参考一下。至于什么是位图,就不多说了,如果不知道,可以简单搜索。

首先说问题,我们假设一趟车是从 A 站到 B 站,中间有 C、D、E、F、G 站,这趟车有 1、2、3、5、6 个座位,任何一个人从可以买任意一趟车的任一个座,当然被别人买过了就不行,我们都坐过车,所以规则就不多说了,直接上算法。

我们设置一个 key,例如 keyA 就代表,这趟车在 A 站的情况,所以默认情况下 keyA = 000000;同理其他站也是这个情况。假设此时有一个人甲买了从 A 站到 E 站的票 2 号靠,也就是 A、C、D 三站他是在 2 号座位上的,E 站就下车了,座位空出来了,所以此时 keyA、keyC、keyD 应该是 010000,其余还都是 000000,于此同时又来了一个人乙,他要买从 C 站到 F 站的票,那么他可以买哪些票呢?很明显除了 2 都可以买(被甲从 A 站到 E 站占了),我们怎么得到的这个结果呢?我们可以让 keyC、keyD、keyE,也就是乙要做的这三站的 key,按位做或运算,我们就可以得出结果:010000,第二位是 1,就代表座上有人我们不能买,其余的都可以买,假设他买了 4 号票,那么此时 keyA 是 010000,keyC、keyD 是 010100,keyE 是 000100,keyF、keyG、keyB 以为是 000000,所以假设此时来了一个人丙要买从 D 站到 B 站的票,我们只需要 keyD、keyE、keyF、keyG 按位或即可,得出的结果是 010100,也就是只有 2 号位(被甲在 D 到 E 的时候占了)和 4 号位(被乙从 D 站到 E 站的时候占了)不能买,其余的座位是可以随便买的,然后把相应的座位从出发站到终到站前面的一站标记成 1 即可,这样我们可以发现,我们只需要一个按位或运算,即可实现动态管理这趟车的车票,非常简单。而且位图八位才一个字节,一趟车一个车厢 118 座,按 16 个车厢算才 1888 位,236 个字节,占用内存非常少。而且 redis 原生支持位图或运算,速度也非常快。

最后我们会发现,这个算法设计很巧妙,占用内存很少,速度很快,使用简单,这就是算法的力量。

全文完,如果本文对您有所帮助,请花 1 秒钟帮忙点击一下广告,谢谢。

作 者: BridgeLi,https://www.bridgeli.cn
原文链接:http://www.bridgeli.cn/archives/714
版权声明:非特殊声明均为本站原创作品,转载时请注明作者和原文链接。
分类: Redis 标签: , ,
  1. 本文目前尚无任何评论.

请输入正确的验证码