赞
踩
本文收录于专辑: 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,就得到了他的活跃度。
OK,这只是位图的一个很简单的用法,位图还有很多高级的用法,比如统计活跃用户数、限流、权限控制等,当然,还有我们今天要曝光的12306抢票算法。
我们知道,一列火车,有很多个座位,可以到很多站,以北京到广州的一列火车G67为例:
G67次列车一共有18个站,有的人可能到武汉就下车了,有的人可能到长沙下车,还有的人可能从武汉上车从衡山西下车,甚至还有的人从北京一直坐到广州,我们假设这趟列车一共有200个座位。
那么,如何实现合理的抢票策略,才能保证这趟列车能够坐最多的人?(没有站票)
什么叫做“坐最多的人”呢?假设针对10号位置,一个人从北京到武汉,另一个人从武汉到长沙,再一个人从长沙到广州,那针对这个位置全程可以坐3个人;针对另一个位置,一个人从北京到广州,那这个位置全程只能坐一个人。简单点说,就是针对一个特定的位置,两个人之间不能有交集,比如一个人从北京到长沙,另一个人从武汉到广州,那这两个人不能安排到同一个位置上。
OK,先给你一分钟时间思考一下,先别急着往下看哦。
好了,一分钟时间已到,让我们继续。
首先,让我们回顾下G67这趟列车的信息:一共18个站,一共200个座位。
为了方便讲解和画图,我们假设它只有 北京、信阳、武汉、岳阳、长沙、广州 6个站,一共有8个座位。
针对这样的信息,我们可以这样来实现抢票策略:
假设,此人最后的座位是2号,那么运算之后,各位图的情况如下:
假设,此人最后的座位是4号,那么,运算之后,各位图的情况如下:
假设,此人最后的座位是1号位,那么,运算之后,各位图的情况如下:
请思考,此时,还能抢到从北京到广州的票吗?
能?不能?回答能的同学,请从头再看一遍^^
好了,关于抢票算法我们就介绍到这里,你有没有Get到呢?或者你有没有更好的实现方法呢?
本节,我们一起重温了位运算的操作,并学习了如何使用位图实现12306的抢票算法,关于位图,其实还有很多用途,比如,各种统计、限流、权限控制等。
彤哥收到最新情报:所有的递归都可以改写成非递归,怎么实现呢?有没有什么套路呢?下一节,我们一起来聊下这个话题。
关注公号主“彤哥读源码”,解锁更多源码、基础、架构知识。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。