回爐重造12時辰-代碼效率優化方法論(二)

回爐重造12時辰-代碼效率優化方法論(二)

—-將昂貴的時間複雜度轉化為廉價的空間複雜度

 

 

時間昂貴、空間廉價

  一段代碼會消耗計算時間、資源空間,從而產生時間複雜度和空間複雜度,那麼你是否嘗試過將時間複雜度和空間複雜進行下對比呢?其實對比過後,你就會發現一個重要的現象。

  假設一段代碼經過優化後,雖然降低了時間複雜度,但依然需要消耗非常高的空間複雜度。 例如,對於固定數據量的輸入,這段代碼需要消耗幾十 G 的內存空間,很顯然普通計算機根本無法完成這樣的計算。如果一定要解決的話,一個最簡單粗暴的辦法就是,購買大量的高性能計算機,來彌補空間性能的不足。

  反過來,假設一段代碼經過優化後,依然需要消耗非常高的時間複雜度。 例如,對於固定數據量的輸入,這段代碼需要消耗 1 年的時間去完成計算。如果在跑程序的 1 年時間內,出現了斷電、斷網或者程序拋出異常等預期範圍之外的問題,那很可能造成 1 年時間浪費的慘重後果。很顯然,用 1 年的時間去跑一段代碼,對開發者和運維者而言都是極不友好的。

  

 

  這告訴我們一個什麼樣的現實問題呢?代碼效率的瓶頸可能發生在時間或者空間兩個方面。如果是缺少計算空間,花錢買服務器就可以了。這是個花錢就能解決的問題。相反,如果是缺少計算時間,只能投入寶貴的人生去跑程序。即使你有再多的錢、再多的服務器,也是毫無用處。相比於空間複雜度,時間複雜度的降低就顯得更加重要了。因此,你會發現這樣的結論:空間是廉價的,而時間是昂貴的。

 

數據結構連接時空

  假定在不限制時間、也不限制空間的情況下,你可以完成某個任務的代碼的開發。這就是通常我們所說的暴力解法,更是程序優化的起點。

  例如,如果要在 100 以內的正整數中,找到同時滿足以下兩個條件的最小數字:

  (1)能被 3 整除;

  (2)除 5 余 2。

  最暴力的解法就是,從 1 開始到 100,每個數字都做一次判斷。如果這個數字滿足了上述兩個條件,則返回結果。這是一種不計較任何時間複雜度或空間複雜度的、最直觀的暴力解法。

  當你有了最暴力的解法後,就需要用上一講的方法評估當前暴力解法的複雜度了。如果複雜度比較低或者可以接受,那自然萬事大吉。可如果暴力解法複雜度比較高的話,那就要考慮採用程序優化的方法去降低複雜度了。

  為了降低複雜度,一個直觀的思路是:梳理程序,看其流程中是否有無效的計算或者無效的存儲。

  我們需要從時間複雜度和空間複雜度兩個維度來考慮。常用的降低時間複雜度的方法有遞歸、二分法、排序算法、動態規劃。而降低空間複雜度的方法,就要圍繞數據結構做文章了。

  降低空間複雜度的核心思路就是,能用低複雜度的數據結構能解決問題,就千萬不要用高複雜度的數據結構

  經過了前面剔除無效計算和存儲的處理之後,如果程序在時間和空間等方面的性能依然還有瓶頸,又該怎麼辦呢?前面我們提到過,空間是廉價的,最不濟也是可以通過購買更高性能的計算機進行解決的。然而時間是昂貴的,如果無法降低時間複雜度,那系統的效率就永遠無法得到提高。

  這時候,開發者們想到這樣的一個解決思路。如果可以通過某種方式,把時間複雜度轉移到空間複雜度的話,就可以把無價的東西變成有價了。在程序開發中,這種時空轉移的思想也是可以使用的,而連接時間和空間的橋樑就是數據結構。對於一個開發任務,如果你能找到一種高效的數據組織方式,採用合理的數據結構的話,那就可以實現時間複雜度的再次降低。同樣的,這通常會增加數據的存儲量,也就是增加了空間複雜度。

  以上就是程序優化的最核心的思路,也是這個專欄的整體框架。我們簡單梳理如下:

  第一步,暴力解法。在沒有任何時間、空間約束下,完成代碼任務的開發。

  第二步,無效操作處理。將代碼中的無效計算、無效存儲剔除,降低時間或空間複雜度。

  第三步,時空轉換。設計合理數據結構,完成時間複雜度向空間複雜度的轉移

 

 

降低複雜度的案例

  有了如上的方法論,我們給出一個例子,幫助你加深理解。

  第 1 個例子,假設有任意多張面額為 2 元、3 元、7 元的貨幣,現要用它們湊出 100 元,求總共有多少種可能性。假設工程師小明寫了下面的代碼:

public void testOne_1() {

    int count = 0;

    for (int i = 0; i <= (100 / 7); i++) {

        for (int j = 0; j <= (100 / 3); j++) {

            for (int k = 0; k <= (100 / 2); k++) {

                if (i * 7 + j * 3 + k * 2 == 100) {

                    count += 1;

                }

            }

        }

    }

    System.out.println(count);

}

  在這段代碼中,使用了 3 層的 for 循環。從結構上來看,是很顯然的 O( n³ ) 的時間複雜度。然而,仔細觀察就會發現,代碼中最內層的 for 循環是多餘的。因為,當你確定了要用 i 張 7 元和 j 張 3 元時,只需要判斷用有限個 2 元能否湊出 100 – 7* i – 3* j 元就可以了。因此,代碼改寫如下:

public void testOne_2() {

    int count = 0;

    for (int i = 0; i <= (100 / 7); i++) {

        for (int j = 0; j <= (100 / 3); j++) {

            if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) {

                count += 1;

            }

        }

    }

    System.out.println(count);

}

  經過改造後,代碼的結構由 3 層 for 循環,變成了 2 層 for 循環。很顯然,時間複雜度就變成了O(n²) 。這樣的代碼改造,就是利用了方法論中的步驟二,將代碼中的無效計算、無效存儲剔除,降低時間或空間複雜度。

 

 

 

  再看第二個例子。查找出一個數組中,出現次數最多的那個元素的數值。例如,輸入數組 a = [1,2,3,4,5,5,6 ] 中,查找出現次數最多的數值。從數組中可以看出,只有 5 出現了 2 次,其餘都是 1 次。顯然 5 出現的次數最多,則輸出 5。

  工程師小明的解決方法是,採用兩層的 for 循環完成計算。第一層循環,對數組每個元素遍歷。第二層循環,則是對第一層遍歷的數字,去遍歷計算其出現的次數。這樣,全局再同時緩存一個出現次數最多的元素及其次數就可以了。具體代碼如下:

public void testTwo_1() {

    int a[] = { 1, 2, 3, 4, 5, 5, 6 };

    int val_max = -1;

    int time_max = 0;

    int time_tmp = 0;

    for (int i = 0; i < a.length; i++) {

        time_tmp = 0;

        for (int j = 0; j < a.length; j++) {

            if (a[i] == a[j]) {

            time_tmp += 1;

        }

            if (time_tmp > time_max) {

                time_max = time_tmp;

                val_max = a[i];

            }

        }

    }

    System.out.println(val_max);

}

  在這段代碼中,小明採用了兩層的 for 循環,很顯然時間複雜度就是 O(n²)。而且代碼中,幾乎沒有冗餘的無效計算。如果還需要再去優化,就要考慮採用一些數據結構方面的手段,來把時間複雜度轉移到空間複雜度了。

  我們先想像一下,這個問題能否通過一次 for 循環就找到答案呢?一個直觀的想法是,一次循環的過程中,我們同步記錄下每個元素出現的次數。最後,再通過查找次數最大的元素,就得到了結果。

  具體而言,定義一個 k-v 結構的字典,用來存放元素-出現次數的 k-v 關係。那麼首先通過一次循環,將數組轉變為元素-出現次數的一個字典。接下來,再去遍歷一遍這個字典,找到出現次數最多的那個元素,就能找到最後的結果了。

具體代碼如下:

public void testTwo_2() {

    int a[] = { 1, 2, 3, 4, 5, 5, 6 };

    Map<Integer, Integer> d = new HashMap<>();

    for (int i = 0; i < a.length; i++) {

        if (d.containsKey(a[i])) {

            d.put(a[i], d.get(a[i]) + 1);

        } else {

            d.put(a[i], 1);

        }

    }

    int val_max = -1;

    int time_max = 0;

    for (Integer key : d.keySet()) {

        if (d.get(key) > time_max) {

            time_max = d.get(key);

            val_max = key;

        }

    }

    System.out.println(val_max);

}

  我們來計算下這種方法的時空複雜度。代碼結構上,有兩個 for 循環。不過,這兩個循環不是嵌套關係,而是順序執行關係。其中,第一個循環實現了數組轉字典的過程,也就是 O(n) 的複雜度。第二個循環再次遍歷字典找到出現次數最多的那個元素,也是一個 O(n) 的時間複雜度。

  因此,總體的時間複雜度為 O(n) + O(n),就是 O(2n),根據複雜度與具體的常係數無關的原則,也就是O(n) 的複雜度。空間方面,由於定義了 k-v 字典,其字典元素的個數取決於輸入數組元素的個數。因此,空間複雜度增加為 O(n)。

  這段代碼的開發,就是借鑒了方法論中的步驟三,通過採用更複雜、高效的數據結構,完成了時空轉移,提高了空間複雜度,讓時間複雜度再次降低

 

文章知識點來源於自購課程《重學數據結構與算法》,在這裡做一個簡單的整理總結分析分享給大家。

敬請期待接下來會更新的博客–《回爐重造12時辰-數據處理不變應萬變》。

我是帝莘,希望能在博客園和你進行技術交流和思想交流!