节省空间
最后更新于：2022-04-01 21:46:23
## 节省空间
本章讲述了节省空间的一些重要方法。
减少程序所需数据的存储空间，一般有以下方法：
* 不存储，重新计算。
* 稀疏数据结构。下面着重讲一下这点。
* 数据压缩。可以通过压缩的方式对对象进行编码，以减少存储空间。
* 分配策略。只有在需要的时候才进行分配。
* 垃圾回收。对废弃的存储空间进行回收再利用。
以下是节省代码空间的几种通用技术：
* 函数定义。用函数替换代码中的常见模式可以简化程序，同时减少代码的空间需求。
* 解释程序。用解释程序命令替换长的程序文本。
* 翻译成机器语言。可以将大型系统中的关键部分用汇编语言进行手工编码。
**稀疏数据结构**
假设我们有一个200 x 200的矩阵(共40000个元素)，里面只有2000个元素有值， 其它的都为0，示意图如下：
显然这是一个稀疏矩阵，直接用一个200 x 200 的二维数组来存储这些数据会造成大量的空间浪费，共需要200x200x4B=160KB。 所以，我们应该想办法用另一种形式来存储这些数据。
**方法一**
使用数组表示所有的列，同时使用链表来表示给定列中的活跃元素。 如下图所示：
该结构中，有200个指针(colhead)和2000条记录(每条记录是两个整数和一个指针)， 占用空间是200x4B + 2000x12B = 24800B = 24.8KB， 比直接用二维数组存储(160KB)要小很多。
**方法二**
我们可以开三个数组来保存这些数，如下图所示：
firstincol是一个长度为201的数组，对于第i列，在数组row中， 下标为firstincol[i]到firstincol[i+1]-1对应的行元素非0， 其值存储在相应的pointnum数组中。
比如对于上图，在第0列中，元素值非0的行有3行，分别是row[0],row[1],row[2], 元素值是pointnum[0],pointnum[1],pointnum[2]；在第1列中，元素值非0的行有2行， 分别是row[3],row[4]，元素值是pointnum[3],pointnum[4]。依次类推。
该结构所需要的存储空间为2x2000x4B + 201x4B = 16804B = 16.8KB。 由于row数组中的元素全部都小于200，所以每个元素可以用一个unsigned char来保存， firstincol数组中元素最大也就2000，所以可以用一个short(或unsigned short)来保存， pointnum中的元素是一个4B的int， 最终所需空间变为：2000x4B + 2000x1B + 201x2B = 10402B = 10.4KB。
深入阅读：Fred Brooks的《人月神话》
';