【性能优化】2.2 [外存数据集] 集文件及倍增分段

2.3 数据类型

使用二进制文件后，我们可以采用更优化的编码方案。

一个整数在计算机可能占 4 字节或 8 字节，原则上存储到文件中也是这个大小。但是，其实有相当一部分整数并不大，比如一个人的年龄不会超过 200，如果表示成 4 字节时，其中有 3 字节都是 0，如果都存储成 4 字节，就显得有些浪费。

不要小看这一点，因为数据量经常很大，如果我们换一种编码方式，把小整数换一种编码方式存储，能节省 2 个字节，如果有 10 亿行数据，就能节省 2G 的空间，可以减少大量硬盘访问时间。

类似地还有日期时间，一个完整的 datetime 类型会占用 8 字节，而经常我们只关心日期部分，甚至只需要表示近几十年的日期，如果能够更换编码方式，可能只要一半空间就能存储下来了。

不过，也不能把编码规则搞得太复杂，否则会导致解码占用较多的 CPU 时间。具体的编码有多种多样，在了解基本原则之后可以自行设计。

SPL 在存储集文件时对小整数、近期日期、短字符串都采用了优化的编码。读者可以自行尝试同样数量的大整数和小整数存储出来占用的空间有多大差异。

数据在外存中占用的存储空间和数据类型相关性很强，越简单的数据类型占用空间就更小，在解码时的运算也最简单。比如整数就是一个简单的值，占用的空间相对确定，读出解码动作很简单；而字符串则还有个长度信息，需要更多的存储；日期时间本身没有其它信息，但会涉及相对复杂的解码动作。

如果我们能够在不丢失数据信息的前提下改变数据类型，就有可能节省很多存储空间并减少解析动作，获得很好的性能提升。

所有的数据类型中，整数最简单，存储与解析性能最好。如果有可能，尽量把其它数据类型转换成整数。

日期可以转换距离某一天起的天数，这样不影响比较。5 万天可以表示超过 100 年的时间段，在大多数场景都够用。希望更方便地获得年月日分量时（有些运算要针对年、月分组），简单来讲可以转换成 yyyymmdd 的 8 位十进制整数；SPL 还提供了一种更省空间的方法，把年月转换成距离 1970 年起的月数，而日用 5 个二进制位表示（一个月最多 31 天，5 位二进制数可以表示 0-31 之间的数），即相当于 ((yyyy-1970)*12+(mm-1))*32+dd，这样就可以用小整数表示从 1970 年到 2140 年间的日期，也基本够用。

A1 是待转换的日期，B1 是一个基准日期。A2、A4、A6 分别用三种办法将 A1 转换成整数，第 3、5、7 行则是这三种编码后再反算出年月日分量。A2 方法得到的整数最小，但反算年月日的计算量较大； A4 方法和 A6 方法的反算计算量都较小，A6 方法转换出来的整数更小，而且 SPL 提供了更方便的基础函数用于转换。第 8、9 行解释了 A6 方法的实际执行逻辑。

字符串会有两种。就是文字本身一般没有太多可优化的余地，比如姓名、地址等；还有一种字符串常常是一种编码方式，其可取范围很小，比如性别、学历、国家或地区的缩写等，这种情况，只要将其转换成编码表的序号就可以了：

B2 把 A1 转换成整数，C2 则再反算回来。转换时需要做查找，相对会耗时（可以用二分法），反算则相当于序号定位，性能很好。这样在存储时多耗一些 CPU 时间做转换，但存储及编码更有优势，而且在运算时的效率要高得多。

前端说过，在适合的编码方式下，小整数会比大整数占用更小的存储空间。另外，对于 SPL 来讲，小整数还有更大的意义。因为 SPL 是 Java 开发的，而 Java 产生对象很慢，SPL 将所有 16 位整数（0-65535）都事先产生了。如果发现读出来的整数在这个范围内，则不会新产生对象了，能减少很多运算量。

刚才说的第三种日期转换方式，可以把 50 多年内的日期转换到 16 位整数之内，而且反算计算量也不大。而第二种虽然反算计算量也小，但转换出来的整数范围要大得多，不再是小整数了，存储和运算性能都会差一些。

这些数据类型的转换，事实上对于内存运算也有意义。

整数运算也比日期、字符串的运算的复杂度更低，在比较相等和大小时都要更快，包括哈希函数的计算也是对整数要比对字符串快得多。

我们在上一章讲查找运算中并没有关注数据类型，从复杂度分析上确实没有区别，但工程上的差别却很大。在查找时，如果能先把被查找键转换成整数存储，每次查找时多做一次对查找值的转换成本，要远小于查找过程中因数据类型简化而带来的比较和哈希计算的收益，这也是性能优化中的常用工程手段。

数据类型的优化，还表现在多字段情况。

我们在上一章讨论查找算法时，都是针对一个字段的被查找键进行的，其实这些算法也适用于多字段的查找。同样的，理论上多字段和单字段在算法复杂度上没有区别，但工程上却有较大差异。即使是两个字段，也需要用一个集合来表示，就会有长度信息，其占用的空间和导致的运算量并不是单字段的两倍（假定字段的数据类型都一样），而会是更多。

所以，有可能的情况下，可以考虑把多个字段拼成一个字段。不过，这个手段是否有效，需要具体分析和实测。多字段拼成一个字段，可以避免集合运算，但又会使整数变大、甚至要把整数转换成字符串（才能和另一个字符串拼接），这些导致的性能损失，有时并不能抵消避免集合运算带来的好处。

简单来讲，如果两个本来无法再转换成整数的字符串拼起来，或者两个小整数拼起来仍然不大的情况（比如两个 2 位数拼起来也就是 4 位数），合并字段都会带来好处。更复杂的情况则不一定了。

【性能优化】2.4 [外存数据集] 组表与列存
【性能优化】 前言及目录