首页 > > 程序设计 > Java技术 >

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

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

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

前言

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

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

需求：

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
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有