使用位图算法来优化签到历史存储空间占用

2019-08-16 09:20:55来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

使用位图算法来优化签到历史存储空间占用

 

前言

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

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

 

需求:

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字段进行区分。

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

 

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


原文链接:https://www.cnblogs.com/lgjlife/p/11096373.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:JavaWeb中点赞功能的实现及完整实例

下一篇:maven安装本地jar到本地仓库(引入第三方jar, maven打包提示程序