google group varint 无损压缩解压算法的高效实现 改进版
- - 搜索技术博客－淘宝google group varint 无损压缩解压算法的高效实现. 近期对其进行了一次改进，性能提升 20%，测试数据如下：. 压缩和解压 100万个整数 (4M). 新版本： encode time consumed: 0.003252 s ;. 老版本： encode time consumed: 0.005198 s ;.
google group varint 无损压缩解压算法的高效实现 改进版
标签：
性能优化
搜索引擎
| 发表时间：2013-04-17 15:54 | 作者：野王
出处：http://www.searchtb.com
之前实现了一个版本:
google group varint 无损压缩解压算法的高效实现
近期对其进行了一次改进，性能提升 20%，测试数据如下：
压缩和解压 100万个整数 (4M)
新版本： encode time consumed: 0.003252 s ; decode time consumed: 0.003769 s
老版本： encode time consumed: 0.005198 s ; decode time consumed: 0.004909 s
这样 1秒钟 能解压 1G 的数据，够惊人的吧
不废话，上代码， 有兴趣的自己看，如果我的注释不够清晰，请联系我修改
/****************************************************************** * Created on: 2011-4-26 * Author: [email protected] [email protected] * * Desc : 提供uint32的 varint 压缩和解压功能 * 提供group varint的高效实现 * ******************************************************************/ #ifndef VARINT_H_ #define VARINT_H_ #include <stdint.h> #include <stddef.h> #include "common.h" namespace ups_util { #pragma pack(1) typedef struct { uint32_t value : 24; }UINT24_T; #pragma pack() /** * group varint 的索引表， 单位：(byte) * * 第0列： 第2整数 和 当前索引单元第一个字节的距离 * 第1列： 第3整数 和 当前索引单元第一个字节的距离 * 第2列： 第4整数 和 当前索引单元第一个字节的距离 * 第3列： 第1整数 占用的字节数 * 第4列： 第2整数 占用的字节数 * 第5列： 第3整数 占用的字节数 * 第6列： 第4整数 占用的字节数 * 第7列： 下一个索引单元（4个整数） 和 当前索引单元第一个字节的距离 * * 第一个整数和 索引单元的距离总是 1 */ static const uint8_t GROUP_VARINT_IDX_ARR[256][8] = { /* 00 00 00 00 */ { 2, 3, 4, 1, 1, 1, 1, 5}, /* 00 00 00 01 */ { 2, 3, 4, 1, 1, 1, 2, 6}, /* 00 00 00 10 */ { 2, 3, 4, 1, 1, 1, 3, 7}, /* 00 00 00 11 */ { 2, 3, 4, 1, 1, 1, 4, 8}, /* 00 00 01 00 */ { 2, 3, 5, 1, 1, 2, 1, 6}, /* 00 00 01 01 */ { 2, 3, 5, 1, 1, 2, 2, 7}, /* 00 00 01 10 */ { 2, 3, 5, 1, 1, 2, 3, 8}, /* 00 00 01 11 */ { 2, 3, 5, 1, 1, 2, 4, 9}, /* 00 00 10 00 */ { 2, 3, 6, 1, 1, 3, 1, 7}, /* 00 00 10 01 */ { 2, 3, 6, 1, 1, 3, 2, 8}, /* 00 00 10 10 */ { 2, 3, 6, 1, 1, 3, 3, 9}, /* 00 00 10 11 */ { 2, 3, 6, 1, 1, 3, 4, 10}, /* 00 00 11 00 */ { 2, 3, 7, 1, 1, 4, 1, 8}, /* 00 00 11 01 */ { 2, 3, 7, 1, 1, 4, 2, 9}, /* 00 00 11 10 */ { 2, 3, 7, 1, 1, 4, 3, 10}, /* 00 00 11 11 */ { 2, 3, 7, 1, 1, 4, 4, 11}, /* 00 01 00 00 */ { 2, 4, 5, 1, 2, 1, 1, 6}, /* 00 01 00 01 */ { 2, 4, 5, 1, 2, 1, 2, 7}, /* 00 01 00 10 */ { 2, 4, 5, 1, 2, 1, 3, 8}, /* 00 01 00 11 */ { 2, 4, 5, 1, 2, 1, 4, 9}, /* 00 01 01 00 */ { 2, 4, 6, 1, 2, 2, 1, 7}, /* 00 01 01 01 */ { 2, 4, 6, 1, 2, 2, 2, 8}, /* 00 01 01 10 */ { 2, 4, 6, 1, 2, 2, 3, 9}, /* 00 01 01 11 */ { 2, 4, 6, 1, 2, 2, 4, 10}, /* 00 01 10 00 */ { 2, 4, 7, 1, 2, 3, 1, 8}, /* 00 01 10 01 */ { 2, 4, 7, 1, 2, 3, 2, 9}, /* 00 01 10 10 */ { 2, 4, 7, 1, 2, 3, 3, 10}, /* 00 01 10 11 */ { 2, 4, 7, 1, 2, 3, 4, 11}, /* 00 01 11 00 */ { 2, 4, 8, 1, 2, 4, 1, 9}, /* 00 01 11 01 */ { 2, 4, 8, 1, 2, 4, 2, 10}, /* 00 01 11 10 */ { 2, 4, 8, 1, 2, 4, 3, 11}, /* 00 01 11 11 */ { 2, 4, 8, 1, 2, 4, 4, 12}, /* 00 10 00 00 */ { 2, 5, 6, 1, 3, 1, 1, 7}, /* 00 10 00 01 */ { 2, 5, 6, 1, 3, 1, 2, 8}, /* 00 10 00 10 */ { 2, 5, 6, 1, 3, 1, 3, 9}, /* 00 10 00 11 */ { 2, 5, 6, 1, 3, 1, 4, 10}, /* 00 10 01 00 */ { 2, 5, 7, 1, 3, 2, 1, 8}, /* 00 10 01 01 */ { 2, 5, 7, 1, 3, 2, 2, 9}, /* 00 10 01 10 */ { 2, 5, 7, 1, 3, 2, 3, 10}, /* 00 10 01 11 */ { 2, 5, 7, 1, 3, 2, 4, 11}, /* 00 10 10 00 */ { 2, 5, 8, 1, 3, 3, 1, 9}, /* 00 10 10 01 */ { 2, 5, 8, 1, 3, 3, 2, 10}, /* 00 10 10 10 */ { 2, 5, 8, 1, 3, 3, 3, 11}, /* 00 10 10 11 */ { 2, 5, 8, 1, 3, 3, 4, 12}, /* 00 10 11 00 */ { 2, 5, 9, 1, 3, 4, 1, 10}, /* 00 10 11 01 */ { 2, 5, 9, 1, 3, 4, 2, 11}, /* 00 10 11 10 */ { 2, 5, 9, 1, 3, 4, 3, 12}, /* 00 10 11 11 */ { 2, 5, 9, 1, 3, 4, 4, 13}, /* 00 11 00 00 */ { 2, 6, 7, 1, 4, 1, 1, 8}, /* 00 11 00 01 */ { 2, 6, 7, 1, 4, 1, 2, 9}, /* 00 11 00 10 */ { 2, 6, 7, 1, 4, 1, 3, 10}, /* 00 11 00 11 */ { 2, 6, 7, 1, 4, 1, 4, 11}, /* 00 11 01 00 */ { 2, 6, 8, 1, 4, 2, 1, 9}, /* 00 11 01 01 */ { 2, 6, 8, 1, 4, 2, 2, 10}, /* 00 11 01 10 */ { 2, 6, 8, 1, 4, 2, 3, 11}, /* 00 11 01 11 */ { 2, 6, 8, 1, 4, 2, 4, 12}, /* 00 11 10 00 */ { 2, 6, 9, 1, 4, 3, 1, 10}, /* 00 11 10 01 */ { 2, 6, 9, 1, 4, 3, 2, 11}, /* 00 11 10 10 */ { 2, 6, 9, 1, 4, 3, 3, 12}, /* 00 11 10 11 */ { 2, 6, 9, 1, 4, 3, 4, 13}, /* 00 11 11 00 */ { 2, 6, 10 , 1, 4, 4, 1, 11}, /* 00 11 11 01 */ { 2, 6, 10 , 1, 4, 4, 2, 12 }, /* 00 11 11 10 */ { 2, 6, 10 , 1, 4, 4, 3, 13 }, /* 00 11 11 11 */ { 2, 6, 10 , 1, 4, 4, 4, 14 }, /* 01 00 00 00 */ { 3, 4, 5, 2, 1, 1, 1, 6}, /* 01 00 00 01 */ { 3, 4, 5, 2, 1, 1, 2, 7}, /* 01 00 00 10 */ { 3, 4, 5, 2, 1, 1, 3, 8}, /* 01 00 00 11 */ { 3, 4, 5, 2, 1, 1, 4, 9}, /* 01 00 01 00 */ { 3, 4, 6, 2, 1, 2, 1, 7}, /* 01 00 01 01 */ { 3, 4, 6, 2, 1, 2, 2, 8}, /* 01 00 01 10 */ { 3, 4, 6, 2, 1, 2, 3, 9}, /* 01 00 01 11 */ { 3, 4, 6, 2, 1, 2, 4, 10}, /* 01 00 10 00 */ { 3, 4, 7, 2, 1, 3, 1, 8}, /* 01 00 10 01 */ { 3, 4, 7, 2, 1, 3, 2, 9}, /* 01 00 10 10 */ { 3, 4, 7, 2, 1, 3, 3, 10}, /* 01 00 10 11 */ { 3, 4, 7, 2, 1, 3, 4, 11}, /* 01 00 11 00 */ { 3, 4, 8, 2, 1, 4, 1, 9}, /* 01 00 11 01 */ { 3, 4, 8, 2, 1, 4, 2, 10}, /* 01 00 11 10 */ { 3, 4, 8, 2, 1, 4, 3, 11}, /* 01 00 11 11 */ { 3, 4, 8, 2, 1, 4, 4, 12}, /* 01 01 00 00 */ { 3, 5, 6, 2, 2, 1, 1, 7}, /* 01 01 00 01 */ { 3, 5, 6, 2, 2, 1, 2, 8}, /* 01 01 00 10 */ { 3, 5, 6, 2, 2, 1, 3, 9}, /* 01 01 00 11 */ { 3, 5, 6, 2, 2, 1, 4, 10}, /* 01 01 01 00 */ { 3, 5, 7, 2, 2, 2, 1, 8}, /* 01 01 01 01 */ { 3, 5, 7, 2, 2, 2, 2, 9}, /* 01 01 01 10 */ { 3, 5, 7, 2, 2, 2, 3, 10}, /* 01 01 01 11 */ { 3, 5, 7, 2, 2, 2, 4, 11}, /* 01 01 10 00 */ { 3, 5, 8, 2, 2, 3, 1, 9}, /* 01 01 10 01 */ { 3, 5, 8, 2, 2, 3, 2, 10}, /* 01 01 10 10 */ { 3, 5, 8, 2, 2, 3, 3, 11}, /* 01 01 10 11 */ { 3, 5, 8, 2, 2, 3, 4, 12}, /* 01 01 11 00 */ { 3, 5, 9, 2, 2, 4, 1, 10}, /* 01 01 11 01 */ { 3, 5, 9, 2, 2, 4, 2, 11}, /* 01 01 11 10 */ { 3, 5, 9, 2, 2, 4, 3, 12}, /* 01 01 11 11 */ { 3, 5, 9, 2, 2, 4, 4, 13}, /* 01 10 00 00 */ { 3, 6, 7, 2, 3, 1, 1, 8}, /* 01 10 00 01 */ { 3, 6, 7, 2, 3, 1, 2, 9}, /* 01 10 00 10 */ { 3, 6, 7, 2, 3, 1, 3, 10}, /* 01 10 00 11 */ { 3, 6, 7, 2, 3, 1, 4, 11}, /* 01 10 01 00 */ { 3, 6, 8, 2, 3, 2, 1, 9}, /* 01 10 01 01 */ { 3, 6, 8, 2, 3, 2, 2, 10}, /* 01 10 01 10 */ { 3, 6, 8, 2, 3, 2, 3, 11}, /* 01 10 01 11 */ { 3, 6, 8, 2, 3, 2, 4, 12}, /* 01 10 10 00 */ { 3, 6, 9, 2, 3, 3, 1, 10}, /* 01 10 10 01 */ { 3, 6, 9, 2, 3, 3, 2, 11}, /* 01 10 10 10 */ { 3, 6, 9, 2, 3, 3, 3, 12}, /* 01 10 10 11 */ { 3, 6, 9, 2, 3, 3, 4, 13}, /* 01 10 11 00 */ { 3, 6, 10 , 2, 3, 4, 1 , 11}, /* 01 10 11 01 */ { 3, 6, 10 , 2, 3, 4, 2 , 12}, /* 01 10 11 10 */ { 3, 6, 10 , 2, 3, 4, 3 , 13}, /* 01 10 11 11 */ { 3, 6, 10 , 2, 3, 4, 4 , 14}, /* 01 11 00 00 */ { 3, 7, 8, 2, 4, 1, 1, 9}, /* 01 11 00 01 */ { 3, 7, 8, 2, 4, 1, 2, 10}, /* 01 11 00 10 */ { 3, 7, 8, 2, 4, 1, 3, 11}, /* 01 11 00 11 */ { 3, 7, 8, 2, 4, 1, 4, 12}, /* 01 11 01 00 */ { 3, 7, 9, 2, 4, 2, 1, 10}, /* 01 11 01 01 */ { 3, 7, 9, 2, 4, 2, 2, 11}, /* 01 11 01 10 */ { 3, 7, 9, 2, 4, 2, 3, 12}, /* 01 11 01 11 */ { 3, 7, 9, 2, 4, 2, 4, 13}, /* 01 11 10 00 */ { 3, 7, 10 , 2, 4, 3, 1 , 11}, /* 01 11 10 01 */ { 3, 7, 10 , 2, 4, 3, 2 , 12}, /* 01 11 10 10 */ { 3, 7, 10 , 2, 4, 3, 3 , 13}, /* 01 11 10 11 */ { 3, 7, 10 , 2, 4, 3, 4 , 14}, /* 01 11 11 00 */ { 3, 7, 11 , 2, 4, 4, 1 , 12}, /* 01 11 11 01 */ { 3, 7, 11 , 2, 4, 4, 2 , 13}, /* 01 11 11 10 */ { 3, 7, 11 , 2, 4, 4, 3 , 14}, /* 01 11 11 11 */ { 3, 7, 11 , 2, 4, 4, 4 , 15}, /* 10 00 00 00 */ { 4, 5, 6, 3, 1, 1, 1, 7}, /* 10 00 00 01 */ { 4, 5, 6, 3, 1, 1, 2, 8}, /* 10 00 00 10 */ { 4, 5, 6, 3, 1, 1, 3, 9}, /* 10 00 00 11 */ { 4, 5, 6, 3, 1, 1, 4, 10}, /* 10 00 01 00 */ { 4, 5, 7, 3, 1, 2, 1, 8}, /* 10 00 01 01 */ { 4, 5, 7, 3, 1, 2, 2, 9}, /* 10 00 01 10 */ { 4, 5, 7, 3, 1, 2, 3, 10}, /* 10 00 01 11 */ { 4, 5, 7, 3, 1, 2, 4, 11}, /* 10 00 10 00 */ { 4, 5, 8, 3, 1, 3, 1, 9}, /* 10 00 10 01 */ { 4, 5, 8, 3, 1, 3, 2, 10}, /* 10 00 10 10 */ { 4, 5, 8, 3, 1, 3, 3, 11}, /* 10 00 10 11 */ { 4, 5, 8, 3, 1, 3, 4, 12}, /* 10 00 11 00 */ { 4, 5, 9, 3, 1, 4, 1, 10}, /* 10 00 11 01 */ { 4, 5, 9, 3, 1, 4, 2, 11}, /* 10 00 11 10 */ { 4, 5, 9, 3, 1, 4, 3, 12}, /* 10 00 11 11 */ { 4, 5, 9, 3, 1, 4, 4, 13}, /* 10 01 00 00 */ { 4, 6, 7, 3, 2, 1, 1, 8}, /* 10 01 00 01 */ { 4, 6, 7, 3, 2, 1, 2, 9}, /* 10 01 00 10 */ { 4, 6, 7, 3, 2, 1, 3, 10}, /* 10 01 00 11 */ { 4, 6, 7, 3, 2, 1, 4, 11}, /* 10 01 01 00 */ { 4, 6, 8, 3, 2, 2, 1, 9}, /* 10 01 01 01 */ { 4, 6, 8, 3, 2, 2, 2, 10}, /* 10 01 01 10 */ { 4, 6, 8, 3, 2, 2, 3, 11}, /* 10 01 01 11 */ { 4, 6, 8, 3, 2, 2, 4, 12}, /* 10 01 10 00 */ { 4, 6, 9, 3, 2, 3, 1, 10}, /* 10 01 10 01 */ { 4, 6, 9, 3, 2, 3, 2, 11}, /* 10 01 10 10 */ { 4, 6, 9, 3, 2, 3, 3, 12}, /* 10 01 10 11 */ { 4, 6, 9, 3, 2, 3, 4, 13}, /* 10 01 11 00 */ { 4, 6, 10 , 3, 2, 4, 1, 11 }, /* 10 01 11 01 */ { 4, 6, 10 , 3, 2, 4, 2, 12 }, /* 10 01 11 10 */ { 4, 6, 10 , 3, 2, 4, 3, 13 }, /* 10 01 11 11 */ { 4, 6, 10 , 3, 2, 4, 4, 14 }, /* 10 10 00 00 */ { 4, 7, 8, 3, 3, 1, 1, 9}, /* 10 10 00 01 */ { 4, 7, 8, 3, 3, 1, 2, 10}, /* 10 10 00 10 */ { 4, 7, 8, 3, 3, 1, 3, 11}, /* 10 10 00 11 */ { 4, 7, 8, 3, 3, 1, 4, 12}, /* 10 10 01 00 */ { 4, 7, 9, 3, 3, 2, 1, 10}, /* 10 10 01 01 */ { 4, 7, 9, 3, 3, 2, 2, 11}, /* 10 10 01 10 */ { 4, 7, 9, 3, 3, 2, 3, 12}, /* 10 10 01 11 */ { 4, 7, 9, 3, 3, 2, 4, 13}, /* 10 10 10 00 */ { 4, 7, 10 , 3, 3, 3, 1, 11 }, /* 10 10 10 01 */ { 4, 7, 10 , 3, 3, 3, 2, 12 }, /* 10 10 10 10 */ { 4, 7, 10 , 3, 3, 3, 3, 13 }, /* 10 10 10 11 */ { 4, 7, 10 , 3, 3, 3, 4, 14 }, /* 10 10 11 00 */ { 4, 7, 11 , 3, 3, 4, 1, 12 }, /* 10 10 11 01 */ { 4, 7, 11 , 3, 3, 4, 2, 13 }, /* 10 10 11 10 */ { 4, 7, 11 , 3, 3, 4, 3, 14 }, /* 10 10 11 11 */ { 4, 7, 11 , 3, 3, 4, 4, 15 }, /* 10 11 00 00 */ { 4, 8, 9, 3, 4, 1, 1, 10}, /* 10 11 00 01 */ { 4, 8, 9, 3, 4, 1, 2, 11}, /* 10 11 00 10 */ { 4, 8, 9, 3, 4, 1, 3, 12}, /* 10 11 00 11 */ { 4, 8, 9, 3, 4, 1, 4, 13}, /* 10 11 01 00 */ { 4, 8, 10 , 3, 4, 2, 1, 11 }, /* 10 11 01 01 */ { 4, 8, 10 , 3, 4, 2, 2, 12 }, /* 10 11 01 10 */ { 4, 8, 10 , 3, 4, 2, 3, 13 }, /* 10 11 01 11 */ { 4, 8, 10 , 3, 4, 2, 4, 14 }, /* 10 11 10 00 */ { 4, 8, 11 , 3, 4, 3, 1, 12 }, /* 10 11 10 01 */ { 4, 8, 11 , 3, 4, 3, 2, 13 }, /* 10 11 10 10 */ { 4, 8, 11 , 3, 4, 3, 3, 14 }, /* 10 11 10 11 */ { 4, 8, 11 , 3, 4, 3, 4, 15 }, /* 10 11 11 00 */ { 4, 8, 12 , 3, 4, 4, 1, 13 }, /* 10 11 11 01 */ { 4, 8, 12 , 3, 4, 4, 2, 14 }, /* 10 11 11 10 */ { 4, 8, 12 , 3, 4, 4, 3, 15 }, /* 10 11 11 11 */ { 4, 8, 12 , 3, 4, 4, 4, 16 }, /* 11 00 00 00 */ { 5, 6, 7, 4, 1, 1, 1, 8}, /* 11 00 00 01 */ { 5, 6, 7, 4, 1, 1, 2, 9}, /* 11 00 00 10 */ { 5, 6, 7, 4, 1, 1, 3, 10}, /* 11 00 00 11 */ { 5, 6, 7, 4, 1, 1, 4, 11}, /* 11 00 01 00 */ { 5, 6, 8, 4, 1, 2, 1, 9}, /* 11 00 01 01 */ { 5, 6, 8, 4, 1, 2, 2, 10}, /* 11 00 01 10 */ { 5, 6, 8, 4, 1, 2, 3, 11}, /* 11 00 01 11 */ { 5, 6, 8, 4, 1, 2, 4, 12}, /* 11 00 10 00 */ { 5, 6, 9, 4, 1, 3, 1, 10}, /* 11 00 10 01 */ { 5, 6, 9, 4, 1, 3, 2, 11}, /* 11 00 10 10 */ { 5, 6, 9, 4, 1, 3, 3, 12}, /* 11 00 10 11 */ { 5, 6, 9, 4, 1, 3, 4, 13}, /* 11 00 11 00 */ { 5, 6, 10 , 4, 1, 4, 1, 11 }, /* 11 00 11 01 */ { 5, 6, 10 , 4, 1, 4, 2, 12 }, /* 11 00 11 10 */ { 5, 6, 10 , 4, 1, 4, 3, 13 }, /* 11 00 11 11 */ { 5, 6, 10 , 4, 1, 4, 4, 14 }, /* 11 01 00 00 */ { 5, 7, 8, 4, 2, 1, 1, 9}, /* 11 01 00 01 */ { 5, 7, 8, 4, 2, 1, 2, 10}, /* 11 01 00 10 */ { 5, 7, 8, 4, 2, 1, 3, 11}, /* 11 01 00 11 */ { 5, 7, 8, 4, 2, 1, 4, 12}, /* 11 01 01 00 */ { 5, 7, 9, 4, 2, 2, 1, 10}, /* 11 01 01 01 */ { 5, 7, 9, 4, 2, 2, 2, 11}, /* 11 01 01 10 */ { 5, 7, 9, 4, 2, 2, 3, 12}, /* 11 01 01 11 */ { 5, 7, 9, 4, 2, 2, 4, 13}, /* 11 01 10 00 */ { 5, 7, 10 , 4, 2, 3, 1 , 11}, /* 11 01 10 01 */ { 5, 7, 10 , 4, 2, 3, 2 , 12}, /* 11 01 10 10 */ { 5, 7, 10 , 4, 2, 3, 3 , 13}, /* 11 01 10 11 */ { 5, 7, 10 , 4, 2, 3, 4 , 14}, /* 11 01 11 00 */ { 5, 7, 11 , 4, 2, 4, 1 , 12}, /* 11 01 11 01 */ { 5, 7, 11 , 4, 2, 4, 2 , 13}, /* 11 01 11 10 */ { 5, 7, 11 , 4, 2, 4, 3 , 14}, /* 11 01 11 11 */ { 5, 7, 11 , 4, 2, 4, 4 , 15}, /* 11 10 00 00 */ { 5, 8, 9, 4, 3, 1, 1, 10}, /* 11 10 00 01 */ { 5, 8, 9, 4, 3, 1, 2, 11}, /* 11 10 00 10 */ { 5, 8, 9, 4, 3, 1, 3, 12}, /* 11 10 00 11 */ { 5, 8, 9, 4, 3, 1, 4, 13}, /* 11 10 01 00 */ { 5, 8, 10 , 4, 3, 2, 1 , 11}, /* 11 10 01 01 */ { 5, 8, 10 , 4, 3, 2, 2 , 12}, /* 11 10 01 10 */ { 5, 8, 10 , 4, 3, 2, 3 , 13}, /* 11 10 01 11 */ { 5, 8, 10 , 4, 3, 2, 4 , 14}, /* 11 10 10 00 */ { 5, 8, 11 , 4, 3, 3, 1 , 12}, /* 11 10 10 01 */ { 5, 8, 11 , 4, 3, 3, 2 , 13}, /* 11 10 10 10 */ { 5, 8, 11 , 4, 3, 3, 3 , 14}, /* 11 10 10 11 */ { 5, 8, 11 , 4, 3, 3, 4 , 15}, /* 11 10 11 00 */ { 5, 8, 12 , 4, 3, 4, 1, 13 }, /* 11 10 11 01 */ { 5, 8, 12 , 4, 3, 4, 2, 14 }, /* 11 10 11 10 */ { 5, 8, 12 , 4, 3, 4, 3, 15 }, /* 11 10 11 11 */ { 5, 8, 12 , 4, 3, 4, 4, 16 }, /* 11 11 00 00 */ { 5, 9, 10 , 4, 4, 1, 1, 11 }, /* 11 11 00 01 */ { 5, 9, 10 , 4, 4, 1, 2, 12 }, /* 11 11 00 10 */ { 5, 9, 10 , 4, 4, 1, 3, 13 }, /* 11 11 00 11 */ { 5, 9, 10 , 4, 4, 1, 4, 14 }, /* 11 11 01 00 */ { 5, 9, 11 , 4, 4, 2, 1, 12 }, /* 11 11 01 01 */ { 5, 9, 11 , 4, 4, 2, 2, 13 }, /* 11 11 01 10 */ { 5, 9, 11 , 4, 4, 2, 3, 14 }, /* 11 11 01 11 */ { 5, 9, 11 , 4, 4, 2, 4, 15 }, /* 11 11 10 00 */ { 5, 9, 12 , 4, 4, 3, 1, 13 }, /* 11 11 10 01 */ { 5, 9, 12 , 4, 4, 3, 2, 14 }, /* 11 11 10 10 */ { 5, 9, 12 , 4, 4, 3, 3, 15 }, /* 11 11 10 11 */ { 5, 9, 12 , 4, 4, 3, 4, 16 }, /* 11 11 11 00 */ { 5, 9, 13 , 4, 4, 4, 1, 14 }, /* 11 11 11 01 */ { 5, 9, 13 , 4, 4, 4, 2, 15 }, /* 11 11 11 10 */ { 5, 9, 13 , 4, 4, 4, 3, 16 }, /* 11 11 11 11 */ { 5, 9, 13 , 4, 4, 4, 4, 17} }; /** * 将一个uint32整数 做 varint 编码 输出到 buf中 * * @param value 输出的值 * @param target 输出的缓冲 , 需确保buf 空间是够用的 * * @return target中下一个可用的字节位置 */ inline uint8_t * varint_encode_uint32 ( uint32_t value, uint8_t * target ) { if ( value >= (1 << 7) ) { target[0] = (uint8_t)(value | 0x80); // 取低7位， 前面补 1 if ( value >= (1 << 14) ) { target[1] = (uint8_t)( (value >> 7) | 0x80 ); // 取次低7位，前面补 1 if ( value >= (1 << 21) ) { // 取第3个 低7位，前面补 1 target[2] = (uint8_t)( (value >> 14) | 0x80 ); if ( value >= (1 << 28) ) { // 取第4个 低7位，前面补 1 target[3] = (uint8_t)((value >> 21) | 0x80); // 剩余的高4位 target[4] = (uint8_t)(value >> 28); return target + 5; } else { target[3] = (uint8_t)( value >> 21 ); return target + 4; } } else { target[2] = (uint8_t)( value >> 14 ); return target + 3; } } else { target[1] = (uint8_t)( value >> 7 ); return target + 2; } } else { target[0] = (uint8_t) value; return target + 1; } } /** * 从buf中 将 varint压缩编码的值 还原读取出来 * 需要确保输入的buf 从 输出的指针到结尾 超过 5个byte, 避免出现core * 函数内部不做边界检查 * * @param buffer 输入的buf * @param value 输出的值 * * @return target中下一个可读的字节位置 */ inline const uint8_t * varint_decode_uint32( const uint8_t * buffer, uint32_t & value ) { register const uint8_t * ptr = buffer; // 低7位， 小于 128 的数字 register uint8_t b0 = ptr[ 0 ]; register uint32_t r0 = (b0 & 0x7F); if (UNLIKELY( !(b0 & 0x80) )) { value = r0; return ptr + 1; } // 低14位, 小于 16384 的数字 register uint8_t b1 = ptr[ 1 ]; register uint32_t r1 = (b1 & 0x7F) << 7; if (UNLIKELY( !(b1 & 0x80) )) { value = ( r1 | r0 ); return ptr + 2; } // 低21位, 小于 2097152 的数字 register uint8_t b2 = ptr[ 2 ]; register uint32_t r2 = (b2 & 0x7F) << 14; if (UNLIKELY( !(b2 & 0x80) )) { value = ( r2 | r1 | r0 ); return ptr + 3; } // 低28位, 小于 268435456 的数字 register uint8_t b3 = ptr[ 3 ]; register uint32_t r3 = (b3 & 0x7F) << 21; if ( !(b3 & 0x80) ) { value = ( r3 | r2 | r1 | r0 ); return ptr + 4; } // 完整的32位 value = ( ((ptr[ 4 ]) << 28) | r3 | r2 | r1 | r0 ); return ptr + 5; } /** * 从buf中 指定的字节数中 将 varint压缩编码的值 还原读取出来 * 指定的字节数 也许是 不足的， 比如： 截断掉了， 这样就返回NULL * * @param buffer 输入的buf * @param value 输出的值 * * @return target中下一个可读的字节位置, 如果buffer异常 返回NULL */ inline const uint8_t * varint_decode_uint32( const uint8_t * buffer, uint32_t len, uint32_t & value ) { if ( len >= 5 ) // len == 0 就不考虑了 return varint_decode_uint32( buffer, value ); register const uint8_t * ptr = buffer; // 低7位， 小于 128 的数字 register uint8_t b0 = ptr[ 0 ]; register uint32_t r0 = (b0 & 0x7F); if (UNLIKELY( !(b0 & 0x80) )) { value = r0; return ptr + 1; } if (UNLIKELY( len < 2 )) return NULL; // 低14位, 小于 16384 的数字 register uint8_t b1 = ptr[ 1 ]; register uint32_t r1 = (b1 & 0x7F) << 7; if (UNLIKELY( !(b1 & 0x80) )) { value = ( r1 | r0 ); return ptr + 2; } if (UNLIKELY( len < 3 )) return NULL; // 低21位, 小于 2097152 的数字 register uint8_t b2 = ptr[ 2 ]; register uint32_t r2 = (b2 & 0x7F) << 14; if (UNLIKELY( !(b2 & 0x80) )) { value = ( r2 | r1 | r0 ); return ptr + 3; } if (UNLIKELY( len < 4 )) return NULL; // 低28位, 小于 268435456 的数字 register uint8_t b3 = ptr[ 3 ]; register uint32_t r3 = (b3 & 0x7F) << 21; if ( !(b3 & 0x80) ) { value = ( r3 | r2 | r1 | r0 ); return ptr + 4; } if ( len < 5 ) return NULL; // 完整的32位 value = ( ((ptr[ 4 ]) << 28) | r3 | r2 | r1 | r0 ); return ptr + 5; } /** 解压时 并不把实际值取得， 只获取下一个可解压位置, 一次忽略 1个 uint32 */ inline const uint8_t * varint_decode_uint32_skip( const uint8_t * buffer ) { if (UNLIKELY( !(buffer[ 0 ] & 0x80) )) return buffer + 1; if (UNLIKELY( !(buffer[ 1 ] & 0x80) )) return buffer + 2; if (UNLIKELY( !(buffer[ 2 ] & 0x80) )) return buffer + 3; if ( !(buffer[ 3 ] & 0x80) ) return buffer + 4; return buffer + 5; } /** * 将一个uint64整数 做 varint 编码 输出到 buf中 * * @param value 输出的值 * @param target 输出的缓冲 , 需确保buf 空间是够用的 * * @return target中下一个可用的字节位置 */ inline uint8_t * varint_encode_uint64 ( uint64_t value, uint8_t * target ) { // 拆分成高32位和低32位 target = varint_encode_uint32( value >> 32, target ); return varint_encode_uint32( value & 0xFFFFFFFF, target ); } /** * 从buf中 将 varint压缩编码的值 还原读取出来 * 需要确保输入的buf 从 输出的指针到结尾 超过 5个byte, 避免出现core * 函数内部不做边界检查 * * @param buffer 输入的buf * @param value 输出的值 * * @return target中下一个可读的字节位置 */ inline const uint8_t * varint_decode_uint64(const uint8_t * buffer, uint64_t & value) { uint32_t high = 0; uint32_t low = 0; buffer = varint_decode_uint32( buffer, high ); buffer = varint_decode_uint32( buffer, low ); value = ((uint64_t)high << 32) + low ; return buffer; } /** 解压时 并不把实际值取得， 只获取下一个可解压位置, 一次忽略 1个uint64 */ inline const uint8_t * varint_decode_uint64_skip( const uint8_t * buffer ) { buffer = varint_decode_uint32_skip( buffer ); return varint_decode_uint32_skip( buffer ); } /** * 对整数数组进行 group varint编码, 一次处理 4个整数 * * @param valueArr 无符号整数的数组 元素个数， 必须是4的倍数。 多余不处理 * @param target 用于输出的buf . 需要确够大 ， 4个整数最多用 17个byte * * @return target下一个可写byte */ inline uint8_t * group_varint_encode_uint32( const uint32_t * valueArr, uint8_t * target) { register uint8_t len1; // 第 1 个数字用的 字节数 register uint8_t len2; // 第 2 个数字用的 字节数 register uint8_t len3; // 第 3 个数字用的 字节数 register uint8_t len4; // 第 4 个数字用的 字节数 register uint32_t val1 = valueArr[0]; register uint32_t val2 = valueArr[1]; register uint32_t val3 = valueArr[2]; register uint32_t val4 = valueArr[3]; register uint8_t * buf = target + 1; if ( val1 > UINT24_MAX ) { len1 = 4; ((uint32_t *)(buf))[0] = val1; } else if ( val1 > UINT16_MAX ) { len1 = 3; ((uint32_t *)(buf))[0] = val1; } else if ( val1 > UINT8_MAX ) { len1 = 2; ((uint16_t *)(buf))[0] = (uint16_t) val1; } else { len1 = 1; buf[0] = (uint8_t) val1; } register uint8_t len = len1; // 4个数字总共用的 字节数 /* 处理第二个数字 */ if (UNLIKELY( val2 > UINT24_MAX )) { len2 = 4; ((uint32_t *)(buf + len))[0] = val2; } else if ( val2 > UINT16_MAX ) { len2 = 3; ((uint32_t *)(buf + len))[0] = val2; } else if ( val2 > UINT8_MAX ) { len2 = 2; ((uint16_t *)(buf + len))[0] = (uint16_t) val2; } else { len2 = 1; buf[len] = (uint8_t) val2; } len += len2; /* 处理第3个数字 */ if (UNLIKELY( val3 > UINT24_MAX )) { len3 = 4; ((uint32_t *)(buf + len))[0] = val3; } else if ( val3 > UINT16_MAX ) { len3 = 3; ((uint32_t *)(buf + len))[0] = val3; } else if ( val3 > UINT8_MAX ) { len3 = 2; ((uint16_t *)(buf + len))[0] = (uint16_t) val3; } else { len3 = 1; buf[len] = (uint8_t) val3; } len += len3; /* 处理第4个数字 */ if (UNLIKELY( val4 > UINT24_MAX )) { len4 = 4; ((uint32_t *)(buf + len))[0] = val4; } else if ( val4 > UINT16_MAX ) { len4 = 3; ((uint32_t *)(buf + len))[0] = val4; } else if ( val4 > UINT8_MAX ) { len4 = 2; ((uint16_t *)(buf + len))[0] = (uint16_t) val4; } else { len4 = 1; buf[len] = (uint8_t) val4; } len += len4; /* 处理第一个索引字节 */ target[0] = ((len1 - 1) << 6) | ((len2 - 1) << 4) | ((len3 - 1) << 2) | (len4 - 1); return buf + len; } /** * 对输入的buf进行解压， 每次一定解压出4个整数 * * @param buf 输入的buf * @param valueArr 输出的数组， 需要预先开辟为4个整数的数组 * * @return target下一个可读byte */ inline const uint8_t * group_varint_decode_uint32 ( const uint8_t * buf, uint32_t * valueArr) { register uint8_t idx = buf[ 0 ]; const uint8_t * star1 = buf + 1; const uint8_t * star2 = buf + GROUP_VARINT_IDX_ARR[idx][0]; const uint8_t * star3 = buf + GROUP_VARINT_IDX_ARR[idx][1]; const uint8_t * star4 = buf + GROUP_VARINT_IDX_ARR[idx][2]; switch ( GROUP_VARINT_IDX_ARR[idx][3] ) { case 1 : valueArr[ 0 ] = *(uint8_t *) star1; break; case 2 : valueArr[ 0 ] = *(uint16_t *) star1; break; case 3 : valueArr[ 0 ] = (*(UINT24_T *)star1).value ; break; default: valueArr[ 0 ] = *(uint32_t *) star1; } switch ( GROUP_VARINT_IDX_ARR[idx][4] ) { case 1 : valueArr[ 1 ] = *(uint8_t *) star2; break; case 2 : valueArr[ 1 ] = *(uint16_t *) star2; break; case 3 : valueArr[ 1 ] = (*(UINT24_T *)star2).value; break; default: valueArr[ 1 ] = *(uint32_t *) star2; } switch ( GROUP_VARINT_IDX_ARR[idx][5] ) { case 1 : valueArr[ 2 ] = *(uint8_t *) star3; break; case 2 : valueArr[ 2 ] = *(uint16_t *) star3; break; case 3 : valueArr[ 2 ] = (*(UINT24_T *)star3).value; break; default: valueArr[ 2 ] = *(uint32_t *) star3; } switch ( GROUP_VARINT_IDX_ARR[idx][6] ) { case 1 : valueArr[ 3 ] = *(uint8_t *) star4; break; case 2 : valueArr[ 3 ] = *(uint16_t *) star4; break; case 3 : valueArr[ 3 ] = (*(UINT24_T *)star4).value; break; default: valueArr[ 3 ] = *(uint32_t *) star4; } return buf + GROUP_VARINT_IDX_ARR[ idx ][ 7 ]; } /** 解压时 并不把实际值取得， 只获取下一个可解压位置, 一次忽略 4个uint32 */ inline const uint8_t * group_varint_decode_uint32_skip ( const uint8_t * buf ) { return buf + GROUP_VARINT_IDX_ARR[ buf[ 0 ] ][ 7 ]; } /** * 对整数数组进行 group varint编码, 一次处理 2个 uint64整数 * * @param valueArr 无符号整数的数组 元素个数， 必须是2的倍数。 多余不处理 * @param target 用于输出的buf . 需要确够大 ， 2个uint64整数最多用 17个byte * * @return target下一个可写byte */ inline uint8_t * group_varint_encode_uint64 ( const uint64_t * valueArr, uint8_t * target) { uint32_t arr[ 4 ] = { valueArr[0] >> 32, (valueArr[0] << 32) >> 32, valueArr[1] >> 32, (valueArr[1] << 32) >> 32 }; return group_varint_encode_uint32( arr, target); } inline uint8_t * group_varint_encode_uint32 ( uint32_t v1,uint32_t v2, uint32_t v3, uint32_t v4, uint8_t * target) { uint32_t valueArr[ 4 ] = {v1, v2 ,v3 ,v4}; return group_varint_encode_uint32( valueArr, target); } inline uint8_t * group_varint_encode_uint64 ( uint64_t v1, uint64_t v2, uint8_t * target) { uint32_t valueArr[ 4 ] = { v1 >> 32, (v1 << 32) >> 32, v2 >> 32, (v2 << 32) >> 32 }; return group_varint_encode_uint32( valueArr, target); } /** * 对输入的buf进行解压， 每次一定解压出2个uint64整数 * * @param buf 输入的buf * @param valueArr 输出的数组， 需要预先开辟为2个uint64整数的数组 * * @return buf 下一个可读byte */ inline const uint8_t * group_varint_decode_uint64 ( const uint8_t * buf, uint64_t * valueArr ) { uint32_t int_arr[ 4 ] = {0}; buf = group_varint_decode_uint32 ( buf, int_arr ); valueArr[ 0 ] = (((uint64_t)(int_arr[0])) << 32) + int_arr[1]; valueArr[ 1 ] = (((uint64_t)(int_arr[2])) << 32) + int_arr[3]; return buf; } /** 解压时 并不把实际值取得， 只获取下一个可解压位置 , 一次忽略2个 uint64 */ inline const uint8_t * group_varint_decode_uint64_skip( const uint8_t * buf ) { return group_varint_decode_uint32_skip ( buf ); } /** * 对整数进行 zigZag编码， 有符号数 转换为 无符号数 * * @param n 有符号数 * * @return 无符号数 */ inline uint32_t zigZag_encode32(int32_t n) { return (n << 1) ^ (n >> 31); } inline uint64_t zigZag_encode64(int64_t n) { return (n << 1) ^ (n >> 63); } /** * 对整数进行 zigZag 解码， 无符号数 转换为 有符号数 * * @param n 无符号数 * * @return 有符号数 */ inline int32_t zigZag_decode32(uint32_t n) { return (n >> 1) ^ -(int32_t)(n & 1); } inline int64_t zigZag_decode64(uint64_t n) { return (n >> 1) ^ -(int64_t)(n & 1); } } #endif /* VARINT_H_ */
相关 [google group varint] 推荐：
kafka consumer group offset
- - 开源软件 - ITeye博客 kafka0.9及以前版本kafka offset 保存在zookeeper， 因频繁读写zookeeper性能不高；从0.10开始，主题分区offset存储于kafka独立主题中. 管理监控kafka主题及分区offset至关重要，原网上很开源流行工具KafkaOffsetMonitor、kafka-manager，旧版offset保存于zookeeper，kafka consumer无相应API，从kafka0.10.1.1以后提供相应API读取主题分区offset（也可以调用KafkaClient API，kafka管理API由scala语言编写）.
solr中facet、group查询
- - 编程语言 - ITeye博客项目(评论)中使用solr查询的时候，有个场景需求：. 1、获取某个商品下评论的级别数量统计（比如该商品下一到五颗星的评论数量各有多少）；. 最终经过讨论，使用了solr中的group和facet完成. 先说下solr中保存的文档数据结构，如下：.
.
Mapreduce实例-分组排重（group by distinct）
- - CSDN博客云计算推荐文章需要实现以下几个类,代码太多，列了下主要代码，可根据排重数据的特征判读是否需要添加combiner来提速. job.setPartitionerClass(MyPartitioner.class);
map略. combiner（根据需要添加）
reduce中的实现：. 作者：liuzhoulong 发表于2013-9-5 22:17:26 原文链接.
量化InnoDB group commit的效果
- - OurMySQL前几天有位开发的同学问了个问题，InnoDB的group commit效果如何. 之前说好了回头给看下，结果险些拖过年. Group commit 背景. InnoDB的redo log的group commit历史比较悠久了（有别于binlog的group commit）. 如果设置为1，每次事务提交都至少需要写一次redolog.
Lucene5学习之Group分组统计
- - ITeye博客 Group即分组，类似SQL里的group by功能，Lucene中分组是通过内置的几种Collector结果集收集器实现的，有关group的结果集收集器都在org.apache.lucene.search.grouping包及其子包下，. 包含group关键字的Collector都是有关Group分组的结果收集器，如果你只需要统计如下这些分组信息:.
Hive高级查询(group by、 order by、 join等)
- - CSDN博客推荐文章所有值不全为NULL时，加1操作
count(1). 不管有没有值，只要有这条记录，值就加1
count(col) col列里面的值为null，值不会加1，这个列里面的值不为NULL，才加1. sum(可转成数字的值） 返回bigint. avg（可转成数字的值）返回double. distinct不同值个数.
关于Elasticsearch里面聚合group的坑
- - ITeye博客原来知道Elasticsearch在分组聚合时有一些坑但没有细究，今天又看了遍顺便做个笔记和大家分享一下. 我们都知道Elasticsearch是一个分布式的搜索引擎，每个索引都可以有多个分片，用来将一份大索引的数据切分成多个小的物理索引，解决单个索引数据量过大导致的性能问题，另外每个shard还可以配置多个副本，来保证高可靠以及更好的抗并发的能力.
面试笔试常考的mysql 数据库操作group by
- - CSDN博客数据库推荐文章IT 面试中，数据库的相关问题基本上属于必考问题，而其中关于sql语句也是经常考察的一个重要知识点. 下面介绍下sql语句中一个比较重要的操作group by，他的重要行一方面体现在他的理解困难度，一方面体现应用中的长见性. 首先，给出一个studnet学生表：. 给出各个部门最高学生的分数. 要想得到各个部门学生，首先就要分组，按照部门把他们分组，然后在各个部门中找到分数最高的就可以了.
多个Consumer Group对Topic消费不能完全覆盖研究总结（一） - 凌晨三点半 - 博客园
- -我们知道Kafka支持Consumer Group的功能，但是最近在应用Consumer Group时发现了一个Topic 的Partition不能100%覆盖的问题. 程序部署后，发现Kafka在pdb组的consumer消费topic时存在问题，consumer无法完全覆盖Topic的各个partition.