30-03 之應用層的運算加速 - 演算法

正文開始

本篇文章開始,我們將要深入的探討,每一個服務,要如何儘可能的達到高性能呢 ?

這首先第一部份,我們要探討以下主題 :

在應用層,要如何儘可能的使用越少的資源( CPU、Memory ),來做最多的事情呢 ?

而這一題的主要的答案就是不少人面試很排斥的『演算法』。

本篇文章會分為以下幾段 :

  • 一個好與不好的演算法性能差距多大呢 ?
  • 演算法運算時間的分類
  • 演算法優化建議

接下來正文開始。

一個好與不好的演算法性能差距多大呢 ?

一個演算法的效能基本上有兩個東東 :

  • 時間複雜度: 你可以把它想成演算法的運行時間。
  • 空間複雜度: 這個可以想成你這個演算法需要花多少的空間來處理。

上面只是簡單說明它的代表概念,比較實際的運算方法直接去 wiki 看就夠囉。

那麼拉回拉,一個好與不好的演算法性能差距有多大呢 ?

呵 !

我們以一個最簡單的演算法『費波那契數列』來看看。

首先這是好的程式碼。

// good

console.time('time');
function fib (n) {
  if ( n === 0 || n === 1) {
    return n;
  }

  let a = 0;
  let res = 1;
  let temp = 0;

  for (let i=2; i <= n; i++) {
    temp = res;
    res = a + res;
    a = temp;
  }
  return res;
}

fib(45);
console.timeEnd('time');

再來這是爛的程式碼。

// bad

console.time('time');

function fib (n) {
  if ( n === 0 || n === 1) {
    return n;
  }
  return fib(n-1) + fib(n-2);
}

fib(45);
console.timeEnd('time');

然後咱們簡單的測試運行時間,你看看這兩個差多少倍,嗯好幾千倍。

good time: 2.609ms
bad time: 17315.706ms

這裡應該是有些人會想說,這種費波那契數列演算法或是很多演算法上網抓就好了,工作上又不太會自已寫,學演算法要幹啥呢 ?

某些方面是沒錯,但這裡問題在於 :

如果你抓成 bad 版本呢 ? 會發生什麼事情呢 ?

很多演算法的確不需要自已在寫,但如果有演算法概念與能力,至少不太會抓錯程式碼,抓錯這事咱真看過這慘況。

~ 小備註 ~ 原本想順到印出 stack 記憶體使用量,但是好像沒啥方法可以印出……。如果不太分的清楚 stack 與 heap 的差別可以參考此篇文章。

How to inspect the memory usage of a process in Node.Js

演算法運算時間的分類

這裡最重要的重點就在於,你要知道你寫的程式碼時間複雜度是屬於那個分級,如果你分不起來,然後寫到 O(2^n) 分級的演算法,那明眼人應該知道會發生什麼事情。

比較常見的分類,分為以下幾種,花費時間由小到大 :

  • O ( 1 )
  • O ( log n )
  • O ( n )
  • O ( n log n )
  • O ( n ^ 2 )
  • O ( 2 ^ n )

圖 1 : 時間複雜度的分級 (圖片來源: 初學者學演算法|談什麼是演算法和時間複雜度)

O ( 1 )

例如這種常見的,兩數交換,就是屬於 O(1) 操作。


var a = 1;
var b = 2;

var temp = b;
b = a;
a = temp;

O ( log n )

這個最常見的操作就是所謂的二分搜尋法,簡單的概念如下圖 2 所示,就是一半一半的找,但這個有個前提假設,那就是數組是要有規則已排序的才能使用這招。

圖 2 : 二分搜尋概念圖

O ( n )

只要有用一個 for 迴圈,那它基本上就屬於 O(n) 的時間複雜度。


for (var i=0; i < n; i++){
   ...
}

O ( n log n )

這裡只要記好,不管是任何的語言,你只要用到它內建的排序功能,那基本上就是 O(nlogn) 的時間複雜度,平均而言喔。

O ( n ^ 2 )

這個也非常的常見,就是內外兩個 for 回圈。


for (var i=0; i < n; i++){
    for (var j=0; j < n; j++){
        ...
    }
}

O ( 2 ^ n )

這種時間複雜度很容易出現在一種情境下,那就是不選的情境,不過這種情況比較常在考演算法題時看到,實務應該是不常看到。

實務上 CPU 與 Memory 優化建議

這裡我覺得要讓應用層以最少的 cpu 與 memory 做最多事情的要幾個要點 :

小建議 1 : 可以理解你寫的程式碼的時間與空間複雜度

簡單的說,你要可以知道你寫的程式碼的時間與空間複雜度,不要寫到了 n^5 的迴圈程式都不知道。然後當寫到這種多層迴圈的情況下,你要仔細的想想兩件事 :

  • 是否真的有必要 ? 有沒有其它寫法呢 ?
  • 如果真的有必要,在多少個數量可能會是臨界點呢 ?

小建議 2 : 熟悉各種工具所提供的方法

例如我們很常使用 redis,它裡面提供了一些資料結構來進行操作,這裡要使用好的要點,就是你要熟悉裡面每個資料結構所提供的操作方法,它的時間複雜度與空間複雜度,這裡如果你選錯了使用方法,那們你可能會耗費不少資源在做事情。

小建議 3 : 熟悉資料結構

現在不少的語言都有提供一些資料結構的操作,但是我相信不少人就是一個陣列幹到底,功能可以出來沒錯,但事實上有些情況下,選擇適當的資料結構使用,你會省下不少力氣並且性能也提升不少。

如果你不知道要學那些資料結構,就乖乖的買本資料結構的書吧。接下來再搭配你會的語言所提供的資料結構,像如果是 c++ 你就可以參考 STL,然後 Java 可以看看 Collection 等,而 js 呢 ? 你就先理解看看它的 Array 到底是啥鬼,並且看看它所提供的方法。

~ 學習小心得 ~

開始或許會覺得很困難,但久了就覺得還好了,畢竟痛久了,就習慣了。

小建議 4 : 熟悉一些演算法的套路

俗話說的好,不要重複做輪子。

多去理解一些演算法,或許會有小收穫,有時後你接到一項工作時,有可能事實上,已有人做過相同的事情了,有的人解決這項任務可能已經有 O(logn) 的寫法,但你偏偏自已寫,然後寫出一個 O(n^2) 的寫法,然後當系統快不行了,就和老闆說只能加機器來處理,這樣有點而不是很好呢

~ 學習小心得 ~

演算法學習也是個很困難的一條路,也同時是很容易讓人放棄的路,但是當你想繼續往上時,演算法就是基本了。建議這一條路找個伴一起學,真的比較不容易放棄,如果最後還是和伴一起放棄了,只能說無緣囉 ~

這裡順到提供一些我的演算法軍火庫,通常在碰到一個問題時,如果沒啥想法就會拿這些方法來思考看看有沒有適合的,而這些方法事實上也可以當成刷題用的分類……

  • BFS
  • DFS
  • Two-Points
  • DP
  • Binary Search
  • Sort
  • 資料結構 (tree、set、hash、prefix tree、binary tree)
  • BitManipulation
  • Recursion
  • Divid And Conquer
  • Greedy
  • 歸納法 (思考方法)
  • 演繹法 (思考方法)

請服用。

~ 小知識 ~

歸納法演繹法這兩種嚴格來說在 leetcode 沒有這種分門別類,但是它卻是所有演算法的核心思考方法。

  • 歸納法 : 就是將相同特性的東西歸納出來,例如這個吃漢堡、吃便當,這就可以歸納出吃東西這個概念
  • 演繹法 : 就是一種依順序的推導,例如人會死,孔子是人,所以孔子會死。

這裡只是很淺淺的說明,未來有機會希望可以開篇來詳談。

結論與心得

這一篇文章中,咱們討論如何以最少的 CPU 與 Memory 來做最多事情的一個重點,那就是 :

演算法

而且我們也知道,一個好的演算法與爛的算法,運行時間差了幾百倍都有可能,而這個影響在比較大的公司就有可能是百台以上的成本差異,雖然在小公司效果比較不顯著,但是如果寫的爛的話,也有可能少少的使用量下,你的機器就掰了。

然後這裡建議一般的開發者,演算法可以不用刷的要死要活,但至少要有演算法的概念,這樣才對得起付錢給你的人(不過如果你討厭老闆那就無所謂),但是如果你追求的對是一般,那就乖乖刷吧。

最後簡單的淺淡一下面試演算法這東西。基本上普通的公司,我不太贊成考演算法題目(我說題目喔)。主要的原因有下 :

  • 工作時用不到(比較準確的說法是,用了也不見得看得到效果)。
  • 有可能會錯失一些在其它方面很強的人。
  • 香蕉的問題。

但是我覺得可以簡單的考一些演算法的概念當參考評分比較用,但請不要第一關演算法題目沒過就刷人,除非公司是萬人想進那種類型,或是開得起 $$ 的則例外。

參考資料

comments powered by Disqus