以時間換取空間，以空間換取時間

設計程式時，想要程式碼有彈性，通常就得犧牲效率；相反的，若是希望程式效率表現好，常常就得在彈性上面打折扣。當然，方法的好壞也會影響，但是當發揮到極致時，這種「不可兼得」的現象就會愈來愈明顯。因此，我們不是拿彈性去換取效率，就是用效率去換取彈性。

除了效率和彈性這二者的取捨之外，另外一個最常遇到的情況，莫過於「以時間換取空間，以空間換取時間」了。

若是從演算法的角度來說，一般我們設計出一個演算法，會評估時間複雜度，以及空間複雜度。時間複雜度指的是該演算法隨著問題規模的成長，所需要計算時間的成長方式；而空間複雜度則是隨著問題規模成長，所需儲存資料空間的成長方式。

有些時候，當我們希望所設計的演算法佔用的記憶體空間小時，可以透過增加演算法所耗費的計算時間來達成，相反的，若是我們希望所設計的演算法降低所需的計算時間，那麼也可以藉由使用更多的記憶體空間，來達到這個目的。這就是所謂「以時間換取空間，以空間換取時間」。

以時間換取空間

這並不是說，只有透過增加所佔用的空間，才有辦法降低演算法的運行時間，當然演算法精益求精，還是有機會在不增加佔用空間的情況下，來減少所需的時間。不過，一旦追求時間到了一個境界之後，想要再往上推進，往往愈來愈難，此時，拿空間來換取時間，可能就會是另一個比較有效的方向。

在我們解決軟體問題的時候，也會遇到類似的情況。例如程式運行的效能不夠快時，可以試著找出程式碼本身是否存在的效能問題，以致於造成了瓶頸，並且試圖予以最佳化，藉以提升執行效率。

不過，若是程式碼本身並沒有太顯著的撰寫問題，但程式的效能還是無法達到預期時，除了從硬體層面著手之外，常常也會考慮使用「以空間換取時間」的策略，而最常使用的的技巧就是查表法。

查表法，顧名思義，就是為程式中即將使用的某些資料先建在一個表格中，接著就只要查詢這個表格便可以得到答案。這些資料之所以需要先建到表格中，是因為它其實是需要經過一些計算才能得到的。倘若這些資料都必須在執行時期每次使用時都重新計算，那麼勢必耗用掉部份的計算時間。但如果資料已經預先計算好、直接建到表格中，在執行期需要使用時，便只需要花費查表的時間便可以得到，相較之下，便迅速許多。

記得我剛開始學著寫程式的前幾年，那是一個CPU計算能力還很弱的年代，事實上，連計算個三角函數像sin或cos，所需的計算時間，都有可能被認為是相當耗時的運算。那時，就時常可以看到許多程式，在程式一啟動就預先計算出一組所需要用到之三角函數值的表，接著在程式中每次需要使用到該函數之值時，便可以直接查表取得，毋需每次皆重新計算。節省可觀的計算時間，大大提升計算效能。

這種查表法就是典型的用空間換取時間的策略，因為它是利用記憶體空間儲存一些預先計算好的結果，使得一些耗時的計算結果只需要被計算一次，之後儲存在記憶體中只需要經由查表便可得到。當表格中的計算愈耗時，查表法就顯得愈有利。

針對三角函數的這個例子，三角函數的值都是固定的，給定一個固定的x，總是可以得到相同的y。所以查表法除了需要佔用額外的表格空間之外，對整個結果完全沒有影響。

不過，除了這類的例子之外，還有一種會搭配的，是犧牲即時性的策略。舉例來說，如果你的系統需要呈現一個數量超過百萬筆、經排序的清單予使用者，而清單中用來排序的值又是動態、隨時可能變化的，如果你想要每次使用者要求此清單時，都即時的套用排序演算法來進行排序，那麼所衍生的計算量將是相當可觀的。若是可能同時使用的使用者數量多時，這個效能的問題勢必更大。

所以，有些設計者往往會選擇放棄即時性，也就是說，若是對應用本身來說，即時性並沒有那麼重要，例如有些類型資料的排行榜，其實，許多類型的排行榜其即時性並沒有那麼重要，有些應用可以接受一小時重新計算一次，甚至有些可以接受一天重新計算一次。這麼一來，就可以定期將排行榜內容計算好，並且記錄到額外的儲存空間，例如關聯式資料庫中。之後想要使用排行榜的內容，便只需要至關聯式資料庫中進行查詢，便可以輕易取得。這樣的技巧主要也是利用空間換取時間，但同時也搭配著犧牲計算的即時性。

曾經看過有個系統，每次都要即時針對關聯式資料庫中兩個很大的表格，做join的動作，接著再到主記憶體中做其他的過濾及後處理計算。可以想見，這是相當耗時而且影響資料庫效能的動作，當然就構成了一個效能瓶頸。

後來這個問題怎麼解決呢？在允許犧牲些許即時性的前提下，一樣只是定期才重新到資料庫撈取資料，並做計算及後處理，而這些計算結果則會被保留在主記憶體中，直到下次重新計算的週期來到之前，程式一律使用主記憶體這個暫存表格中的值。這麼一來，便節省了大量的計算時間及耗用的資源，尤其在線上使用者眾多時更為明顯。

這種方式在概念上有點像是快取，但是快取主要是搭建在不同存取速度層次的儲存媒介之上，而這種保留中介計算結果的手法則還包括了計算的結果。

從這個例子你同時也可以了解，很多時候，對某些應用來說，即時性並不是那麼重要，我們沒有必要每次都很即時的做計算。只要能夠放寬對即時性的要求，在效能上往往大有幫助。

用空間換取時間

大多數時候，我們都在「拿空間換時間」，這是因為大多數的情況下，我們遇到的是效能問題，而儲存空間通常不太構成問題。即使如此，空間資源還是有限，尤其是像RAM樣的主記憶體空間。一旦遇上了空間問題，可能就要思考是否可以倒著來做，也就是為了不佔用空間，可否以運用計算來重新取得資料而不需要持續佔用或是減少佔用的量。

有個用時間換取空間的最佳例子就是──壓縮。如果你程式的空間佔用量是個問題，那麼在不使用資料時，利用諸如ZIP之類的演算予以壓縮，等到即將使用時再予以解壓縮來使用。在硬碟空間還相對比較昂貴的年代，就有人做出即時針對檔案系統做壓縮及壓縮動作的機制。這使得檔案在儲存到硬碟時，會自動即時進行壓縮，而在取得資料時，也會即時解壓縮。這就是典型的用時間換取空間。

另外，除了儲存空間，對於需要做傳輸的資料，有時也會有空間的問題。例如，在有限的頻寬或是希望降低傳輸的資料量時，就會想要透過額外的計算，像是壓縮，來降低傳輸時的資料量。此外，像視訊或音訊的編解碼，基本上都可以算是用時間換取空間，因為它們不直接儲存或傳輸原始資料，而是透過付出計算時間來大幅減少資料量。

有些時候，你不追求時間的最佳化，也不追求空間的最佳化，而是試著在這二者之間取得平衡。例如，你要在計算力有限的內嵌式系統上，將即時擷取到的視訊資料透過無線網路傳輸出來。由於計算力不夠強，所以不能使用複雜的視訊編碼技術，但也不能夠完全都不編碼，因為無線網路的頻寬也有限，所以必須找到一個微妙的平衡點，在受限的計算力、受限的頻寬中，找到滿足限制條件的結果。

時間和空間這兩個特質具備了很不錯的互換性，有許多常見的技巧都是透過交換這二者來得到。日後遇到空間或是時間上的問題，不妨想想是否存在交換的可能，或許問題就能迎刃而解。