節(jié)省空間

節(jié)省空間

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

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

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

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

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

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

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

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

方法一

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