Base64 的那些事儿
程序员文章站
2022-07-09 20:51:50
前言 实际开发中有这样的场景，用户每日签到，可获取相对应的积分赠送，如果连续签到，则可获得额外的积分赠送。 本文主要讲解使用位图算法来优化签到历史记录的空间占用。当然如果业务中仅仅是获取连续签到的最大天数，使用一个计数器即可记录。 需求： 1.记录一年的签到历史 2.获取某月的签到历史 3.获取过去 ......
前言
实际开发中有这样的场景，用户每日签到，可获取相对应的积分赠送，如果连续签到，则可获得额外的积分赠送。
本文主要讲解使用位图算法来优化签到历史记录的空间占用。当然如果业务中仅仅是获取连续签到的最大天数，使用一个计数器即可记录。
需求：
1.记录一年的签到历史
2.获取某月的签到历史
3.获取过去几天连续签到的最大天数
位图算法实现思路
一天的签到状态只有两种，签到和未签到。如果使用一个字节来表示，就需要最多366个字节。如果只用一位来表示仅需要46(366/8 = 45.75)个字节。
位图算法最关键的地方在于定位。 也就是说数组中的第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 来进行转码，会造成乱码出现，
乱码
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字段进行区分。
====================================
上一篇： Neo4j常用的查询