使用位图演算法来优化签到历史资料的空间占用
前言
实际开发中有这样的场景，使用者每日签到，可获取相对应的积分赠送，如果连续签到，则可获得额外的积分赠送。
本文主要讲解使用位图算法来优化签到历史记录的空间占用。当然如果业务中仅仅是获取连续签到的最大天数，使用一个计数器即可记录。
需求：
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 decodeResult[index] = data ;
//获取该天所在的bit的值
int flag = data[index] & (1 编码问题
应用中使用的字节阵列，而存到数据库的是字串。
由于ASCII表中有很多不可打印的ASCII值，并且每一个签到记录的字节都是-128～127,如果使用String 来进行转码，会造成乱码出现，
乱码
public static void main(String args[]){
byte[] data = new byte[1];
for(int i = 0; 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 的那些事儿
LocalDateDate类并不能为我们提供获取某一天是该年的第几天功能，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 decodeResult[index] = data ;
String encodeResult = new BASE64Encoder().encode(decodeResult);
return encodeResult;
}
获取某年某月的签到资料
该功能实现先求出当月第一天和最后一天属于当年的第几天，然后遍历该范围内的签到情况。
/**
*功能描述
* @author lgj
* @Description 获取某年某月的签到资料
* @date 6/27/19
* @param: List，如果当月的第一天和第三天签到，返回[1,3]
* @return:
*
*/
public static List 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 signDayOfMonths = new ArrayList();
int signDay = 0;
//遍历
for(int i = start; 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 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 maxDay)){
throw new SignException("The param dayOfYear["+dayOfYear+"] is out of [0-"+ maxDay+"]");
}
}
//校验月数是否超出范围
private static void checkOutofMonth(int month) throws Exception{
if((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 System.out.print(data[i]);
}
System.out.println();
log.info("signHistory 长度:[{}],VALUE=[{}]",signHistory.length(),signHistory);
List 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 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字段进行区分。
