時間換空間,空間換時間  

Posted by 藍斯洛 in

標題這句話,是程式設計裡頭進行最佳化(Optimize)調整時的最終圭臬。不是唯一的方法,卻是全世界通用、軟硬體通吃的最後一招。

所以寫程式的人都沒什麼才華,弄來弄去,只剩一招。

最佳化調整通常有兩個目的,一個是增加程式的運算效能,另一個就是節省程式的資源使用。我們需要減少運算時間的時候,就用查表的方式、建立快取(Cache)的方式,拿空間換時間;需要節省記憶體空間、硬碟空間的時候,就改存放比較簡單的資料、壓縮過的資料,再花時間用演算法計算。

不過,不管怎麼樣,這都是最後一招。意思是,在我們將能夠調整的都調整過了之後,才能使用它。如果有一個比較快速的演算法可以改善程式的運算效能,我們就還不能使用這最後一招。畢竟這一招是需要付出代價的。

舉個很簡單的例子講。我們需要做一個計算從整數A累加到整數B的函式。看到題目,我們很快的寫了一個迴圈來做累加的計算。然後我們將這個函式做最佳化。不需要查表,不需要快取,不需要任何用空間換時間的方法,只需要一個很簡單的梯形面積公式。Sum = (B+A)*(B-A+1)/2。

好,我知道這個例子很蠢,但是概念很重要。

概念是,有比較好的方法可以改進運算效能、節省資源使用量的時候,千千萬萬不要只會想到時間換空間,空間換時間的最後一招。

我們最近進行了一個最佳化的任務--改善遊戲的資料讀取時間。

一開始,我們將資料讀取的工作修改為交給一個專門的執行緒來做,得到一部份的成果,只是還不夠理想。然後我們進一步的將資料分出優先順序,盡可能的將資料載入的時間點分開來,不要讓很多資料載入的工作集中在同一時間。但是這樣的改善成果也還不夠。

最後,我們發現資料載入的效能瓶頸,是出在將這些讀取得的資料轉換為遊戲內資料的過程,於是就施放大絕--拿空間換時間。我們將資料檔案做修改,改成存放已經轉換過的資料,載入的過程中不再需要做轉換,只需要很單純的將資料讀取到記憶體中就可以。效果很好,達到我們的理想需求,但是代價也很大--檔案容量膨脹了十倍以上。

問題來了。

這樣的檔案容量大爆炸,會影響到下載檔案的時間與頻寬,還有,搞不好安裝光碟會從一片DVD變成兩片,成本大增。於是我們又想了個辦法調整。

我們將一部份的資料還原成轉換前的比較小的原始資料,然後做了個小程式把轉換資料的工作獨立出來。使用者下載與安裝的是容量小的原始資料,經過轉換程式轉換後,再存放到資料硬碟裡面。這樣,我們又拿時間來換空間,只不過這個時間並不是遊戲進行時的運算時間,而是檔案安裝與更新的時間。遊戲還是保持順暢,安裝與更新嘛…多花一點時間無妨的啦!

This entry was posted on 2008年9月24日 星期三 at 星期三, 9月 24, 2008 and is filed under . You can follow any responses to this entry through the comments feed .

2 意見

先從時間換空間,再從空間換時間,這個方法真不錯!

此外,我所好奇的是,除非是在多核心電腦上執行程式,否則使用另一個執行緒處理檔案讀取,應該不會加快資料處理的工作速度?

不知道是不是利用 background loading 的作法,將檔案資料依需求分批讀取進來?

2008年9月25日 下午5:04

理論上是。多執行緒需要多核心的電腦,才會發揮改善的效果。不過,近來的電腦幾乎都是雙核心以上了,所以這方法有它的成效在。

過去我們可能都會在Game Loop裡偷偷抓一點時間做Loading,也就是Time Slice的方式做一個假的background loading,但是現在可以考慮使用多執行緒來做了。

說真的,實驗證明,拿硬碟空間換CPU時間的效果還是最大....XD

2008年9月26日 上午9:31

張貼留言