preface
This article is from dwz.win/HjK. Click to unlock more data structures and algorithms.
Hello, I am tong elder brother, a daily climb 26 floors also do not forget to read the source code of the hardcore man.
I believe that we all have the experience of snatching tickets and brushing tickets. At the end of each year, it is a feast.
However, have you ever wondered how 12306’s ticket-snatching algorithm works?
No? Thought about it? No idea?
Today, we are going to expose how 12306, which people both love and hate, achieves the ticket snatching.
Bit operation review
We know that the computer can only recognize zeros and ones, and the only way to manipulate those zeros and ones is through bit operations, so how many bit operations are there?
Let’s review:
| operation | symbol | For example, | The results of |
|---|---|---|---|
| with | & | 1101 & 0110 | 0100 |
| or | | | 1101 & 0110 | 1111 |
| Exclusive or | ^ | 1101 ^ 0110 | 1011 |
| The not | ~ | 1101 | 0010 |
| Shift to the left | << | 1101 < < 1 | 11010 |
| Signed right shift (high complement 1) | >> | 1101 > > 1 | 1110 |
| Unsigned right shift (high fill 0) | >>> | 1101 > > > 1 | 0110 |
The above bit operation is used as an example in Java. Other languages may not have >>> operations.
OK, a simple review of bit operations here, and do not understand the students can be baidu.
The bitmap
Although bitwise operations are available in most languages, there is no such thing as a bit array. To use bitwise operations, we can only use numeric types, such as int/long in Java.
These numeric arrays are generally referred to as bitmaps.
Long [] bitmap = new Long [2]; long[] bitmap = new long[2]; .
But what’s the use of bitmaps?
Useful, for example, we want to count the activity of a user in a year, you can use a bitmap to achieve.
There are 365 days in a year. One long can represent 64 bits, 365/64=6. Only 6 long types are needed to record the activity of a user in a year.
When the user logs in on a certain day, we find that day in the bitmap and change the bit to 1. Over the course of a year, the bitmap records the days that the user logged in. We count the number of 1s in the bitmap and divide by 365 to get their activity.
OK, this is just a very simple use of bitmaps, there are many advanced uses of bitmaps, such as active user statistics, traffic limiting, permission control, and of course, we are going to expose the 12306 ticket grab algorithm today.
12306 Grab tickets algorithm
As we know, a train has many seats and can go to many stations. Take G67, a train from Beijing to Guangzhou, for example:
The G67 train has a total of 18 stations. Some people may get off in Wuhan, some may get off in Changsha, some may get on in Wuhan and get off in Hengshan West, and some may even take the train from Beijing to Guangzhou. Let’s assume that this train has a total of 200 seats.
So, how to achieve a reasonable strategy to ensure that the train can be filled by the largest number of people? (No standing room ticket)
What is “most seated person”? If one person goes from Beijing to Wuhan, another person goes from Wuhan to Changsha, and another person goes from Changsha to Guangzhou, three people can sit in this position. For another position, a person from Beijing to Guangzhou, then this position can only sit a person. To put it simply, for a specific location, there is no intersection between two people. For example, if one person goes from Beijing to Changsha, and another person goes from Wuhan to Guangzhou, the two people cannot be arranged to the same location.
OK, I’ll give you a minute to think about it before you read down.
All right, one minute is up. Let’s move on.
First, let’s review the information of G67: there are 18 stations with 200 seats.
For the convenience of explanation and drawing, we assume that there are only 6 stations in Beijing, Xinyang, Wuhan, Yueyang, Changsha and Guangzhou, with a total of 8 seats.
In view of such information, we can achieve the strategy of snatching tickets as follows:
-
Create 5 bitmaps. Each bitmap is 8 bits in size. Initially, each bit has a value of 0.
Why five bitmaps? Because the arrival of the station on the bus, and Guangzhou station is the terminal, all people have to get off the bus. For example, a person from Beijing to Wuhan, he gets off when he gets to Wuhan, so, it will not take up the position in Wuhan.
-
The ticket grab logic in a single thread to deal with, the advantages of a single thread is not to consider the concurrency problem, there is no CPU context switch, and the whole operation is CPU operation, the speed is fast, the use of a single thread is more efficient.
Of course, we have a better choice – Redis, Redis itself single thread processing, and it naturally supports BitMap, fast and good, interested students can learn about the BitMap in Redis.
-
Assumes that the first request came over, he is going to rob the ticket from Beijing to wuhan, at this point, we only need to do Beijing and xinyang bitmap “or” operation, the results of all the position of the zero position are said to rob, returns a random in these locations, and put the position in Beijing and in xinyang both the bitmap is marked as 1, It means the location is occupied in Beijing and Xinyang. (Why did Wuhan not participate in the calculation? As mentioned before, this person got off the bus when he arrived in Wuhan.)
Suppose that the last seat of this person is number 2, then after the calculation, the situation of the graph is as follows:
- Then, the request of the second person comes, suppose he wants to go from Xinyang to Changsha, at this time, need to do “or” operation of xinyang, Wuhan and Yueyang bitmap:
Suppose that the person’s last seat is no. 4, then, after calculation, the situation of the graphs is as follows:
- Then, the request comes from the third person, assuming that he wants to go from Beijing to Guangzhou, at this point, all five bitmaps are “or” :
Assume that the last seat of this person is position 1, then, after the calculation, the situation of the graph is as follows:
- OK, after multiple requests, suppose the bitmap situation becomes the following:
Please think, at this time, can still grab a ticket from Beijing to Guangzhou?
Can? Can’t? Those who answer yes, please read it again from the beginning ^^
Ok, about snatching tickets algorithm we are introduced here, have you got it? Or do you have a better way to do it?
Afterword.
In this section, we review the operation of bitmap and learn how to use bitmap to achieve 12306’s ticket-snatching algorithm. Bitmap has many uses, such as statistics, traffic limiting, permission control, etc.
Tong Ge received the latest information: all recursion can be rewritten into non-recursion, how to achieve it? Is there any formula? Let’s talk about that in the next video.
Pay attention to the main public number “Tong Elder brother read source code”, unlock more source code, foundation, architecture knowledge.