17
Jun
2021

一种数组压缩算法

标签: 算法

我们在开发中后台应用或者中间件的时候,会存储一些数据在内存中以加快访问速度。随着数据量的增加,除了可以放置于堆外,还可以通过实时压缩来缓解。今天就给大家介绍一种压缩整形数组的方式

数组指 long[] 或者 int[] 类型,主要用来存索引数据。当数据量变大时,首先想到的就是缩减每个数字占用的空间,因为我们都知道一个 long 类型是占 8 个字节,而 int 也是占用 4 个字节。就以正数而言,int 3 个字节以上表示 2^24 = 16M 即 1600 百万以上的数字,一般我们是用不到的,大多数情况下高位都是闲置着的,所以可以将高位去掉,只存储用到的那几个字节(见图1)。当然为了可以还原,我们需要记录这个数字到底使用了几位。这里有两种方式:一是借用几位来表示,就拿 long 来说,我们只需要借用 3 位就可以表示用到的字节数了,另一方面,2^60 以后已经是非常大的数了,几乎用不到,所以我们借用也不会产生额外的效果;另一种就是利用字节最高位表示还有剩余数据(见图2)。这样一来,我们就把 long 或者 int 数组压缩成了 byte 数组,里面所有用到的字节都是有表示意义的。

1.jpg
图1

2.jpg
图2

这样一样我们就可以顺利地将数字进行压缩与解压缩了,在传输场景下可以很好的解决空间问题,这都是常见的思路。但是如果我们需要压缩后的数组仍然具备下标访问的能力怎么办?之前每个数字都是固定长度,我们可以通过 [单个数字占用的字节数]*[下标] 很快地找到对应的地址,但是压缩过后每个数字占用的空间不是一样的,这种方式就失效了。如果我们要取下标为 200 的数据,那我们就得线性查找 200 次?那么时间复杂度就由 O(1) 下降为了 O(n)。有没有更好的办法呢?当然是有的。我们可以建立索引(图3),即:

  1. 将数字分为若干个桶,每个桶的大小可心调节
  2. 我们使用另一个数组,大小为桶的数量,存储每个桶所第一个数据所在的下标
  3. 在查找时我首先使用二分查找到对应的桶,再使用线性查找到对应的数据

3.jpg
图3

由于在桶内是线性查找,因此不会太大,一般是 1KB 或者 4 KB。这样一来,我们查找速度就可以大大提升,接近 O(logn)。使用这套方式,经测试,在 4 亿随机数据的情况占用的空间可以缩减 30% 左右,但这并不是终点。利用桶的性质,我们可以只在桶内第一个元素存原数字,后面的都存一个偏移量,因为当数据不会明显离散(即一会儿是十几,一会是几十亿那种),可以很好地缩减数据大小,比如两个数都占用了 3 个字节,存偏移量后,第二个数字就可以使用 1~2 个字节来表示了。当然如果你对数组本身的顺序没有要求的话,还可以先对数组进行排序,这种偏移量的效果就可以暴表了。最理想的情况下,可以压缩至原来的 30%。

D3035B08-6314-4ee1-9A2D-D9E16C2E0978.png
测试压缩效果(未排序)

UPDATE:2021-06-20

这里还有优化空间,之前采用二分查找是因数我们采用定长的桶,每个桶存储的数字数量不定,但如果我们采用变长桶,让每个桶存储 N 个数,那么,便可以直接通过 “整除+求余” 的方式快速打到数所在的桶,查询效率进一步提升。

源码:seflerZ/zipped-num-array: Compressed number array and acts exactly like the original array like long[] and int[] (github.com)

12
May
2021

2021清海湖骑行

标签: 骑行 思考
想来也是不容易,距离上次台湾骑行已经过了快 5 年了(台湾骑行是 2016 年),人过 30 岁以后,真的有点变得身不由己,这次也尝试约了很多以前的骑友,但大多已经成家立业,均表示心有余而力不足了。自从上次创业失败后,这几年也过得不怎么好,人生开始变得被动起来,确实人过了 30 岁后就很难找到自然增涨的方式,好在一直在尝试,不放弃,就是不想变成生活的奴隶,有句话说得好:梦想还是有要有。那么身体与灵魂总需要有一个在路上吧,所以想来想去这次骑行还是得安排上,就算只是我一个人,风雨无阻,我就是喜欢在路上的感觉。

阅读全文>>

21
Feb
2021

几行命令,让你的 Windows 拥有全能解压软件

首先你需要安装 WSL,最好是 Ubuntu,然后在 WSL 建立以下脚本:

#! /bin/bash

FILE=$1
FILE=${FILE##*\\}
EXT=${FILE##*.}
NAME=${FILE%%.*}

#echo $FILE >> ./filename
#echo $EXT >> ./filename
#echo $NAME >> ./filename

#echo $FILE >> ./filename

if [ $EXT = "zip" ]; then
        unzip "$FILE"
elif [ $EXT = "tgz" ]; then
        tar -xzvf "$FILE"
elif [ $EXT = "gz" ]; then
        gzip -d "$FILE"
elif [ $EXT = "rar" ]; then
        unrar x -ad "$FILE"
else
        echo "not supported"
fi

sleep 2


然后在 Ubuntu 中安装 unrar, zip, tar 等工具用于解压。之后就是在 Windows 注册表,路径为 \HKEY_CLASSES_ROOT\*\shell,在shell上点击右键->新建->项,命名为 解压至当前目录(随便命名),在刚才那个目录上点击右键->新建->项,命名为command(必须这个名),再新建一个字符串,输入值为:wsl exec sh ~/unzip.sh "%1",其中 ~/unzip.sh 是第一个脚本在 wsl 中的路径,我这里放置在了 home 目录。如果还不明白如何新建右键菜单可以参考这个文章 



08
Nov
2020

《孙子兵法》有感于斯文

标签: 思考

《孙子兵法》早已名扬远外,而对于这些的著作,我竟然而立之年才读到,实属遗憾。读罢感触颇深,受益良多,故写此一文,以作交流学习之用,若干后后再回看,岂不美哉!

首先我们要明白它是 2500 多年前的春秋时期著作,整整 25 个世纪!文字真是人类文名的基石,读着这些文字,会有跨越时空交流的感觉,非常神奇的感觉。正如《兰亭集序》篇尾写到的那样 “后之视今犹如今之视昔”,每个人都是历史中的一粟,无人永生,但是通过文字,思想得到了流传,精神得到了永生,人类才得以不断进步。

《孙子兵法》整篇分为 13 篇,从宏观的战争因素、利弊权衡,到客观的地形,再到人性相关的用兵用将,篇尾再至火攻、离间等计某的阐述,精彩绝伦,金句不断。如 《作战篇》中孙子谈到 “夫兵久而国利者,未之有也”,再至人人皆知的 “兵者,诡道也”,再如 《虚实篇》中的 “故善战者,致人而不致于人”。把书的思想放到现在,也可以成为一篇军事著作,更何况作者生活在公元前,拥有如此先进的思想令人震撼。

阅读全文>>

12
Sep
2019

浅谈神经网络与机器学习

标签: 机器学习

发展历史

说到机器学习,大家听闻最多的就要数 “深度学习” 这么一个概念了,近几年比较火。深度学习其实就是机器学习的一新方法论合集,不过机器学习的研究上世纪就开始了,特别是深度学习的基础 “人工神经元网络(以下简称神经网络)” 更是于 1943 年就由心理学家 Warren McCulloch 和数学家 Walter Pitts 提出了。在经历了快速发展后陷入瓶颈期,最重要的一点便是无法有效地训练神经网络——一方便是算法,另一方面是计算能力——直到上世纪未才由反向传播(BP)方式得以改进。

神经网络就是模拟生物大脑的信息传递结构,以计算机的视角进行了构建,参照生物神经元的特性,也分为神经元、轴突与树突,具体由计算机图数据结构来表示。例如一个简单的神经元网络如下:

前馈人工神经元网络

阅读全文>>

15
May
2019

我的书出版了!Service Mesh: Istio 入门必备

标签: 思考 软件设计 架构

很长时间没有写博客了,大家可能以为它已经废弃了。其实,从去年到现在我都是在忙着写一本关于 Istio 的书籍,之所以写这本书主要还是因为当时市面上对这方面的文章太少了,书籍则是零。因此我将自己的理解与实践经验分享给大家,希望对大家有帮助。


我个人是非常看好服务网格的,我自己本身专注于软负载,我认为服务网格是在容器时代的软负载最佳的存在形态。就像 PaaS 一样,服务网格也将自己作为一个基础通用服务层下层到了基础技术栈体系,这样不仅有利于通用性,还对业务的无侵入性有很好的支持。在容器时代,一切都是浮动的、弹性的,可变的,负载也不例外,从早些时候的硬件负载,到微服务时代的透明负载,再到服务网格,这一个世代的划分。我觉得每个对分布式有兴趣或者从事其中的工程师都应该或多或少了解下。


有兴趣吗?买我一本书吧,听我慢慢为你道来~


当当:http://product.dangdang.com/27857036.html 


19
Oct
2018

Coqlicot 09 reversion 03

标签: 钢琴

阅读全文>>

17
Jun
2018

(Long Ver.) Love is a Flower, You are the Seed

标签: 钢琴
27
Apr
2018

再谈意识形态

标签: 意识
最近在跑装修,想起个有趣的问题:为什么上世纪90年代的建筑一看便知?凌型的窗台装饰,阳台外加装的雨篷,不要以为这是以前的现象,现也如此,如现在流行的男士飞机头发型。任何一个时代有自己的物质特点,物质决定意识,而人的本质则是一切社会关系的总合,这种关系将意识聚集起来,形成主流(也就是我们说所的“流行”),随着物质的迭代,意识也相应跟着改变,所以,只要环境没有改变,人的意识便难以突破,没人可以置身于外。
08
Dec
2017

未觉池塘春草梦 阶前梧叶已秋声

1 2 3 4 5 6 7 ... »