分类

使用位图算法来优化签到历史存储空间占用 Base64 的那些事儿

JAVA学习网 2019-06-27 22:49:02

 

前言

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

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

 

需求：

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---
阅读(2592) 评论(0)