Base64 的那些事儿

程序员文章站 2022-04-15 15:34:55

前言实际开发中有这样的场景，用户每日签到，可获取相对应的积分赠送，如果连续签到，则可获得额外的积分赠送。本文主要讲解使用位图算法来优化签到历史记录的空间占用。当然如果业务中仅仅是获取连续签到的最大天数，使用一个计数器即可记录。需求： 1.记录一年的签到历史 2.获取某月的签到历史 3.获取过去 ......

前言

实际开发中有这样的场景，用户每日签到，可获取相对应的积分赠送，如果连续签到，则可获得额外的积分赠送。

本文主要讲解使用位图算法来优化签到历史记录的空间占用。当然如果业务中仅仅是获取连续签到的最大天数，使用一个计数器即可记录。

需求：

1.记录一年的签到历史

2.获取某月的签到历史

3.获取过去几天连续签到的最大天数

位图算法实现思路

一天的签到状态只有两种，签到和未签到。如果使用一个字节来表示，就需要最多366个字节。如果只用一位来表示仅需要46(366/8 = 45.75)个字节。

Base64 的那些事儿

位图算法最关键的地方在于定位。也就是说数组中的第n bit表示的是哪一天。给出第n天，如何查找到第n天的bit位置。

这里使用除法和求余来定位。

比如上图

第1天，index = 1/8 = 0, offset = 1 % 8 = 1 ,也就是第0个数组的第1个位置(从0开始算起)。

第11天，index = 11/8 = 1, offset = 11 % 8 = 3 ,也就是第1个数组的第3个位置(从0开始算起)。

        byte[] decoderesult = signhistorytobyte(signhistory);
         //index 该天所在的数组字节位置
        int index = dayofyear / 8;
       //该天在字节中的偏移量
        int offset = dayofyear % 8;
        //设置该天所在的bit为1
　　　　 byte data = decoderesult[index];
        data =  (byte)(data|(1 << (7-offset)));
        decoderesult[index] = data ;

　　　　//获取该天所在的bit的值
       int flag = data[index] & (1 << (7-offset));

编码问题

应用中使用的字节数组，而存到数据库的是字符串。

由于ascii表中有很多不可打印的ascii值，并且每一个签到记录的字节都是-128～127,如果使用string 来进行转码，会造成乱码出现，

Base64 的那些事儿

乱码

public static void main(string args[]){

       byte[] data = new byte[1];
       for(int i = 0; i< 127; i++){
           data[0] = (byte)i;
           string str =  new string(data);
           system.out.println(data[0] + "---" + str);
       }

       data[0] = -13;
       string str =  new string(data);
       system.out.println(data[0] + "---" + str + "----");


   }

/////////////////////////
0--- 
1---
2---
3---
4---
5---
6---
7---
8--
9---    
10---

11---
12---

为了解决编码乱码问题，

本文使用base64编码来实现。参看

base64 的那些事儿

localdate

date类并不能为我们提供获取某一天是该年的第几天功能，jdk8为我们提供了localdate类，该类可以替换date类，相比date提供了更多丰富的功能。更多使用方法参考源码。

 //获取2018/6/11 位于该年第几天
       localdate localdate  = localdate.of(2018,6,11);
       localdate.getdayofyear();

       //获取今天 位于当年第几天
       localdate localdate1  = localdate.now();
       localdate.getdayofyear();

数据表

原始数组长度仅需要46个字节，经过base64编码后的字符串长度为64,所以这里的sign_history长度最大为64.

drop table if exists `sign`;
create table `sign`(
   `id` bigint   auto_increment comment "id",
   `user_id` bigint  default null comment "用户id",
   `sign_history` varchar(64) default null comment "签到历史",
   `sign_count` int default 0 comment "连续签到次数" ,
   `last_sign_time` timestamp default  current_timestamp comment "最后签到时间",
    primary key (`id`),
    unique user_id_index (`user_id`)

)engine=innodb default charset=utf8 comment="签到表";

签到

由于每一天在签到历史记录的字节数组中的位置都是固定好的。因此可以通过对该天进行除法和求余，即可轻易计算出该天所在的bit.

对该天签到仅需将该bit置1即可。之后对字节数组进行重新base64编码即可

/**
     *功能描述
     * @author lgj
     * @description   签到
     * @date 6/27/19
     * @param:   signhistory: 原始签到字符串
     *           dayofyear: 需要签到的那一天(那年的第几天)
     * @return:  最新生成的签到历史字符串
     *
    */
    public static string sign(string signhistory,int dayofyear) throws exception {

        if(signhistory == null){
            throw new signexception("signhistory can not be null!");
        }
        checkoutofday(dayofyear);

        byte[] decoderesult = signhistorytobyte(signhistory);
        //index 该天所在的数组字节位置
        int index = dayofyear / 8;
       //该天在字节中的偏移量
        int offset = dayofyear % 8;
        byte data = decoderesult[index];
        data =  (byte)(data|(1 << (7-offset)));
        decoderesult[index] = data ;

        string encoderesult =  new base64encoder().encode(decoderesult);

        return encoderesult;

    }

获取某年某月的签到数据

该功能实现先求出当月第一天和最后一天属于当年的第几天，然后遍历该范围内的签到情况。

/**
     *功能描述
     * @author lgj
     * @description   获取某年某月的签到数据
     * @date 6/27/19
     * @param:    list<integer>，如果当月的第一天和第三天签到，返回[1,3]
     * @return:
     *
    */
    public static list<integer> getsignhistorybymonth(string signhistory, int year, int month)throws exception{

        if(signhistory == null){
            throw new signexception("signhistory can not be null!");
        }
        checkoutofmonth(month);
        //start 本月第一天属于当年的第几天
        localdate localdate =  localdate.of(year,month,1);
        int start = localdate.getdayofyear();
        //end 本月的最后一天属于当年的第几天
        int dayofmonth = localdate.lengthofmonth();
        //log.info("dayofmonth = {}",dayofmonth);
        localdate = localdate.withdayofmonth(dayofmonth);
        int end = localdate.getdayofyear();

        //log.info("start={},end={}",start,end);
        integer result = 0;

        byte[] data = signhistorytobyte(signhistory);

        list<integer> signdayofmonths = new arraylist<>();

        int signday = 0;
　　　　　//遍历
        for(int i = start; i< end ; i++){
            signday++;
            if(issign(data,i)){
                signdayofmonths.add(signday);
            }

        }

        return signdayofmonths;

    }

获取过去几天的连续签到的次数

先定位当天的bit所在的bit位置，再往前遍历，直到碰到没有签到的一天。

/**
     *功能描述
     * @author lgj
     * @description   获取过去几天的连续签到的次数
     * @date 6/27/19
     * @param:
     * @return:   今天 6.27 签到， 同时 6.26 ，6.25 也签到 ，6.24 未签到 ，返回 3
     *            今天 6.27 未签到， 同时 6.26 ，6.25 也签到 ，6.24 未签到 ，返回 2
     *
    */
    public static int  getmaxcontinuitysignday(string signhistory) throws exception{

        int maxcontinuitysignday = 0;

        if(signhistory == null){
            throw new signexception("signhistory can not be null!");
        }
        //获取当天所在的年偏移量
        localdate localdate =localdate.now();
        int curdayofyear = localdate.getdayofyear();

        byte[] data = signhistorytobyte(signhistory);

        //开始遍历，从昨天往前遍历
        int checkdayofyear = curdayofyear-1;
        while (checkdayofyear > 0){
            if(issign(data,checkdayofyear)){
                checkdayofyear--;
                maxcontinuitysignday++;
            }
            else {
                break;
            }

        }
        //检测今天是否已经签到，签到则+1
        if(issign(data,curdayofyear)){
            maxcontinuitysignday +=1;
        }
        return maxcontinuitysignday;
    }

测试某年的第n天是否签到

和上面一样先定位当天的bit所在的位置，再获取该bit的值，如果为1则说明已经签到，否则为0说明没签到。

/**
     *功能描述
     * @author lgj
     * @description  测试某年的第n天是否签到
     * @date 6/27/19
     * @param:  true： 该天签到 false：没有签到
     * @return:
     *
    */
    public static boolean issign(byte[] data,int dayofyear) throws exception{

        checkoutofday(dayofyear);
        int index = dayofyear / 8;
        int offset = dayofyear % 8;
        //system.out.print(index+"-");
        int flag = data[index] & (1 << (7-offset));

        return flag == 0?false:true;

    }

其他代码

//获取默认值，所有的bit都为0,也就是没有任何的签到数据
public static string defaultsignhistory(){
        byte[] encodedata = new byte[46];
        return new base64encoder().encode(encodedata);
    }
//签到历史字符串转字节数组
public static byte[] signhistorytobyte(string signhistory) throws exception {
        if(signhistory == null){
            throw new signexception("signhistory can not be null!");
        }

        return new base64decoder().decodebuffer(signhistory);
    }
 //校验天是否超出范围 0- 365|366
 private static void checkoutofday(int dayofyear) throws exception{
        localdate localdate =localdate.now();
        int maxday = localdate.isleapyear()?366:365;
        if((dayofyear <= 0)&&( dayofyear > maxday)){
            throw  new signexception("the param dayofyear["+dayofyear+"] is out of [0-"+ maxday+"]");
        }
    }
//校验月数是否超出范围
    private static void checkoutofmonth(int month) throws exception{
        if((month <= 0)&&( month > 12)){
            throw  new signexception("the param month["+month+"] is out of [0-"+ 12+"]");
        }
    }

测试

测试1

@test
public void sign() throws exception{

    string signhistory = signhistoryutil.defaultsignhistory();


    int signmonth = 8;
    int signday = 13;
    int dayofyear0 = localdate.of(2019,signmonth,signday).getdayofyear();
    log.info("对2019-"+ signmonth + "-"+signday+",第[" + dayofyear0 + "]天签到！");
    signhistory = signhistoryutil.sign(signhistory,dayofyear0);


    signmonth = 8;
    signday = 24;
    int dayofyear1 = localdate.of(2019,signmonth,signday).getdayofyear();
    log.info("对2019-"+ signmonth + "-"+signday+",第[" + dayofyear1 + "]天签到！");
    signhistory = signhistoryutil.sign(signhistory,dayofyear1);



    byte[] data = signhistoryutil.signhistorytobyte(signhistory);


    system.out.println();

    log.info("第[{}]天是否签到:{}",dayofyear0,signhistoryutil.issign(data,dayofyear0));
    log.info("第[{}]天是否签到:{}",dayofyear1,signhistoryutil.issign(data,dayofyear1));

    log.info("第[{}]天是否签到:{}",15,signhistoryutil.issign(data,16));


    log.info("签到结果:");
    log.info("数组长度 = " + data.length);
    for(int i = 0; i< data.length; i++){

        system.out.print(data[i]);
    }
    system.out.println();
    log.info("signhistory 长度:[{}],value=[{}]",signhistory.length(),signhistory);
    list<integer> signdayofmonths = signhistoryutil.getsignhistorybymonth(signhistory,2019,signmonth);

    log.info("第[{}]月签到记录[{}]",signmonth,signdayofmonths);
}

输出

14:09:23.493 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 对2019-8-13,第[225]天签到！
14:09:23.529 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 对2019-8-24,第[236]天签到！

14:09:23.531 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 第[225]天是否签到:true
14:09:23.535 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 第[236]天是否签到:true
14:09:23.535 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 第[15]天是否签到:false
14:09:23.535 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 签到结果:
14:09:23.536 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 数组长度 = 46
00000000000000000000000000006480000000000000000
14:09:23.542 [main] info com.microblog.points.service.strategy.signhistoryutiltest - signhistory 长度:[64],value=[aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaeaiaaaaaaaaaaaaaaaaaaaaaa==]
14:09:23.545 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 第[8]月签到记录[[13, 24]]

process finished with exit code 0

测试2

@test
    public void getmaxcontinuitysignday()throws exception {

        string signhistory = signhistoryutil.defaultsignhistory();

        int curmonth = localdate.now().getmonth().getvalue();
        int curday = localdate.now().getdayofmonth();

        int signdaycount = 0;
        int maxcount = 5;
        while(signdaycount < maxcount){
            localdate localdate  = localdate.of(2019,curmonth,curday-signdaycount);
            log.info("[{}]签到",localdate);
            signhistory = signhistoryutil.sign(signhistory,localdate.getdayofyear());
            signdaycount++;
        }

        localdate localdate  = localdate.of(2019,curmonth,curday-signdaycount-1);
        log.info("[{}]签到",localdate);
        signhistory = signhistoryutil.sign(signhistory,localdate.getdayofyear());


       int  maxcontinuitysignday = signhistoryutil.getmaxcontinuitysignday(signhistory);
        log.info("连续签到[{}]天！",maxcontinuitysignday);



    }

输出

14:11:02.340 [main] info com.microblog.points.service.strategy.signhistoryutiltest - [2019-06-27]签到
14:11:02.351 [main] info com.microblog.points.service.strategy.signhistoryutiltest - [2019-06-26]签到
14:11:02.352 [main] info com.microblog.points.service.strategy.signhistoryutiltest - [2019-06-25]签到
14:11:02.353 [main] info com.microblog.points.service.strategy.signhistoryutiltest - [2019-06-24]签到
14:11:02.354 [main] info com.microblog.points.service.strategy.signhistoryutiltest - [2019-06-23]签到
14:11:02.355 [main] info com.microblog.points.service.strategy.signhistoryutiltest - [2019-06-21]签到
14:11:02.355 [main] info com.microblog.points.service.strategy.signhistoryutiltest - 连续签到[5]天！

注意: 本文实例代码中并未考虑跨年度的情况，sign_history字段仅支持保存当年(1月1号--12月31号)的日签到数据，如果需要跨年度需求，在数据表中添加year字段进行区分。

本文完整代码实现代码测试代码

====================================

上一篇： JVM工作原理浅析

下一篇： 2019最新Java视频免费赠送

Base64 的那些事儿

前言

需求：

位图算法实现思路

编码问题

base64 的那些事儿

localdate

数据表

签到

获取某年某月的签到数据

获取过去几天的连续签到的次数

测试某年的第n天是否签到

其他代码

测试

测试1

输出

测试2

输出

神经网络API、Kotlin支持，那些你必须知道的Android 8.1预览版和Android Studio 3.0新特性

分析那些能够在三个月做到10万IP的站

此文介绍我的那些站长小工具

那些不为人知的流量来源分析

结合这几年的工作，浅谈网络品牌营销的那些事

说说关于友情链接的那些事儿

盘点那些年个人站长使用过的网站模板

CDN缓存是什么意思解析CDN加速的那些事

解密那些骗子一样的营销手段

JS正则表达式从入门到入土（9）—— test方法以及它的那些坑

Base64 的那些事儿

前言

需求：

位图算法实现思路

编码问题

base64 的那些事儿

localdate

数据表

签到

获取某年某月的签到数据

获取过去几天的连续签到的次数

测试某年的第n天是否签到

其他代码

测试

测试1

输出

测试2

输出

神经网络API、Kotlin支持，那些你必须知道的Android 8.1预览版和Android Studio 3.0新特性

分析那些能够在三个月做到10万IP的站

此文介绍我的那些站长小工具

那些不为人知的流量来源分析

结合这几年的工作，浅谈网络品牌营销的那些事

说说关于友情链接的那些事儿

盘点那些年个人站长使用过的网站模板

CDN缓存是什么意思 解析CDN加速的那些事

解密那些骗子一样的营销手段

JS正则表达式从入门到入土（9）—— test方法以及它的那些坑

CDN缓存是什么意思解析CDN加速的那些事