#2 BIG O - 有關程式執行的快慢 - Optimization

從上一次寫的文章中可以看到如何辦別一個程式執行的好壞,那些都是相當基本而簡單的例子,但在工作中時,我們需要利用這技巧嗎? 答案當然是 YES,但在一般業界中 BIG O 的評估,有時並不是那麼單純,因為我們都習慣用了其他公司寫好的 framework 來進行我們的程式撰寫,比如用 Java platform 或 .Net platform ,所以一個 API 內部會如何執行,我們看不到原始碼就不太能準確知道,所以這一部份只能靠著多使用這些 framework 所得的經驗來知道那一個 API 比較好.

比如,前一篇文章曾講到 string1.Contains(string2),要寫 Contains() 可以很簡單,你可以把 string 看成是一個 array,在這個 array 裡的元素就是字串裡的每個字母,而今天你要在這字串裡面尋找是否包含另一個子字串時,最簡單的方法就是寫 2 個 loops,外面的 loop 是用來記錄目前比對的位置,裡面的 loop 是用來比較 string1 從記錄點開始有沒有跟 string2 一樣的字元.以 Contains() 的角度來看,我們在評估 BIG O 時只看輸入參數的影響,所以我們不會去管 string1 的長短,在 string1 一樣的情況下,去看 string2 從很短到很長時對執行步驟的變化.這個是最簡單的寫法,難道你認為你用的 framework 就一定這樣寫嗎? 那可不一定. 這些產品工程師們總是有可能想到更好的寫法,所以有時候若有機會去看看這些 framework 的原始碼時,相信會對於你寫程式的功力將大有幫助.

BIG O 談的是輸入參數變化量對程式本身影響的一個趨勢,在業界中,當然會利用這個技巧來討論,除此之外,在業界中還更需要做一些 optimization. 什麼是 optimization 呢? 簡單的說,就是去掉一些沒有用的執行. 讓我們來看上一篇 FindSum4() 的例子.

bool FindSum4(int[] ary, int target) {
    for (int i = 0; i < ary.length ; i++) {
        for ( int j = 0 ; j < ary.length ; j++) {
            if ( i != j ) 
            {
                int sum = ary[i] + ary[j];
                if ( sum == target ) {
                    return true;
                }
            }
        }
    }
    return false;
}

你看看上面寫的例子還有沒有可以改進的地方呢? 可以改進的地方就是有些運算其實是重覆了.其實重覆的地方很多,比如 i = 0 , j = 1 和 j = 0 , i = 1 的運算是一樣的,因為都是抓 ary 的第一個元素和第二個元素來做加法運算. 所以你可以看到 loop 的次數其實可以不用跑那麼多次的,我們只要改一下

bool FindSum4(int[] ary, int target) {
    for (int i = 0; i < ary.length ; i++) {
        for ( int j = i + 1 ; j < ary.length ; j++) {
            if ( i != j ) 
            {
                int sum = ary[i] + ary[j];
                if ( sum == target ) {
                    return true;
                }
            }
        }
    }
    return false;
}

把第二個 loop 的 j = 0 改成 j = i + 1,這樣就大大減少了 loop 內容執行的次數了,而且 if ( i != j ) 還是多餘的.雖然這不一定是最完美的 optimization,但相信你抓住我所要講的重點,那就是去除掉一些重覆的執行動作,雖然以上的兩個程式的 BIG O 都是一樣的,但在工作時,我們還是會要求工程師要做優良的 optimization. 畢竟你輸入的 ary 不可能是無窮大,電腦記憶體是有限的,所以做優良的 optimization 的確是可以幫助你讓程式別重覆做同樣的動作.

話說回來,那像 FindSum4() 是不是還有更好的寫法呢? 答案是有的,以後在適當的內容時會再說明.

Share: