Java小强个人技术博客站点    手机版
当前位置: 首页 >> 理论 >> 使用Redis位图实现12306分段购票

使用Redis位图实现12306分段购票

13711 理论 | 2023-3-24

很多编程语言都有位运算符,Java语言也不例外。在Java语言中,提供了7种位运算符,分别是按位与(&)、按位或(|)、按位异或(^)、取反(~)、左移(<<)、带符号右移(>>)和无符号右移(>>>)。

这些运算符当中,仅有~是单目运算符,其他运算符均为双目运算符。

在讲解这些运算符的使用之前,必须了解一个常识,那就是:位运算符是对long、int、short、byte和char这5种类型的数据进行运算的,我们不能对double、float和boolean进行位运算操作。


12306.jpg


如果你要理解本文章的理论和逻辑,可以参考,有人写了我就不啰嗦了

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

https://segmentfault.com/a/1190000023534009 


如果你对Redis位图不理解,可以参考

使用Bitmaps位图实现Redis签到

https://www.javacui.com/DB/703.html 

其他知识内容可以参考

https://www.javacui.com/index.php?keyword=redis 


如果你已经了解运算符和Redis位图,那么按照上面文章说法,逻辑其实很简单,就是把所有座位初始化为位图,当你购买车站A到车站B的票时,把中间车站的位图进行计算,如果最终计算有票,则为有票。

当然这边只是在技术上对于这个逻辑进行了实现,12306实际的逻辑的话,大家都懂的,天花板。

相关逻辑的解释,都在注释里面了,直接运行一下即可理解,上代码:

package com.example.springboot;

import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.data.redis.connection.BitFieldSubCommands;
import org.springframework.data.redis.core.RedisTemplate;

import java.util.ArrayList;
import java.util.List;

/**
 * 12306分段购票模拟
 */
@SpringBootTest
public class A12306 {
    @Autowired
    private RedisTemplate redisTemplate;
    private final static int cz = 5; // 几个站点
    private final static int zw = 5; // 几个坐位

    @Test
    public void test1() {
        init();

        // 购买 2 张 1-3的票,此时有票
        int from = 1, to = 3;
        for (int i = 0; i < 2; i++) {
            qp(from, to);
        }

        from = 2;
        to = 4;
        // 购买 2 张 2-4的票,此时有票
        for (int i = 0; i < 2; i++) {
            qp(from, to);
        }

        from = 1;
        to = 5;
        // 购买 2 张 1-5的票,此时有 1 张票
        for (int i = 0; i < 2; i++) {
            qp(from, to);
        }

        from = 1;
        to = 3;
        // 购买 1 张 1-3的票,此时 无票
        qp(from, to);
    }

    public void qp(int from, int to) {
        System.out.println("=========================== 购票开始 ===========================");
        // 这里是要购买的起始站到终点站中间所有站的坐位情况
        List<Long> czLong = new ArrayList<>();
        // 最后一站 不用取,因为最后一站下车,下车就可以继续从这站开始买
        for (int i = from; i < to; i++) {
            // 这里取的时候要多取一个,因为 0 位是默认的 1
            List<Long> list1 = redisTemplate.opsForValue().bitField(i + "",
                    BitFieldSubCommands.create().get(BitFieldSubCommands.BitFieldType.unsigned(zw + 1)).valueAt(0));
            long temp = list1.get(0);
            System.out.println("车站 " + i + " 购票前 坐位情况 " + Long.toBinaryString(temp));
            czLong.add(temp);
        }
        long v = 0;
        for (Long l : czLong) {
            // 两个都为 0 时,才为 0
            v = v | l;
        }
        // 转为 2 进制 01 的字符串
        String b = Long.toBinaryString(v);
        System.out.println("最终计算 坐位情况 " + b);
        // 如果最终结算里面包含 0 ,说明有坐位,可以购买
        if (b.indexOf("0") > -1) {
            // 1 代表无票,把无票的去掉,长度就是总票量
            b = b.replace("1", "");
            System.out.print(from + " 到 " + to + " 有票 总票量 " + b.length());
            // 坐位,这里从右边开始取,否则无法进行下面的运算
            A:
            for (int i = zw; i > 0; i--) {
                // 按位操作向右位移1,再移动回来,再移回来时是用0补位,如果补位后相等说明这个位本来就是0
                if (v >> 1 << 1 == v) {
                    System.out.println(" 您的坐位编号:" + i);
                    for (int j = from; j < to; j++) {
                        // j 站点编号 i 坐位号 ,这里要把区间的车站都标为占用
                        redisTemplate.opsForValue().setBit(j + "", i, true);
                    }
                    break A;
                }
                // 是右移后赋值,意思是向右移动一位出去,此时变量v的值将发生变化
                v >>= 1;
            }
            // 打印购票后所有站坐位情况,最后一站不打印
            for (int i = 1; i < cz; i++) {
                // 这里取的时候要多取一个,因为 0 位是默认的 1
                List<Long> list1 = redisTemplate.opsForValue().bitField(  i + "",
                        BitFieldSubCommands.create().get(BitFieldSubCommands.BitFieldType.unsigned(zw + 1)).valueAt(0));
                long temp = list1.get(0);
                System.out.println("车站 " + i + " 购票后 坐位情况 " + Long.toBinaryString(temp));
            }
        } else {
            System.out.println(from + " 到 " + to + " 无票");
        }
        System.out.println("=========================== 购票结束 ===========================");
    }

    /**
     * 初始化站点和坐位
     */
    @Test
    public void init() {
        for (int z = 1; z <= cz; z++) {
            redisTemplate.delete(z + "");
        }
        for (int z = 1; z <= cz; z++) {
            // 这里把 0 位设置为 1,这样出来的数据就是 1000,方便查看
            redisTemplate.opsForValue().setBit(z + "", 0, true);
            for (int i = 1; i <= zw; i++) {
                redisTemplate.opsForValue().setBit(z + "", i, false);
            }
        }

        System.out.println("数据初始化完毕");
    }
}


运行以后打印结果如下:

数据初始化完毕
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 100000
车站 2 购票前 坐位情况 100000
最终计算 坐位情况 100000
1 到 3 有票 总票量 5 您的坐位编号:5
车站 1 购票后 坐位情况 100001
车站 2 购票后 坐位情况 100001
车站 3 购票后 坐位情况 100000
车站 4 购票后 坐位情况 100000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 100001
车站 2 购票前 坐位情况 100001
最终计算 坐位情况 100001
1 到 3 有票 总票量 4 您的坐位编号:4
车站 1 购票后 坐位情况 100011
车站 2 购票后 坐位情况 100011
车站 3 购票后 坐位情况 100000
车站 4 购票后 坐位情况 100000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 2 购票前 坐位情况 100011
车站 3 购票前 坐位情况 100000
最终计算 坐位情况 100011
2 到 4 有票 总票量 3 您的坐位编号:3
车站 1 购票后 坐位情况 100011
车站 2 购票后 坐位情况 100111
车站 3 购票后 坐位情况 100100
车站 4 购票后 坐位情况 100000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 2 购票前 坐位情况 100111
车站 3 购票前 坐位情况 100100
最终计算 坐位情况 100111
2 到 4 有票 总票量 2 您的坐位编号:2
车站 1 购票后 坐位情况 100011
车站 2 购票后 坐位情况 101111
车站 3 购票后 坐位情况 101100
车站 4 购票后 坐位情况 100000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 100011
车站 2 购票前 坐位情况 101111
车站 3 购票前 坐位情况 101100
车站 4 购票前 坐位情况 100000
最终计算 坐位情况 101111
1 到 5 有票 总票量 1 您的坐位编号:1
车站 1 购票后 坐位情况 110011
车站 2 购票后 坐位情况 111111
车站 3 购票后 坐位情况 111100
车站 4 购票后 坐位情况 110000
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 110011
车站 2 购票前 坐位情况 111111
车站 3 购票前 坐位情况 111100
车站 4 购票前 坐位情况 110000
最终计算 坐位情况 111111
1 到 5 无票
=========================== 购票结束 ===========================
=========================== 购票开始 ===========================
车站 1 购票前 坐位情况 110011
车站 2 购票前 坐位情况 111111
最终计算 坐位情况 111111
1 到 3 无票
=========================== 购票结束 ===========================


可以看到,如果你买了中间的站点,那么再买起始站到终点站时,就不能买了。

推荐您阅读更多有关于“ 12306 redis Bitmaps 位图 分段购票 ”的文章

上一篇:spring-boot-starter-validation 下一篇:SQL/日志监控框架log4jdbc

猜你喜欢

发表评论:

评论:

回复 Java小强 评论于 2023-03-24 15:59
之所以写这个东西,是因技术群讨论时说到了,然后早就对这个感兴趣,于是花了一点时间琢磨了一下,算是复习了一下这些技术点。但是这个和实际应用还是有非常大差距的,因此后续还要再琢磨一下。