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