## 節省空間
本章講述了節省空間的一些重要方法。
減少程序所需數據的存儲空間，一般有以下方法：
* 不存儲，重新計算。
* 稀疏數據結構。下面著重講一下這點。
* 數據壓縮。可以通過壓縮的方式對對象進行編碼，以減少存儲空間。
* 分配策略。只有在需要的時候才進行分配。
* 垃圾回收。對廢棄的存儲空間進行回收再利用。
以下是節省代碼空間的幾種通用技術：
* 函數定義。用函數替換代碼中的常見模式可以簡化程序，同時減少代碼的空間需求。
* 解釋程序。用解釋程序命令替換長的程序文本。
* 翻譯成機器語言。可以將大型系統中的關鍵部分用匯編語言進行手工編碼。
**稀疏數據結構**
假設我們有一個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的《人月神話》
