全网首发:12306抢票算法大曝光?(十张图搞定)

全网首发:12306抢票算法大曝光?(十张图搞定)插图

前言

本文收录于专辑:http://dwz.win/HjK,点击解锁更多数据结构与算法的知识。

你好,我是彤哥,一个每天爬二十六层楼还不忘读源码的硬核男人。

相信大家都有过抢票、刷票的经验,每年年底,这都是一场盛宴。

然而,你有没有想过12306的抢票算法是怎么实现的呢?

没有吧,想过,还是没有头绪?

今天,我们就来曝光让人又爱又恨的12306是如何实现抢票的。

运算回顾

我们知道计算机只能识别0和1,要操作这些0和1,只能通过位运算来进行,那么,一共有几种位运算呢?

让我们来回顾一下:

运算 符号 举例 结果
& 1101 & 0110 0100
| 1101 & 0110 1111
异或 ^ 1101 ^ 0110 1011
取反 ~ 1101 0010
左移 << 1101 << 1 11010
带符号右移(高位补1) >> 1101 >> 1 1110
不带符号右移(高位补0) >>> 1101 >>> 1 0110

以上位运算以Java为例,其他语言中可能没有 >>> 操作。

OK,位运算的简单回顾就到这里,还有不懂的同学可以自行百度一下。

位图

虽然大部分语言都有提供位运算,但是,并没有提供一种类似于位数组的类型,要使用这些位运算,我们只能通过数字类型来实现,比如Java中的int/long等类型。

而这些数字类型的数组,我们一般可以称之为“位图”(BitMap)。

比如,我们需要使用128位的内存,可以申请包含两个long类型的数组long[] bitmap = new long[2];

不过,位图有什么用呢?

有大用处哦,比如,我们要统计某个用户一年的活跃度,就可以使用位图来实现。

一年有365天,一个long类型可以表示64位,365/64=6,只需要6个long类型就可以记录一个用户一年的活跃情况,怎么记录呢?

很简单,初始时,位图中所有位都是0,当这个用户某天登录了,就在位图中找到这天,把其位变成1,一年下来,这张位图就记录了这个用户哪些天登录了,统计这个位图中1的数量,除以365,就得到了他的活跃度。

全网首发:12306抢票算法大曝光?(十张图搞定)插图(1)

OK,这只是位图的一个很简单的用法,位图还有很多高级的用法,比如统计活跃用户数、限流、权限控制等,当然,还有我们今天要曝光的12306抢票算法。

12306抢票算法

我们知道,一列火车,有很多个座位,可以到很多站,以北京到广州的一列火车G67为例:

全网首发:12306抢票算法大曝光?(十张图搞定)插图(2)

G67次列车一共有18个站,有的人可能到武汉就下车了,有的人可能到长沙下车,还有的人可能从武汉上车从衡山西下车,甚至还有的人从北京一直坐到广州,我们假设这趟列车一共有200个座位。

那么,如何实现合理的抢票策略,才能保证这趟列车能够坐最多的人?(没有站票)

什么叫做“坐最多的人”呢?假设针对10号位置,一个人从北京到武汉,另一个人从武汉到长沙,再一个人从长沙到广州,那针对这个位置全程可以坐3个人;针对另一个位置,一个人从北京到广州,那这个位置全程只能坐一个人。简单点说,就是针对一个特定的位置,两个人之间不能有交集,比如一个人从北京到长沙,另一个人从武汉到广州,那这两个人不能安排到同一个位置上。

全网首发:12306抢票算法大曝光?(十张图搞定)插图(3)

OK,先给你一分钟时间思考一下,先别急着往下看哦。


好了,一分钟时间已到,让我们继续。

首先,让我们回顾下G67这趟列车的信息:一共18个站,一共200个座位。

为了方便讲解和画图,我们假设它只有 北京、信阳、武汉、岳阳、长沙、广州 6个站,一共有8个座位。

针对这样的信息,我们可以这样来实现抢票策略:

  1. 创建5个位图,每个位图的大小为8位,初始时,每个位的值都是0。

    为什么是5个位图呢?因为到站就下车了,而广州站是终点站,到站全部人都得下车。比如,一个人从北京到武汉,他到武汉就下车了,所以,它不会占用武汉的位置。

全网首发:12306抢票算法大曝光?(十张图搞定)插图(4)

  1. 把抢票逻辑放在单线程中来处理,单线程的好处是不用考虑并发问题,没有CPU上下文切换的问题等,而且整个操作都是CPU操作,速度很快,使用单线程效率更高。

    当然,我们还有更好的选择——Redis,Redis本身就是单线程处理的,而且它天然支持BitMap,速度又快又好,有兴趣的同学可以了解一下Redis中的BitMap。

  2. 假设第一个人的请求过来了,他要抢从北京到武汉的票,此时,我们只需要把北京和信阳两个位图做“与”运算,结果中,所有0的位置都表示可抢的位置,在这些位置中随机返回一个即可,并把此位置在北京和信阳这两个位图中标记为1,表示此位置在北京和信阳有人占用了。(武汉为什么不参与运算了,前面讲过了,这个人到武汉就下车了。)

    全网首发:12306抢票算法大曝光?(十张图搞定)插图(5)

    假设,此人最后的座位是2号,那么运算之后,各位图的情况如下:

    全网首发:12306抢票算法大曝光?(十张图搞定)插图(6)

  3. 接着,第二个人的请求过来了,假设他要从信阳到长沙,此时,需要把信阳、武汉和岳阳三个位图做“与”运算:

    全网首发:12306抢票算法大曝光?(十张图搞定)插图(7)

    假设,此人最后的座位是4号,那么,运算之后,各位图的情况如下:

    全网首发:12306抢票算法大曝光?(十张图搞定)插图(8)

  4. 然后,第三个人的请求来了,假设他要从北京到广州,此时,把所有5个位图做“与”运算:

    全网首发:12306抢票算法大曝光?(十张图搞定)插图(9)

    假设,此人最后的座位是1号位,那么,运算之后,各位图的情况如下:

    全网首发:12306抢票算法大曝光?(十张图搞定)插图(10)

  5. OK,经过了多个人的请求之后,假设位图的情况变成了下面这样:

    全网首发:12306抢票算法大曝光?(十张图搞定)插图(11)

    请思考,此时,还能抢到从北京到广州的票吗?

    能?不能?回答能的同学,请从头再看一遍^^

好了,关于抢票算法我们就介绍到这里,你有没有Get到呢?或者你有没有更好的实现方法呢?

后记

本节,我们一起重温了位运算的操作,并学习了如何使用位图实现12306的抢票算法,关于位图,其实还有很多用途,比如,各种统计、限流、权限控制等。

彤哥收到最新情报:所有的递归都可以改写成非递归,怎么实现呢?有没有什么套路呢?下一节,我们一起来聊下这个话题。

关注公号主“彤哥读源码”,解锁更多源码、基础、架构知识。

本站资源均源自网络,若涉及您的版权、知识产权或其他利益,请附上版权证明邮件告知。收到您的邮件后,我们将在72小时内删除。
若下载资源地址错误或链接跳转错误请联系站长。站长q:770044133。

» 全网首发:12306抢票算法大曝光?(十张图搞定)

发表评论

免登录下载网,提供全网最优质的资源集合!