節(jié)省空間

節(jié)省空間

本章講述了節(jié)省空間的一些重要方法。

減少程序所需數(shù)據(jù)的存儲空間，一般有以下方法：

• 不存儲，重新計算。
• 稀疏數(shù)據(jù)結(jié)構。下面著重講一下這點。
• 數(shù)據(jù)壓縮。可以通過壓縮的方式對對象進行編碼，以減少存儲空間。
• 分配策略。只有在需要的時候才進行分配。
• 垃圾回收。對廢棄的存儲空間進行回收再利用。

以下是節(jié)省代碼空間的幾種通用技術：

• 函數(shù)定義。用函數(shù)替換代碼中的常見模式可以簡化程序，同時減少代碼的空間需求。
• 解釋程序。用解釋程序命令替換長的程序文本。
• 翻譯成機器語言。可以將大型系統(tǒng)中的關鍵部分用匯編語言進行手工編碼。

稀疏數(shù)據(jù)結(jié)構

假設我們有一個200 x 200的矩陣(共40000個元素)，里面只有2000個元素有值， 其它的都為0，示意圖如下：

顯然這是一個稀疏矩陣，直接用一個200 x 200 的二維數(shù)組來存儲這些數(shù)據(jù)會造成大量的空間浪費，共需要200x200x4B=160KB。 所以，我們應該想辦法用另一種形式來存儲這些數(shù)據(jù)。

方法一

使用數(shù)組表示所有的列，同時使用鏈表來表示給定列中的活躍元素。 如下圖所示：