一 数据压缩
1 去冗余
数字压缩基本原理
将数字分为若干个桶,桶的大小可以调节(比如可以 1KB 一个桶,4KB 一个桶等)。
我们使用另一个数组,大小为桶的数量,存储每个桶所第一个数据所在的下标。
在查找时我首先使用二分查找到对应的桶,再使用线性查找到对应的数据。
2 偏移量存储
二 存取优化
1 变固定长度桶为变长桶
2 编写专用迭代器
3 减少中间数据,使用栈直传递共用
计算数字所在的桶与偏移量,然后将其包装成 ByteBuffer。
使用包装好的 ByteBuffer 线性分析字节数组,通过偏移量查找桶内数字。
依据数字的长度信息(即前三个位)将对应的字节复制至一个临时数组中。
将临时数组传入 inflate 方法进行解压。
public long get(int ix) {
// 首先寻找 shard, 由于每个桶存储固定数量的数字,因此可以直接映射
int i = ix / SHARD_SIZE;
// 剩下的为需要线性查找的偏移量
ix %= SHARD_SIZE;
ByteBuffer buf = ByteBuffer.wrap(shards[i]);
// 找到对应数据的偏移量
long offset = 0;
if (ix > 0) {
int len = (Byte.toUnsignedInt(buf.get(0)) >>> 5);
byte[] bag = new byte[len];
buf.get(bag, 0, len);
offset = inflate(bag);
}
// 重置位置
buf.position(0);
int numPos = 0;
while (ix > 0) {
int len = (Byte.toUnsignedInt(buf.get(numPos)) >>> 5);
numPos += len;
ix -= 1;
}
buf.position(numPos);
int len = (Byte.toUnsignedInt(buf.get(numPos)) >>> 5);
byte[] bag = new byte[len];
buf.get(bag, 0, len);
return offset + inflate(bag);
}
}
private static long inflate(byte[] bag) {
byte[] num = {0, 0, 0 ,0 ,0 ,0, 0, 0};
int n = bag.length - 1;
int i;
for (i = 7; n >= 0; i--) {
num[i] = bag[n--];
}
int negative = num[i+1] & 0x10;
num[i + 1] &= 0x0f;
num[i + 1] |= negative << 63;
return negative > 0 ? -ByteBuffer.wrap(num).getLong() : ByteBuffer.wrap(num).getLong();
}
}
public long get(int ix) {
// 首先寻找 shard, 由于每个桶存储固定数量的数字,因此可以直接映射
int i = ix / SHARD_SIZE;
// 剩下的为需要线性查找的偏移量
ix %= SHARD_SIZE;
byte[] shard = shards[i];
// 找到对应数据的偏移量
long offset = 0;
if (ix > 0) {
int len = (Byte.toUnsignedInt(shard[0]) >>> 5);
offset = inflate(shards[i], 0, len);
}
int numPos = 0;
while (ix > 0) {
int len = (Byte.toUnsignedInt(shard[numPos]) >>> 5);
numPos += len;
ix -= 1;
}
int len = (Byte.toUnsignedInt(shard[numPos]) >>> 5);
return offset + inflate(shards[i], numPos, len);
}
private static long inflate(byte[] shard, int numPos, int len) {
byte[] num = {0, 0, 0 ,0 ,0 ,0, 0, 0};
System.arraycopy(shard, numPos, num, num.length - len, len);
int i = num.length - len;
int negative = num[i] & 0x10;
num[i] &= 0x0f;
num[i] |= negative << 63;
return negative > 0 ? -longFrom8Bytes(num) : longFrom8Bytes(num);
}
4 将堆数据变为栈数据
longData = (longData & ˜(0xff << 2 * 8)) | (0x02 << 2 * 8)
private static long inflate(byte[] shard, int numPos, int len) {
- byte[] num = {0, 0, 0 ,0 ,0 ,0, 0, 0};
+ long data = 0;
- System.arraycopy(shard, numPos, num, num.length - len, len);
+ for (int i = 0; i < len; i++) {
+ data |= (long) Byte.toUnsignedInt(shard[numPos + i]) << (len - i - 1) * 8;
+ }
- int i = num.length - len;
- int negative = num[i] & 0x10;
+ // 查看符号位
+ long negative = data & (0x10L << (len - 1) * 8);
- num[i] &= 0x0f;
- num[i] |= negative << 63;
+ // 将占用位数据清零
+ data &= ~(0xf0L << (len - 1) * 8);
- return negative > 0 ? -longFrom8Bytes(num) : longFrom8Bytes(num);
+ return negative > 0 ? -data : data;
}
5 内联短函数
private void updateOffset() {
byte[] shard = shards[shardIndex];
// 找到对应数据的偏移量
int len = (0xff & shard[0]) >>> 5;
curOffset = inflate(shard, 0, len);
}
我们将之内联后表示如下:
if (numPos >= shard.length) {
shardIndex++;
numPos = 0;
- updateOffset();
// 找到对应数据的偏移量
+ shard = shards[shardIndex];
+ curOffset = inflate(shard, 0, (0xff & shard[0]) >>> 5);
}
三 性能
四 优化总结
Java 基本类型数据结构比对象结构快很多,越面向底层,越快。
堆上分配数据很慢,高频调用还会频繁触发 Yong GC,对执行速度影响相当大,所以能栈绝不用堆。
对象调用慢于直接操作,因为需要进退栈,所以如果是几行简单调用,直接将逻辑复制调出会快很多,例如 Byte.toUnsignedInt() ——当然,这是在极致性能下。
减少中间数据、减少临时变量。
任何细小的性能损失在巨大的调用量在都会成倍扩大,所以对于批量接口要倍加小心。
免费下载电子书
《Java开发者面试百宝书》
《Java开发者面试百宝书》来啦!集结阿里Java大神一手面试经验诚意出品,包括Java面试常见问题标准答案以及阿里技术大神为你总结的面试要点,重点难点两不误,一手面经助你过关斩将,进阶王者!
点击“阅读原文”,立即下载吧~
网友评论已有0条评论, 我也要评论